Problem set 3 Problem 5. Here is a long run of composite numbers 114,115,116,117,118,119,120,121,122,123,124,125,126 Prove that there exist arbitrarily long runs of composite numbers. Consider numbers a little bigger than n! where n!=m:(n-1)…3·2.1 Solution. Let k be some natural number such that 1<k< n. We know k I(n!+ k) because k n! and k k. Thus, the numbers n! +2, n! +3, n! +4,.. n!+n are all composite This is a run of n-1 consecutive composite numbers. Because we can choose n arbitrarily, we know arbitrarily long runs of composite numbers exist Problem 6. Here is a very, very fun game. Initially, there is a blackboard with the numbers 1309 and 1729 written on it. Now you and I take turns; you go first. On each player's turn, he or she must write a new positive integer on the board that is the difference of two numbers that are already there the first person who can not create a new number loses the ga ame For example, your first move must be 1729- 1309= 420. Then I could play either 1309-420=889or1729-420=1309, and so forth (a) Prove every number written on the board is a multiple of 7 less than or equal to 1729 Solution. We use induction. Let P(n) be the proposition that after n moves, every number on the board is a positive linear combination of 1729 and 1390 Base case. P(O) is true because 1729 and 1390 are trivial linear combinations of 1729 Inductive step. Assume that after n moves, every number on the board is a positive linear combination of 1729 and 1390. The next number written on the board is also a positive linear combination because: The rules require the number to be positive The new number must be a difference of two numbers already on the board, which are themselves linear combinations of 1729 and 1390 by assumption And a difference of linear combinations is another linear combination By induction, every number on the board is a positive linear combination of 1729 and 1390. And every positive linear combination of 1729 and 1390 is a multiple of gcd(1729,1390)=7 (b) Prove that every positive multiple of 7 less than or equal to 1729 is on the board at the end of the game Solution. Let a be the smallest number on the board at the end of the game. B the Division Algorithm, there exist integers q and r such that 1729=qa+r whereProblem Set 3 5 Problem 5. Here is a long run of composite numbers: 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126 Prove that there exist arbitrarily long runs of composite numbers. Consider numbers a little bigger than n! where n! = n · (n − 1) 3 2 1 · · · · · . Solution. Let k be some natural number such that 1 < k ≤ n. We know k | (n! + k) because k | n! and k k| . Thus, the numbers n!+2, n!+3, n!+4, . . . , n!+n are all composite. This is a run of n−1 consecutive composite numbers. Because we can choose n arbitrarily, we know arbitrarily long runs of composite numbers exist. Problem 6. Here is a very, very fun game. Initially, there is a blackboard with the numbers 1309 and 1729 written on it. Now you and I take turns; you go first. On each player’s turn, he or she must write a new positive integer on the board that is the difference of two numbers that are already there. The first person who can not create a new number loses the game. For example, your first move must be 1729 − 1309 = 420. Then I could play either 1309 − 420 = 889 or 1729 − 420 = 1309, and so forth. (a) Prove every number written on the board is a multiple of 7 less than or equal to 1729. Solution. We use induction. Let P(n) be the proposition that after n moves, every number on the board is a positive linear combination of 1729 and 1390. Base case. P(0) is true because 1729 and 1390 are trivial linear combinations of 1729 and 1390. Inductive step. Assume that after n moves, every number on the board is a positive linear combination of 1729 and 1390. The next number written on the board is also a positive linear combination, because: • The rules require the number to be positive. • The new number must be a difference of two numbers already on the board, which are themselves linear combinations of 1729 and 1390 by assumption. And a difference of linear combinations is another linear combination. By induction, every number on the board is a positive linear combination of 1729 and 1390. And every positive linear combination of 1729 and 1390 is a multiple of gcd(1729, 1390) = 7. (b) Prove that every positive multiple of 7 less than or equal to 1729 is on the board at the end of the game. Solution. Let x be the smallest number on the board at the end of the game. By the Division Algorithm, there exist integers q and r such that 1729 = q · x + r where