Bonus for Test 1

Each of the following problems is worth 1 point if you answer it completely correctly. Partially correct answers will receive zero credit. These extra point problems must be turned in to me by 11am on Wednesday, October 1, if you would like to receive credit for them.

• Prove that every integer greater than 11 can be expressed as the sum of two composite numbers.
• Let p be an odd prime number. Prove that the numerator of $1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{p-1}$ (when expressed as a single fraction with denominator $(p-1)!$) is divisible by p.
• Let $a,b \in \mathbb{Z}$ with $a,b>0$ and $(a,b)=1$. Prove that there are infinitely many composites of the form $a+kb$, where k ranges of all non-negative integers.
• Two integers m and n between 2 and 100 inclusive are chosen. The sum of the two integers is given to Sam, and the product of the two integers is given to Pam. Both Sam and Pam are brilliant mathematicians who make perfect logical deductions whenever there is a logical deduction to be made. After they look at their numbers for a while, Pam says "I don't know your sum, Sam." Sam responds "I knew you didn't know my sum, Pam." Pam thinks for a moment and then says, with a smile, "Now I know your sum." Sam's response is "Now I know your product." What are m and n?
• In an infinite prison each inmate gets his or her own cell; these cells are numbered by the positive integers: 1, 2, 3, … The warden of the prison can control whether each cell is locked or unlocked by the push of a button; his system works so well that he can even decide precisely which of his infinitely many cells to lock or unlock at a given time. Drunk with power, the warden decides to play a game. With each prisoner in his or her respective cell, he locks all the doors. He then "turns the key" on each of the doors which are a multiple of 2 (where by "turns the key" i mean he unlocks the doors which were locked, and locks the doors which were unlocked). Next he turns the key on each of the cells which are a multiple of 3, then he turns the key on each of the cells which are a multiple of 4, and so on.
  • The warden will play this game forever, but for any given prisoner the game eventually stops. Describe at which step of the game the prisoner in cell n knows that the warden will no longer "turn the key" on cell number n.
  • Find exactly which prisoners are left with an open door when the game is through for them. Be sure to give a full justification for your answer.
• Let n be an integer greater than 1. Prove that the sum of all positive integers k with $1 \leq k \leq n$ and $(k,n)=1$ is $\frac{1}{2}n\phi(n)$.