First Exam for Math 463

First exam for Math 463 Time limit: 75 minutes. Problems 1—5 are worth 20 points each, Problem 6 is worth 10 extra points. All your answers must be justified. Good luck! In the following problems all variables are integers 1. Prove that n3 − n is divisible by 6 for every integer n. Solution 1. First note that (−n)3 − (−n) = −n3 + n = −(n3 − n).¡ This ¢ we may assume that n ≥ 0. Second, n3 − n = (n + 1) · n · (n − 1) = 6 · 16 (n + 1) · n · (n − 1) = 6 n3 . Solution 2. If 3|n, then 3|n(n2 − 1) = n3 − n. If 3 - n, then n = 3N ± 1 for some integer N . Thus n2 − 1 = (n − 1)(n + 1) = 3N (3N ∓ 2), and it follows that 3|n(n2 − 1) = n3 − n. Similarly, if 2|n, then 2|n(n2 − 1) = n3 − n. If 2 - n, then n = 2K + 1 for some integer K. Thus n − 1 = 2K and it follows that 2|(n − 1)(n + 1) · n = n3 − n. In all cases 2|n and 3|n, so 6|n. 2. Prove that (a, a + 2) = 1 or 2 for every integer a. Note that 2 = 1 · (a + 2) + (−1) · a. Because gcd(a, a + 2) divides every linear combination of a and a + 2, it follows that gcd(a, a + 2)|2. The only positive divisors of 2 are 1 and 2, so gcd(a, a + 2) = 1 or 2. ¯ a ¯¯ 3. Prove that a|bc if and only if c. (a, b) ¯ ³ ´ Let g = gcd(a, b). Obviously g|a and g|b, but also gcd( ag , gb ) = 1. Suppose a|bc, then ag | gb c. Because a g and gb are relatively prime, it follows that ag divides c. Conversely, suppose that ag divides c. Then b· ag divides bc, however gb is an integer, so clearly a divides a· gb = b· ag , that in turn divides c. Therefore a divides bc. ¢ ¡ ¢ ¡ ¢ ¡ ¢ ¡ 4. Evaluate with proof ab, p4 and a + b, p4 given that a, p2 = p and b, p3 = p2 where p is a prime. Let pα and pβ be the largest powers of p that divide a and b, respectively. Because gcd(a, p2 ) = p and gcd(b, p3 ) = p2 , it follows that min(α, 2) = 1 and min(β, 3) = 2. Thus α = 1 and β = 2. Therefore the largest power of p that divides ab is α + β = 3, and gcd(ab, p4 ) = pmin(3,4) = p3 . Similarly, the largest power of p that divides a + b is p, because if p2 were to divide a + b, then p2 would divide a + b + (−b) = a, and the largest power that divides a is p. Therefore gcd(a + b, p4 ) = pmin(1,4) = p. 5. Show that there exist non-negative integers x and y such that x2 − y 2 = n if and only if n is odd or is a multiple of 4. Show that there is exactly one such representation of n if and only if n = 1, 4, and odd prime, or four times a prime. Suppose that n is odd, then x = 12 (n + 1) and 12 (n − 1) are integers and ¶µ ¶ µ 1 1 x2 − y 2 = (x + y)(x − y) = (n + 1 + n − 1) (n + 1 − n + 1 = n. 2 2 If n is a multiple of 4, say n = 4N for some integer N , then let x = N + 1 and y = N − 1. Note that x2 − y 2 = (x + y)(x − y) = (N + 1 + N − 1)(N + 1 − N + 1) = 2N · 2 = n. Now suppose that x2 − y 2 = (x + y)(x − y) = n is even but not a multiple of 4. It follows that one of the factors x + y or x − y is even, and the other one is odd. But this is impossible, because their sum is equal to x + y + x − y = 2x, which is even. Suppose that n is odd but not equal to 1 or prime. Then n = ab for some odd integers a and b with 1 < a ≤ b < n. Let x = 12 (a + b) and y = 12 (b − a). Note that both x and y are integers and ¶µ ¶ µ 1 1 2 2 x − y = (x + y)(x − y) = (a + b + b − a) (a + b − b + a) = ab = n. 2 2 Moreover this pair (x, y) is different from the solution pair ( 12 (n + 1), 12 (n − 1)) shown before. Suppose that n is a multiple of 4, n = 4N for some integer N , but N is not equal to 1 or prime. Then N = ab for some integers a and b with 1 < a ≤ b < N . Let x = a + b and y = b − a. Note that x2 − y 2 = (x + y)(x − y) = (a + b + b − a)(a + b − b + a) = (2b) · (2a) = 4ab = n. Moreover this pair (x, y) is different from the solution pair (N + 1, N − 1) shown before. Finally, if n is equal to 1 or a prime, then n can only be written as a product of two positive integers as 1 · n. Thus we must have x − y = 1 and x + y = n, which yields the solution obtained before, and thus there is only one solution. Similarly, if n = 4N , where N is 1 or prime, then N can only be written as a product of two positive integers as 1 · N . If n = (x + y)(x − y) is a multiple of 4, then given that x + y + (x − y) = 2x is even, it follows that both factors must be even. The only way to write n = 4N as a product of two even numbers is 2 · 2N , thus x − y = 2 and x + y = 2N yields the only possible solution which was obtained before. 6. (Extra) Let a and b be positive integers such that 2 < b ≤ a. Prove that 2b − 1 does not divide 2a + 1. Suppose 2 < b ≤ a. Suppose that a = bq + r where q and r are nonnegative integers such that q ≥ 1 and 0 ≤ r < b. Performing long division yields ³ ´ 2a + 1 = (2b − 1) 2b(q−1)+r + 2b(q−2)+r + 2b(q−3) + · · · + 2b+r + 2r + (2r + 1). If 2b − 1 divides 2a + 1, then it follows that 2b − 1 divides 2r + 1. Thus 2b − 1 ≤ 2r + 1, but since r < b, it follows that r ≤ b − 1 and then 2b − 1 ≤ 2r + 1 ≤ 2b−1 + 1. Thus 2b−1 − 1 ≤ 2b−2 . But 2b−1 − 1 = 1 + 2 + 22 + 23 + · · · + 2b−2 > 2b−2 for b > 2, which is a contradiction. Thus 2b − 1 does not divide 2a + 1.