TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-07-31

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

For every positive integer $n$ , $\sum_{d ∣ n, d > 0} φ (d) = n$

Statement

For every positive integer $n$ ,

$\sum_{\begin{array}{c} d ∣ n \\ d > 0 \end{array}} φ (d) = n .$

The sum is over the finite set of positive divisors of $n$ (The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form).

Facts & Assumptions

Given: A positive integer $n$ , its standard representative set $X : = {a \in Z : 0 \leq a < n}$ , and its positive-divisor set $D : = {d \in Z : d ∣ n, d > 0}$ .

[L1]

The set $X$ has cardinality $n$ , and the units modulo a positive $d$ are represented exactly once by the $u$ with $0 \leq u < d$ and $\gcd (u, d) = 1$ ; their number is $φ (d)$ (For $n \geq 1$ , every class in $Z / n$ has one representative $r$ with $0 \leq r < n$ , so $∣ Z / n ∣ = n$ ; while $Z / 0$ is in bijection with $Z$ , For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$ , The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ ).

[L2]

The gcd is a nonnegative common divisor, and $\gcd (c a, c b) = ∣ c ∣ \gcd (a, b)$ (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ , $\gcd (c a, c b) = ∣ c ∣ \gcd (a, b)$ for all integers $a, b, c$ , the identity holding at $c = 0$ and at $(a, b) = (0, 0)$ as well).

[L3]

A divisor of a nonzero integer has bounded absolute value; hence $D$ is a subset of a finite integer interval and is finite (If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ ; hence the set of divisors of a nonzero integer is bounded above by $∣ a ∣$ , A subset of a finite set is finite, with $∣ B ∣ \leq ∣ A ∣$ , and equality holds if and only if $B = A$ ).

[L4]

A finite set partitioned into finite blocks has cardinality equal to the sum of their cardinalities (The sum rule: a finite disjoint union is finite with $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣$ and $∣ ⋃_{i \in I} A_{i} ∣ = \sum_{i \in I} ∣ A_{i} ∣$ , and a sum over a finite index set splits along a partition, The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form).

[L5]

Integer divisibility gives quotient witnesses, and nonzero integer factors cancel (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ , The integers have no zero divisors; multiplicative cancellation).

Proof

technique · direct

1.1

For each $d \in D$ , put $X_{d} : = {a \in X : n / \gcd (a, n) = d}$ . Every $a \in X$ lies in exactly one such block: its positive gcd $g = \gcd (a, n)$ divides $n$ , and $d = n / g$ is a positive divisor of $n$ . Thus the $X_{d}$ form a partition of $X$ .

L2L5

1.2

Fix $d \in D$ and put $c : = n / d > 0$ . Multiplication by $c$ sends each standard unit representative $u$ modulo $d$ to $a : = c u \in X$ , because $0 \leq u < d$ gives $0 \leq c u < n$ ; moreover $\gcd (a, n) = \gcd (c u, c d) = c \gcd (u, d) = c$ , so $n / \gcd (a, n) = d$ and $a \in X_{d}$ .

L1L2

1.3

Conversely, if $a \in X_{d}$ , then $\gcd (a, n) = n / d = c$ , so $c ∣ a$ and $a = c u$ for a unique integer $u$ . The bounds on $a$ give $0 \leq u < d$ , and $c = c \gcd (u, d)$ by [L2], so cancellation gives $\gcd (u, d) = 1$ . Thus $u$ is a standard unit representative modulo $d$ .

L1L2L5

2.1

Steps 1.2 and 1.3 are inverse constructions, so $∣ X_{d} ∣ = φ (d)$ for every $d \in D$ .

step 1.2step 1.3L1

3.1

The index set $D$ is finite by [L3]. Applying the sum rule to the partition in step 1.1 and using step 2.1 gives $n = ∣ X ∣ = \sum_{d \in D} ∣ X_{d} ∣ = \sum_{d \in D} φ (d)$ .

step 1.1step 2.1L1L3L4∎

Remarks

The partition by $n / \gcd (a, n)$ is an incidence identity: each residue is assigned to one positive divisor, and the block over $d$ is counted by the units modulo $d$ .

Depends on

Used by

Dependency tree · two levels

51 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Mathematics LibreTexts, Euler's phi Function (standard reference, not scraped)
J. J. P. Veerman, sum of Euler phi over divisors (standard reference, not scraped)

For every positive integer nn, ∑d∣n, d>0φ(d)=n∑d∣n, d>0​φ(d)=n