Assignment # 2-Number Theory

(1) Compute the following quantities:
(a) 3^29 (mod 31)
(b) 19^19 (mod 7):
(2) If possible, nd a pair of integers x and y that satisfy the given condition. If it is not
possible, explain why not.
(a) x and y are congruent modulo 3 but not modulo 6.
(b) x and y are congruent modulo 6 but not modulo 3.
(c) x and y are congruent modulo 5 but not modulo 10.
(d) x and y are congruent modulo 10 but not modulo 5.
(3) Let n be a non-negative integer. Prove that 5j3^(3n+1 )+ 2^(n+1).
(4) Prove that if n and m are odd and not divisible by 3, then 24j(n^2 – m^2).
(5) (a) Let p be a prime number greater than 3. What are the possible remainders of p
upon division by 6?
(b) What are the possible values of n2 (mod 6) for an odd integer n?
(c) Show that if 2^n + n^2 is a prime greater than 3, then n =3 (mod 6).
(6) Prove that 2^644 – 1 is divisible by 645. (Hint: First reduce 2^14 modulo 645.)
(7) Bonus: Prove that 11…1 is divisible by 41 if and only if n is divisible by 5.

assignment 2 solution