18.781 Solutions to Practice Problems for Midterm 1

Solutions to practice problems for Midterm 1 1. Find the gcd of 621 and 483. Solution: We run the Euclidean algorithm: 621 = 1 · 483 + 138 483 = 3 · 138 + 69 138 = 2 · 69. So gcd(621, 483) = 69. 2. Find a solution of 621m + 483n = k, where k is the gcd of 621 and 483. Solution: Building upon problem 1, we extend the table: 1 1 3 1 0 621 0 1 483 1 −1 138 −3 4 69 So −3 · 621 + 4 · 638 = 69, i.e. (m, n) = (−3, 4) works. 3. Calculate 364 modulo 67 by repeated squaring. Solution: We have 34 = 81 ≡ 14 8 2 3 ≡ 14 = 196 ≡ −5 16 2 (mod 67) (mod 67) ≡ 5 ≡ 25 (mod 67) 332 ≡ 252 = 625 ≡ 22 (mod 67) 3 3 64 2 ≡ 22 = 484 ≡ 15 mod 67. 4. Calculate 364 modulo 67 using Fermat’s little theorem. Solution: We know 366 ≡ 1 (mod 67). So 32 · 364 ≡ 1 (mod 67) . so we just need to invert 9 mod 67. You can either do this by the Euclidean algorithm, or by inspection. For example, 67 · 2 + 1 = 135 = 15.9, so it follows that 9−1 ≡ 15 (mod 67). 5. Calculate φ(576). Solution: The factorization is 576 = 242 = 26 · 32 . So φ(576) = 25 · 3 · 2 = 192. 6. Find all the solutions of x3 − x + 1 ≡ 0 (mod 25). Let f (x) = x3 − x + 1. First we find solutions to f (x) ≡ 0 (mod 5), just by trying all the values of x modulo 5. We see that x ≡ −2 (mod 5) is the only solution. Now we want to apply Hensel’s lemma. We have 1 f  (x) = 3x2 − 1 and f  (−2) = 11 ≡ 1 (mod 5). So f  (−2) = f  (−2)−1 ≡ 1 (mod 5). Finally, f (−2) = −5, so the solution modulo 25 is −2 − (−5) · 1 = 3 (mod 2)5. We check that 33 − 3 + 1 = 25 ≡ 0 (mod 25). 7. Find all solutions of x3 − x + 1 ≡ 0 (mod 35). Solution: The idea is to solve it modulo 5 and 7 and then use the Chinese remainder theorem. The unique solutions modulo 5 and 7 are −2 and 2 , respectively. Also, we have 3·5−2·7 = 1. So to combine the solutions, we take 15 · 2 + (−14) · (−2) = 30 + 28 = 58 ≡ 23 (mod 35). 8. Find the smallest integer N such that φ(n) ≥ 5 for all n ≥ N . Solution: Trying out small values of n, we see that φ(12) = 4 but φ(n) seems  eito be greater than 4 for all n ≥ 13. Let’s prove this: suppose n ≥ 11. Let n = pi , so φ(n) =  ei −1 pi (pi − 1). Let e be the power of 2 dividing n. If e ≥ 4, then φ(n) ≥ 2e−1 ≥ 8. So we only need to consider e = 0, 1, 2, 3. If e = 0, then n is odd. If n is prime, then φ(n) = n − 1 ≥ 12. Otherwise, either n will be divisible by at least two distinct odd primes p and q, in which case φ(n) ≥ (p−1)(q−1) ≥ 2·4 = 8, or n is divisible by p2 for some odd prime p, in which case φ(n) ≥ p(p − 1) ≥ 3(3 − 1) = 6. Next suppose e = 1. Then n = 2m where m is odd and m = n/2 ≥ 7. We have φ(n) = φ(m). Then if m is prime, φ(n) = m − 1 ≥ 6. Otherwise, the above reasoning (for the e = 0 case) shows that φ(n) ≥ 6. Next, the case e = 2. Then n = 4m, with m odd and m = n/4 > 3, so m ≥ 5 since m is an odd integer. So φ(n) = 2φ(m). As before we show that φ(m) ≥ 4, so φ(n) ≥ 8. Finally, if e = 3 then n = 8m, with m odd and m = n/8 > 1. So m ≥ 3. Then φ(n) = 4φ(m) = 4 · 2 = 8. 9. Find two positive integers m, n such that φ(mn) = φ(m)φ(n). Solution: In fact, any two integers which are not coprime will do! For example, m = n = 2 gives φ(m) = φ(n) = 1 and φ(mn) = 2. 10. True or false: two positive integers m, n are coprime if and only if φ(mn) = φ(m)φ(n). Give a proof or counterexample. Solution: This is true. Let pi (for i ∈ I) be the common primes dividing both m and n. Let qj (for j ∈ J) be the primes dividing m but not n, and let rk (for k ∈ K) be the primes dividing n but not m.  e  fj m= pi i qj and n=  2 pfi i  rkhk . Then calculating φ(m), φ(n) and φ(mn) gives   φ(m)φ(n)  1 = 1− . φ(mn) pi Since 1 − 1/pi < 1, the only way this product could be 1 is if its is empty, i.e. if there are no common primes dividing m and n. 11. Give the definition of a reduced residue system modulo n. 12. State and prove the Chinese remainder theorem. 13. Show that (n − 1)! ≡ 0 (mod n) for composite n > 4. [Hint: Make sure that your proof works for the case n = p2 , where p is a prime].  p2 then p and n/p are both less Solution: Let p be the smallest prime dividing n. If n = than n and are distinct. So (n − 1)! is divisible by p(n/p) = n. Now, if n = p2 then since p > 2 (because n > 4) we see that p and 2p are both less than n. So (n − 1)! is divisible by p · 2p = 2p2 = 2n and therefore by n. 14. Solve the system of congruences x≡1 (mod 3) x≡2 (mod 5) x≡3 (mod 7) Solution: We need to apply CRT. We have 3 · 5 = 15 ≡ 1 (mod 7), with inverse 1. Next, 3 · 7 = 21 ≡ 1 (mod 5), with inverse 1. Finally, 5 · 7 = 35 ≡ −1 (mod 3), with inverse −1. So the solution is x ≡ 1 · 35 · (−1) + 2 · 21 · 1 + 3 · 15 · 1 = −35 + 42 + 45 = 52 (mod 105). 15. Let n be a positive integer. Show the identity n    n i = n2n−1 . i i=1 [Hint: differentiate both sides of the Binomial theorem, or manipulate the binomial coefficients.]   Solution: We have (1 + x)n = ni=0 ni xi . Differentiating we get n(1 + x)n−1 = n    n i−1 i x i i=1 where the i = 0 term goes away because differentiating a constant gives 0. Now plugging in x = 1, we get the result. 3 16. Calculate the order of 3 modulo 301. Solution: Note that 301 = 7 · 43. If h1 is the order of 3 mod 7 and h2 is the order of 3 mod 43, then the order of 3 mod 301 will just be the LCM (least common multiple of h1 and h2 ). Now, we know by Fermat that 36 ≡ 1 (mod 7). It’s easy to see that 32 and 33 are not 1 modulo 7. So h1 = 6. Also 342 ≡ 1 (mod 43). Since the order divides 42, it either equals 42 or divides 42/p, where p is one of the primes dividing 42, namely 2, 3 or 7. Now it’s easy to check that 321 , 314 , 36 are all not 1 mod 43. So h2 = 42. Therefore h2 = 42. Therefore the order of 3 mod 301 is LCM(6, 42) = 42. 4