Period 6,Group 5: Euler’s Totient Theorem
Homework Answers:
- Last two digits of 72016 is the same as 72016 mod 100. φ(100) = 40, so 72016 = (716)*750*40 mod 100 = 716 mod 100 = 498 mod 100 = 24014 mod 100 = 14 mod 100 = 1
- We can rewrite 932016 as (100-7)2016, which simplifies to (-7)2016, which is just 72016 = 1, as shown above. We can treat numbers as negative within modular systems to make calculations simpler.
- We divide this into two problems using the Chinese Remainder Theorem. We know 2183 mod 3 = 0 because 21 is divisible by 3. We must find 2183 mod 16. φ(16) = 8. 2183 mod 16 = (16+5)16*5+3= 53 mod 16 = 125 mod 16 = 13. So 2183 mod 48 = 0 mod 3 and 13 mod 16. Thus, it is 16*2+13 = 45
- By exponent rules, = .φ(55) = 40. So we must find mod 40. So we apply Euler’s theorem again. φ(40) = 16. 614166 mod 40 = 146 mod 40 = 27442 mod 40 = 242 mod 40 = 576 mod 40 = 36. So now we find 336 mod 55 = 819 mod 55 = 269 mod 55 = 313 mod 55 = 36
- First we show that φ(mn) is divisible by φ(m). Let n = a*b, where GCD(b,m) = 1 and each factor of a is a factor of m. Because GCD(m*a,b) = 1, φ(m*n) = φ(m*a) * φ(b). And because all the factors of a are factors of m, φ(m*a) = φ(m) * a. Thus, φ(m*n) is divisible by φ(m) for any m. Note that φ(p), where p is an odd prime, is p-1, which is even. This in conjunction with the previous result gives that any number divisible by an odd prime has even φ(n). The only numbers with no odd divisors are powers of 2, but φ(4) = 2 and all higher powers of 2 are divisible by 4, so they must be even too. Thus, all n > 2 have φ(n) is even.
Sources:
- own creation
- own creation