Problem Set 3 0<r< a. When no more moves are possible 1729- a must already be on the board, and thus so must 1729-2. c,.. 1729-(q-1)a. However, 1729-q=rcan not be on the board, since r r and r is defined to be the smallest number there The only explanation is that r=0, which implies that c 1729. By a symmetric argument, 3| 1390. Therefore, a is a common divisor of c and y. The only common divisors of 1729 and 1390 are 1 and 7, and r can not be 1 by the preceding problem part. Therefore, 7 is on the board at the end of the game. Since no more moves are possible, 1729-7, 1729-2.7,..., 7,0 must all be on the board as well. So every positive multiple of of 7 less than or equal to 1729 is on the board at the end of the me (c) Who wins? Solution. There are 1729/7= 247 numbers on the board at the end of the game Thus, there were 247-2= 245 moves. Since you go first, you also get the last move and win the game Problem 7. Prove the following theorem Theorem. If gcd(a, b)=l, then gcd(a+b, a-b)=l or 2 Solution. Since gcd(a, b)=l, there exist integers s and t such that +t·b Now there is a linear combination of a+b and a-b equal to 2 (s+t)·(a+b)+(s-t)·(a-b)=2(sa+t·b)=2 Thus gcd(a+b, a-b) is at most 2, which implies it is equal to 1 or 26 Problem Set 3 0 ≤ r < x. When no more moves are possible, 1729 − x must already be on the board, and thus so must 1729 − 2x, . . . 1729 − (q − 1)x. However, 1729 − qx = r can not be on the board, since r < x and x is defined to be the smallest number there. The only explanation is that r = 0, which implies that x | 1729. By a symmmetric argument, x | 1390. Therefore, x is a common divisor of x and y. The only common divisors of 1729 and 1390 are 1 and 7, and x can not be 1 by the preceding problem part. Therefore, 7 is on the board at the end of the game. Since no more moves are possible, 1729 − 7, 1729 − 2 7· , . . . , 7, 0 must all be on the board as well. So every positive multiple of of 7 less than or equal to 1729 is on the board at the end of the game. (c) Who wins? Solution. There are 1729/7 = 247 numbers on the board at the end of the game. Thus, there were 247 − 2 = 245 moves. Since you go first, you also get the last move and win the game. Problem 7. Prove the following theorem. Theorem. If gcd(a, b) = 1, then gcd(a + b, a − b) = 1 or 2. Solution. Since gcd(a, b) = 1, there exist integers s and t such that: s · a + t · b = 1 Now there is a linear combination of a + b and a − b equal to 2: (s + t) · (a + b) + (s − t) · (a − b) = 2(s · a + t · b) = 2 Thus gcd(a + b, a − b) is at most 2, which implies it is equal to 1 or 2