18.781: Solution to Practice Questions for Final Exam

18.781: Solution to Practice Questions for Final Exam 2 2 1. Find three solutions in √ positive integers of |x − 6y | = 1 by first calculating the continued fraction expansion of 6. Solution: We have √ 1 6 = [2, √ ] 6−2 √ 6+2 = [2, ] 2 √ 1 2 = [2, 2, √ ] = [2, 2, √ ] = [2, 2, 6 + 2] 6−2 6−2 2 1 ] 6−2 = [2, 2, 4, 2, 4, 2, 4, . . . ] = [2, 2, 4]. = [2, 2, 4, √ Therefore, looking at [2, 2] we get 5/2, which leads to 52 − 6 · 22 = 1. Therefore (5, 2) is a solution. To get two more we compute √ √ (5 + 2 6)2 = 49 + 20 6 √ √ √ √ (5 + 2 6)3 = (5 + 2 6) · (49 + 20 6) = 485 + 198 6. Therefore (5, 2), (49, 20) and (485, 198) are three solutions. Note that since the length of the period is 2 (even) there are no solutions to x2 − 6y 2 = −1. 2. If θ1 = [3, 1, 5, 9, a1 , a2 , . . . ] and θ2 = [3, 1, 5, 7, b1 , b2 , . . . ], show that |θ1 − θ2 | < 49/7095. Solution: Let θ = [3, 1, 5] = 23/6. Then computing the next convergent to [3, 1, 5, 9] = 211/56, we see that |θ1 − θ| < 1/(6 · 55). Similarly |θ2 − θ| < 1/(6 · 43). So by the triangle inequality |θ1 − θ2 | ≤ |θ1 − θ| + |θ − θ2 | < 1/(6 · 55) + 1/(6 · 43) = 49/7095. Note: once you compute [3, 1] = 4/1 and [3, 1, 5] = 23/6, you can be a bit lazy and not compute say [3, 1, 5, 9], since you’re only interested in q3 = a3 q2 + q1 = 9 · 6 + 1 = 55. Similarly for [3, 1, 5, 7]. 3. For n = 1728, figure out the number of positive divisors of n, and the sum of its positive divisors. Solution: n = 26 33 , so d(n) = (6 + 1)(3 + 1) = 28, and σ (n) = 27 − 1 34 − 1 · = 127 · 40 = 5080. 2−1 3−1 4. Use multiplicativity to calculate the sum  φ(d) . d d|2592 1 Solution: Since f (n) = φ(n)/n is a multiplicative function of n, so is g =U ∗f =  φ(d) d|n d . So we need to figure out what it is on prime powers. We have g(1) = 1 and for e ≥ 1,   p − 1 p(p − 1) pe−1 (p − 1) 1 e g(p ) = 1 + + + ··· + = 1+e 1− . p p2 p−1 p Now 2592 = 25 34 . We have g(25 ) = 1 + 5/2 = 7/2 and g(34 ) = 1 + 8/3 = 11/3. So g(n) = 77/6. 5. Prove that if a prime p > 3 divides n2 − n + 1 for an integer n, then p ≡ 1 (mod 6). (the original problem should have said p > 3) Solution: We have n2 − n + 1 ≡ 0 (mod p). So 4n2 − 4n + 4 ≡ 0 (mod p). That is, (2n − 1)2 ≡ −3 (mod p). So −3 is a quadratic residue mod p (since gcd(3, p) = 1). This forces p ≡ 1 (mod 3), since      p p −3 −1 3 1= = = (−1)(p−1)/2 (−1)(p−1)/2 = , p p p 3 3 and the last expression is +1 if p ≡ 1 (mod 3) and −1 if p ≡ 2 (mod 3). 6. Compute the value of the infinite periodic fraction 12, 24. Find the smallest positive (i.e. both x, y > 0) solution of x2 − 145y 2 = 1. √ Solution: Let y = [24] = 24+1/y. Then y 2 −24y−1 = 0, √ so y = 12+ 145 √ (plus sign because √ y > 0). Therefore x = [12, 24] = 12 + 1/y = 12 + 1/(12 + 145) = 12 + 145 − 12 = 145. The period is odd. Therefore the smallest positive solution to the Brahmagupta-Pell equation will come from [12, 24] = 12 + 12/24 = 289/24, and it is (289, 24). Note that [12] = 12/1 will give 122 − 145 · 12 = −1. 7. Determine whether there is a nontrivial integer solution of the equation 49x2 + 5y 2 + 38z 2 − 28xy + 70xz − 28yz = 0. Solution: Let’s simplify the conic. It’s expeditious to first scale x by 1/7, gettting x2 + 5y 2 + 38z 2 − 4xy + 10xz − 28yz = (x − 2y + 5z)2 + y 2 + 13z 2 − 8yz. Therefore replacing calling (x − 2y + 5z) our new variable x, we get x2 + y 2 + 13z 2 − 8yz = x2 + (y − 4z)2 − 3z 2 . So we end up with x2 + y 2 − 3z 2 which is already nice and squarefree. By Legendre’s theorem, we just need to verify whether the local conditions are satisfied. The coefficients 1, 1, −3 don’t all have the same sign, so that one’s ok. We also need to check that −1 is a square mod 3, which is not ok. So the original conic doesn’t have any nontrivial rational or integer points. 2 8. Find a Pythagorean triangle such that the difference of the two (shorter) sides is 1, and every side is at least 100. Solution: Suppose that the sides are r 2 − s2 , 2rs, r 2 + s2 . (In general, they will be some common multiple of these, but the fact that the difference of two of the sides is 1, and positivity of the sides, forces that multiple to be 1 anyway). So we need |r 2 − s2 − 2rs| = 1, i.e. |(r − s)2 − 2s2 | = 1. Let x = r − s and y = s, then this is just a Brahmagupta-Pell type equation x2 − 2y 2 = ±1. 2 We want a solution such that s = y and r = x+y ar √e both positive, and such that min(2rs, r − 2 s ) is larger than 100. The continued fraction of 2 is [1, 2]. So the smallest positive solution comes from [1] = 1/1, i.e. is (x, y) = (1, 1) (which we could have guessed anyway, without 2 using continued fractions). Now 12 −2·1 the √ to look at√ √ n = −1. To get all solutions, we just have rational and irrational parts of (1+ 2) . The smallest one which works is (1+ 2)3 = 7+5 2. So we get (r, s) = (12, 5). So the Pythagorean triangle is (119, 120, 169). 9. Show that x2 + 2y 2 = 8z + 5 has no integral solution. Solution: Looking mod 8, we see that we have x2 + 2y 2 ≡ 5 (mod 8). Now, further looking mod 2 we see x must be odd. So x2 ≡ 1 (mod 8), which forces 2y 2 ≡ 4 (mod 8). This is impossible, since if y is even, then 2y 2 ≡ 0 (mod 8), and if y is odd, then 2y 2 ≡ 2 (mod 8). 10. Define a sequence by a0 = 2, a1 = 5 and an = 5an−1 − 4an−2 for n ≥ 2. Show that an an+2 − a2n+1 is a square for every n ≥ 0. Solution: The characteristic polynomial is T 2 − 5T + 4 = (T − 1)(T − 4). So we must have an = A · 4n + B · 1n . Subsituting in n = 0 and 1, we get an = 4n + 1. So an an+2 − a2n+1 = (4n + 1)(4n+2 + 1) − (4n+1 + 1)2 = 4n+2 + 4n − 2 · 4n+1 = 4n (16 + 1 − 2 · 4) = 9 · 4n = (2 · 3n )2 which is a perfect square. 11. Let p  ab. Show that ax2 + by 2 ≡ c (mod p) has a solution. Solution: Consider the (p + 1)/2 number ax2 for x = 0, . . . , (p − 1)/2. These are all distinct modulo p. Similarly, the (p + 1)/2 numbers c − by 2 are also all distinct modulo p. Since we now have p + 1 numbers in all, and only p residue classes mod p, by the Pigeonhole principle, two of these must be congruent mod p. Therefore we must have ax2 ≡ c − by 2 (mod p) for some x, y. Therefore the congruence has a solution. 12. How many solutions are there to x2 + 3x + 18 ≡ 0 (mod 28)? Find all of them. Solution: We need to figure out the number of solutions mod 4 and mod 7, and multiply. Modulo 4 we have x2 + 3x + 2 ≡ (x + 1)(x + 2) (mod 4). It’s easy to see this has the solutions x ≡ −1, −2 (mod 4). Note: one must be very careful when dealing with congruences modulo prime powers. It’s not necessarily true that if you have a product of (e.g. linear) factors, that the product will 3 be zero mod pe iff one of them is. For example, x(x + 2) ≡ 0 (mod 8) has more than the two solutions x ≡ 0, −2; in fact, any even number x will make x(x + 2) vanish mod 8, so there are 4 solutions mod 8. If pe is small enough, the best strategy is probably just to run over all the congruence classes and check. On the other hand, if you’re working mod a prime (i.e. e = 1) then you can separate out factors. Modulo 7 we have x3 + 3x + 18 ≡ x2 − 4x + 4 = (x − 2)2 ≡ 0 (mod 7). So just one solution x ≡ 2 (mod 7). So the total number of solutions mod 28 is 2 · 1 = 2. To find them, we need the linear combination 2 · 4 + (−1) · 7 = 1. Then to combine −1 and 2 we have (−1) · (−1) · 7 + 2 · 2 · 4 = 23. To combine −2 and 2 we have (−2) · (−1) · 7 + 2 · 2 · 4 = 30 ≡ 2 (mod 28). So the two solutions mod 28 are 2 and 23. 13. Let a, m be positive integers, not necessarily coprime. Show that am ≡ am−φ(m) (mod m).  Solution: Write m = pei i . Enough to prove that am ≡ am−φ(m) (mod pei i ) for every i. If pi  a then by Euler ei ) aφ(pi Since φ(pei i ) divides φ(m) =  ≡ 1 (mod pei i ). φ(pei i ), we get that aφ(m) ≡ 1 (mod pei i ), and then by multiplying by am−φ(m) , we get the desired congruence. On the other hand, if pi |a, then the left and right sides of the congruence we wish to prove will be divisible by m−φ(m) pm respectively. If we prove that both the exponents are at least ei , then both i and pi sides will be congruent to 0 modulo pei i , and we’ll be done. It’s obviously enough to prove m − φ(m) ≥ ei , since m ≥ m − φ(m). We’ll assume m > 1, since if m = 1 there are no primes dividing it, and nothing to prove. Now note that m > φ(m) (since φ(m) is the number of integers in {1, . . . , m} coprime to m, and there’s at least one which is not coprime to m, namely m). Also, since pei i |m, remembering that φ(m) = pei i −1 times other stuff, we see that pei i −1 divides m − φ(m). So m − φ(m) ≥ pei i −1 ≥ 2ei −1 ≥ ei whenever ei ≥ 1. (It’s an easy exercise to prove by induction that 2e−1 ≥ e for any e ∈ N.) 14. Parametrize all the rational points on the curve x2 − 3y 2 = 1. Solution: We find one trivial point (1, 0). So write y = m(x − 1) and plug it in, to get x2 − 3m2 (x − 1)2 = 1 So (x − 1)(x + 1) = 3m2 (x − 1)2 . Cancelling a factor of (x − 1), we get x + 1 = 3m2 (x − 1) 4 So x = (3m2 + 1)/(3m2 − 1) and then y = m(x − 1) = 2m/(3m2 − 1). This parametrizes all rational points on the conic (except for the original point (1, 0), which is obtained as a limit when m → ∞). 15. Find an integer solution of 37x + 41y = −3. Solution: We run the Euclidean algorithm on 37 and 41 to get 1 0 41 0 1 37 −1 1 −1 4 −9 −9 10 1 So (−9) · 41 + 10 · 37 = 1. 16. Show that if n > 1 then n  2n − 1. (Hint: consider the smallest prime dividing n). Solution: By contradiction. Suppose n|2n − 1. Let p be the smallest prime dividing n. Then p|2n − 1. So the order of 2 mod p divides n. But it also divides p − 1. So the order h of 2 mod p is less than p and divides n, and so are the primes dividing h. Since there’s no prime smaller than p which divides n, the order must be 1. So 21 ≡ 1 (mod p), which is impossible. 17. Let p ≥ 11 be prime. Show that for some n ∈ {1, . . . , 9}, both n and n + 1 are quadratic residues. If either 2 or 5 is a quadratic residue mod p, we’re done, considering the pairs (1, 2) and (4, 5), since 1 and 4 are squares and therefore quadratic residues. If both 2 and 5 are quadratic nonresidues, then 10 is a quadratic residue. So (9, 10) does the job. 18. Show that if 23a2 ≡ b2 (mod 17) then 23a2 ≡ b2 (mod 289). Solution: We calculate           23 6 3 17 2 = = = = = −1. 17 17 17 3 3 So if 23a2 ≡ b2 (mod 17) then we claim 17 | a, else we would have 23 ≡ (ba−1 )2 (mod 17) which is a contradiction to the above calculation. So 172 | 23a2 = b2 and so 17 | b. Then 172 | 23a2 − b2 , so 23a2 ≡ b2 (mod 289).  19. Calculate the product α (2 − α), where α runs over the primitive 14’th roots of unity. Solution: We compute the cyclotomic polynomial Φ14 (x) noting that it must have degree φ(14) = 6. x14 − 1 = (x7 − 1)(x7 + 1). Throwing out x7 − 1, we have x7 + 1 = (x + 1)(x6 − x5 + x4 − x3 + x2 − x + 1) 5 So Φ14 (x) = x6 − x5 + x4 − x3 + x2 − x + 1.  Note that Φ14 (x) = α (x − α), where α runs over the primitive 14’th roots of unity. Substituting x = 2 in, we get  (2 − α) = 26 − 25 + 24 − 23 + 22 − 2 + 1 = 43. α 20. Let f be a multiplicative function with f (1) = 1, and let f −1 be its inverse for Dirichlet convolution. Show that f −1 is multiplicative as well, and that for squarefree n, we have f −1 (n) = μ(n)f (n). Solution: The inverse f −1 is defined by f ∗ f −1 = 1, and it exists as long as f (1) = 0, as we showed on a problem set. To show it’s multiplicative, we will define a function g which will be multiplicative by definition, and show that f ∗ g = 1. Then it will follow that f −1 = g. So let g(1) = 1, and define g on prime powers pe by induction on e ≥ 1 by letting 1(pe ) = 0 = (f ∗ g)(pe ) = f (1)g(pe ) + f (p)g(pe−1 ) + . . . f (pe−1 )g(e) + f (pe )g(1) = g(pe ) + f (p)g(pe−1 ) + . . . f (pe−1 )g(e) + f (pe )g(1). Since g(1), . . . , g(pe−1 ) have been defined by the inductionhypothesis, we can solve this g(pei i ). By construction, g is uniquely for g(pe ). Then for n = pe11 . . . perr , define g(n) = multiplicative. Therefore so is g ∗ f . By construction (g ∗ f )(1) = 1 and (g ∗ f )(pe ) = 0 for e ≥ 1. So (g ∗ f )(n) = 0 for n ≥ 1 by multiplicativity. That is, g ∗ f = 1. Therefore g is the multiplicative inverse of f . Note that there is a unique multiplicative inverse, since if g were another inverse, then g = g ∗ 1 = g ∗ (f ∗ g ) = (g ∗ f ) ∗ g = 1 ∗ g = g . Finally, we need to show g(n) = μ(n)f (n) for n squarefree. By multiplicativity of g, μ and f , it’s enough to show this when n = p, a prime (it’s clearly true for n = 1). But then g(p) is defined by 0 = g(p) + f (p)g(1) = g(p) + f (p). That is, g(p) = −f (p) = μ(p)f (p), which finishes the proof. 6