Midterm 1 Bonus

You can submit as many of the problems below as you desire to be graded for extra credit on the first exam. Your solutions must be submitted by the **beginning** of class on Wednesday, February 25. Each problem is worth up to 1 point on your exam, but no partial credit is given. You are welcomed to talk with me about the problem or consult your text and notes, but you should not discuss these problems with your friends, nor should you look at other sources (books, the internet) for answers.

- Let
*a,m*and*n*be positive integers with $a>1$. Prove that $a^m-1 \mid a^n -1$ if and only if $m \mid n$. - Let
*a*and*n*be positive integers with $n>1$. Prove that, if $a^n-1$ is prime, then $a=2$ and*n*is prime. - Let
*a*and*n*be positive integers with $a>1$. Prove that, if $a^n+1$ is prime, then*a*is even and*n*is a power of 2. - Prove that in any eight composite positive integers not exceeding 360, at least two are not relatively prime.
- Let
*p*be an odd prime number. Prove that the numerator of $\frac{1}{1}+\frac{1}{2} + \cdots + \frac{1}{p-1}$ (when expressed as a single fraction) is divisible by*p*. - Let
*m*be a positive integer such that $6m+1, 12m+1$ and $18m+1$ are prime. Prove that $n = (6m+1)(12m+1)(18m+1)$ is a Carmichael number. - 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.

- 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