NUMBER-THEORY EXERCISES, V

DAVID PIERCE

As usual, p and q are primes. Exercise 1. The number 32 970 563 is the product of two primes. Find them. Exercise 2. Factorize 1 003 207 (the product of two primes) knowing

1 835^{2} ≡ 598^{2} (mod 1 003 207).

Exercise 3. Compute 16200 modulo 19. Exercise 4. If p ≠ q, and gcd(a, pq) = 1, and n = lcm(p − 1, q − 1), show

a^{n} ≡ 1 (mod pq).

Exercise 5. Show a^{13} ≡ a (mod 70). Exercise 6. Assuming gcd(n, p) = 1, and 0 ⩽ n < p, solve the congruence

a^{n}x ≡ b (mod p).

Exercise 7. Solve 2^{14}x ≡ 3 (mod 23).

Exercise 8. Show ∑_{k=1}^{p−1} k^{p} ≡ 0 (mod p).

Exercise 9. We can write the congruence 2^{p} ≡ 2 (mod p) as

2^{p} − 1 ≡ 1 (mod p).

Show that, if n | 2^{p} − 1, then n ≡ 1 (mod p). (Suggestion: Do this first if n is a prime q. Then 2^{q−1} ≡ 1 (mod q). If q ≢ 1 (mod p), then gcd(p, q − 1) = 1, so pa + (q − 1)b = 1 for some a and b. Now look at 2^{pa} · 2^{(q−1)b} modulo n.) Exercise 10. Let F_{n} = 2^{2^{n}} + 1. (Then F_{0}, …, F_{4} are primes.) Show

2^{F_{n}} ≡ 2 (mod F_{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: October 16, 2007.