Test 2 solution – Number Theory
1. State and prove Euler’s Theorem (generalization of Fermat’s Little Theorem). (4 points)
2. Find the last two decimal digits of 453^561. (4 points)
3. Determine, with explanation, whether or not there exists an integer n such that n^10 +1 is divisible by
151. (Note that 151 is prime.) (3 points)
4. (University of Illinois) Let p and q be distinct primes. Prove that, for any a -> Z, a^pq + a = a^p + a^q
mod pq. (5 points)
5. Prove for any c > 2 that phi(c) is even. (3 points)
6. Suppose p is an odd prime. Prove that there can be no primitive root mod m unless m = 2; 4; p^k; 2p^k. (4 points)
7. Prove that 2 is a primitive root modulo 19. Find all primitive roots modulo 19. (5 points)
8. Let p be an odd prime and a, b integers such that (p; ab) = 1. Prove that (ab/p)=(a/p)(b/p) (4 points)
9. Determine (83/17) (4 points)
10. Bonus: (King’s College, London) True or False. If true, prove. If false, give a counterexample.
“For all positive integers n, phi(n) > n=4.”
Leave a reply