NUMBER-THEORY EXERCISES, VII

DAVID PIERCE

Exercise 1. f(568) = f(638) when f ∈ {τ, σ, ϕ}.

Exercise 2. Solve:

(a) n = 2ϕ(n).

(b) ϕ(n) = ϕ(2n).

(c) ϕ(n) = 12. (Do this without a table. There are 6 solutions.)

Exercise 3. Find a sequence (a_{n}: n ∈ ℕ) of positive integers such that

lim_{n→∞} \frac{ϕ(a_{n})}{a_{n}} = 0.

(If you assume that there is an answer to this problem, then it is not hard to see what the answer must be. To actually prove that the answer is correct, recall that, formally,

∑_{n} \frac{1}{n} = ∏_{p} \frac{1}{1 − \frac{1}{p}} ,

so lim_{n→∞} ∏_{k=0}^{n} \frac{1}{1 − \frac{1}{p_{k}}} = ∞ if (p_{k}: k ∈ ℕ) is the list of primes.)

Exercise 4. (a) Show a^{100} ≡ 1 (mod 1000) if gcd(a, 1000) = 1.

(b) Find n such that n^{101} ≢ n (mod 1000).

Exercise 5. (a) Show a^{24} ≡ 1 (mod 35) if gcd(a, 35) = 1.

(b) Show a^{13} ≡ a (mod 35) for all a.

(c) Is there n such that n^{25} ≢ n (mod 35)?

Exercise 6. If gcd(m, n) = 1, show m^{ϕ(n)} ≡ n^{ϕ(m)} (mod mn).

Exercise 7. If n is odd, and is not a prime power, and if gcd(a, n) = 1, show a^{ϕ(n)/2} ≡ 1 (mod n).

Exercise 8. Solve 5^{10000}x ≡ 1 (mod 153).

Exercise 9. Prove ∑_{d|n} μ(d)ϕ(d) = ∏_{p|n}(2 − p).

Exercise 10. If n is squarefree (has no factor p^{2}), and k ∈ ℕ, show

∑_{d|n} σ(d^{k})ϕ(d) = n^{k+1}.

Exercise 11. ∑_{d|n} σ(d)ϕ(\frac{n}{d}) = nτ(n).

Exercise 12. ∑_{d|n} τ(d)ϕ(\frac{n}{d}) = σ(n).

Mathematics Dept, Middle East Tech. Univ., Ankara 06531, Turkey E-mail address: dpierce@metu.edu.tr URL: http://www.math.metu.edu.tr/~dpierce/

Date: November 8, 2007.