Exercise 1 (15 points). Prove that for integers n > 1 and k > 1, we...

Transcribed Image Text:

Exercise 1 (15 points). Prove that for integers n > 1 and k > 1, we have 4(n) = nk-14(n), where (n) is the Euler's totient function: (n)=#{a Z | 1an AND gcd(a, n) = 1}. Exercise 2 (15 points). Notice that, when n is an odd number, n > 1, then [2] Z. Let f be a function f: {nN n odd AND n >1} N defined as follows: f(n) is the order of [2] modulo n. Prove that, for h, k odd, h, k > 1, and gcd(h, k) = 1, we have f(hk) = lcm(f(h), f(k)), where lcm denotes the least common multiple, defined in HW04, Exercise 4. Exercise 3 (10 points). Use the baby-steps-giant-steps algorithm to find h, k such that 2 7 (mod 53), 2k = 9 (mod 53). Exercise 4 (20 points). Solve the following congruences. (a) 523 (mod 71). (b) 333 (mod 61). (c) 11 (mod 89). (d) 837 (mod 73). (Hint:) Note that [7], [2], [3], [5] is a primitive element modulo 71, 61, 89, 73 respectively. Exercise 1 (15 points). Prove that for integers n > 1 and k > 1, we have 4(n) = nk-14(n), where (n) is the Euler's totient function: (n)=#{a Z | 1an AND gcd(a, n) = 1}. Exercise 2 (15 points). Notice that, when n is an odd number, n > 1, then [2] Z. Let f be a function f: {nN n odd AND n >1} N defined as follows: f(n) is the order of [2] modulo n. Prove that, for h, k odd, h, k > 1, and gcd(h, k) = 1, we have f(hk) = lcm(f(h), f(k)), where lcm denotes the least common multiple, defined in HW04, Exercise 4. Exercise 3 (10 points). Use the baby-steps-giant-steps algorithm to find h, k such that 2 7 (mod 53), 2k = 9 (mod 53). Exercise 4 (20 points). Solve the following congruences. (a) 523 (mod 71). (b) 333 (mod 61). (c) 11 (mod 89). (d) 837 (mod 73). (Hint:) Note that [7], [2], [3], [5] is a primitive element modulo 71, 61, 89, 73 respectively.