Definition D1
A natural number d is a divisor of n when there is a natural number e with n = d · e, written d ∣ n.
Proof.
n = d·e = e·d, so e is also a divisor of n.convention, A1
∎
Definition D2
Let D(n) = { d : d ∣ n }, and let d(n) denote the number of its elements.
Proof.
(1)If d ∈ D(n), then n = d·e with e ≥ 1, so n = d·e ≥ d.D1, O1, O2
(2)Every divisor is at most n, so D(n) is a finite set.(1)
∎
Lemma L1
For each d ∈ D(n), the natural number x with n = d · x is unique. Writing that x as φ(d), φ maps D(n) into D(n) and φ(φ(d)) = d.
Proof.
(1)If d ∈ D(n), there is a natural number e with n = d·e.D1
(2)d is a natural number, so d ≥ 1 and d ≠ 0O1
(3)If d·e = d·e′, then since d ≠ 0, e = e′. Such an e is unique.(1), (2), A1, A2
(4)Write that e as φ(d).(3), convention
(5)n = d·φ(d) = φ(d)·d, so φ(d) ∈ D(n)(4), A1, D1
(6)φ(φ(d)) is the unique x with n = φ(d)·x, and n = φ(d)·d, so φ(φ(d)) = d(3), (5)
∎
Lemma L2
For d ∈ D(n), φ(d) = d holds exactly when d · d = n.
Proof.
(1)φ(d) satisfies n = d·φ(d).L1
(2)If φ(d) = d, then n = d·d(1), E
(3)Conversely, if n = d·d then d ∈ D(n), and φ(d) is the unique x with n = d·x, so φ(d) = dD1, L1
∎
Lemma L3
Let F = { d ∈ D(n) : φ(d) = d } and R = D(n) ∖ F. Then |R| is even.
Proof.
(1)F and R split D(n) into two parts with nothing left over.convention, D2
(2)If d ∈ R then φ(d) ∈ R. For if φ(d) were a fixed point, then φ(φ(d)) = φ(d), and φ(φ(d)) = d, so φ(d) = d, contradicting d ∈ R.(1), L1
(3)On R, define d ~ d′ by 'd′ = d or d′ = φ(d)'. Since φ(φ(d)) = d, this relation is reflexive, symmetric, and transitive.(2), L1, E
(4)Therefore R is partitioned into the blocks of this relation.(3), A4
(5)Each block is { d, φ(d) }, and d ∈ R, so φ(d) ≠ d. Each block has 2 elements.(1), (3), (4)
(6)If there are k blocks, then |R| = 2k(5), A5
(7)Therefore |R| is even.(6), A7
∎
Lemma L4
F has at most one element.
Proof.
(1)Suppose d, d′ ∈ F.assumption
(2)d·d = n and d′·d′ = n, so d·d = d′·d′(1), L2, E
(3)Natural numbers with equal squares are equal, so d = d′(2), A3
∎
Theorem T1
If d(n) is odd, then n is a square.
Proof.
(1)Suppose d(n) is odd.assumption
(2)d(n) = |F| + |R|D2, L3, A6
(3)|R| is even.L3
(4)Adding an even number preserves parity, so |F| is odd.(1), (2), (3), A8
(5)0 is even, so |F| ≠ 0, and F has an element.(4), A7, A9
(6)If d ∈ F then d·d = n, so n is a square.(5), L2
∎
Theorem T2
If n is a square, then d(n) is odd.
Proof.
(1)Suppose there is a natural number d with n = d·d.assumption
(2)Then φ(d) = d, so d ∈ F(1), L2
(3)F has at most one element, so |F| = 1(2), L4
(4)d(n) = |F| + |R| = 1 + |R|, and |R| is even.(3), L3, A6
(5)Therefore d(n) is odd.(4), A8, A7
∎