Exercise 2.22

Show that the sum of all the integers t such that 1 ≤ t ≤ n and ( t , n ) = 1 is 1 2 nϕ ( n ) .

Answers

Proof. Suppose n > 1 (the formula is false if n = 1 ).

Let S = ∑ ⁡ 1 ≤ t ≤ n , t ∧ n = 1 t = ∑ 1 ≤ t ≤ n − 1 , t ∧ n = 1 t .

Using the symmetry t ↦ n − t , as t ∧ n = 1 ⟺ ( n − t ) ∧ n = 1 , we obtain

2 S = ∑ 1 ≤ t ≤ n − 1 , t ∧ n = 1 t + ∑ 1 ≤ t ≤ n − 1 , t ∧ n = 1 t = ∑ 1 ≤ t ≤ n − 1 , t ∧ n = 1 t + ∑ 1 ≤ s ≤ n − 1 , ( n − s ) ∧ n = 1 n − s ( s = n − t ) = ∑ 1 ≤ t ≤ n − 1 , t ∧ n = 1 t + ∑ 1 ≤ t ≤ n − 1 , ( n − t ) ∧ n = 1 n − t = ∑ 1 ≤ t ≤ n − 1 , t ∧ n = 1 t + ∑ 1 ≤ t ≤ n − 1 , t ∧ n = 1 n − t = ∑ 1 ≤ t ≤ n − 1 , t ∧ n = 1 n = n Card { t ∈ ℕ | 1 ≤ t ≤ n − 1 , t ∧ n = 1 } = nϕ ( n )

Conclusion :

∀ ⁡ n ∈ ℕ ∗ , ∑ 1 ≤ t ≤ n , t ∧ n = 1 t = 1 2 nϕ ( n ) .

(See another interesting proof in Adam Michalik’s paper.) □

User profile picture
2022-07-19 00:00
Comments