4 CSE/MATH 467 Due: 16 September, 2016 1 and 2. For b Z and k1 , k2 Z0 , we have the following rules for exponents: i) bk1 bk2 = bk1 +k2 ii) (bk1 )k2 = bk1 k2 A) Deduce those laws for elements Z/mZ and k1 , k2 Z0 . B) Moreover if Z/mZ and Z/mZ with = 1 in Z/mZ, for k Z0 we define k := ( )k . Show that the these two rules can be shown to hold for all k1 , k2 Z. (by converting everything to use positive exponents). Hint If such , Z/mZ exist, then show that ( ) = and consider four cases for each of i) and ii) depending on the signs of k1 , k2 . C) Another approach to the latter identities comes from the fact that, for k Z0 and Z/mZ, = ( )k if and only if k = 1. Prove the displayed equivalence. 3. This problem generalizes Part c) of problem 5 of the previous homework set. Let gcd(c, m) = g. a) Show that if kc + lm = g, then gcd(k, l) = 1. b) Show that if we write m = m0 g, c = c0 g, then gcd(c0 , m0 ) = 1. c) Prove that ec f c mod m e f mod m0 . 4. Use the definition of congruence and Fermat's Little Theorem, to show that, if gcd(b, 561) = 1, then mod 3, 1 560 b 1 mod 11 1 mod 17. Conclude that, if gcd(b, 561) = 1, then b560 1 mod 561 and so 561 is a Carmichael number. Hint: What does it mean that b560 1 mod 561? 2 5. a) Prove by induction on k that if m1 , . . . , mk N>1 are pair-wise relatively prime and we set m = m1 , . . . , mk , then the map a 7 (a%m1 , . . . , a%mk ) is a 1-1 correspondence from {0, . . . , m} {0, . . . , m1 } {0, . . . , mk }. b) Deduce the general Chinese Remainder Theorem. c) Why would it be enough to prove that the map in a) is 1-1? d) Why is it enough to show that the composite map \"hits\" every element of the target, i.e. that the composite is \"onto\"? Hint for A: In the Induction Step, explain why each of the horizontal maps is a 1-1 correspondence and why that makes the composite map into a 1-1 correspondence: Zm1 ...mK Zm1 ZmK1 ZmK Z(m1 ...mK1 )mK Zm1 ...mK1 ZmK (Zm1 ZmK1 ) ZmK Coding Problem (Due September 23). Write fast exponentiation code and find ten 10-digit probable primes (with respect to base 2)