# Thread: A Couple Problems with Primes

1. ## A Couple Problems with Primes

1) Show that if a is a positive integer and $\displaystyle a^m + 1$ is an odd prime, then $\displaystyle m = 2^n$ for some nonnegative integer n.

2) Find all primes of the form $\displaystyle 2^2^n + 5$, where n is a nonnegative integer. (Its 2^(2^n), meaning the n is another exponent, I just couldn't get it to work with Latex.)

2. Originally Posted by Janu42
1) Show that if a is a positive integer and $\displaystyle a^m + 1$ is an odd prime, then $\displaystyle m = 2^n$ for some nonnegative integer n.

2) Find all primes of the form $\displaystyle 2^2^n + 5$, where n is a nonnegative integer. (Its 2^(2^n), meaning the n is another exponent, I just couldn't get it to work with Latex.)
Well I find these to be interesting problems and have not studied enough number theory to know how to approach them, nevertheless I see you've made over 100 posts so by this time should know that MHF is not a homework service; please provide some partial work/say where you got stuck.

To get a power tower in LaTeX use braces like this (double click to see source)

$\displaystyle 2^{2^n}+5$

3. Ah I think I've solved the first problem. For a odd, m can't be odd because then $\displaystyle a^m+1$ is even. For a even, we have $\displaystyle a \equiv -1 \pmod{ (a+1)}$ and for odd m we have $\displaystyle -1^m \equiv -1 \pmod{ (a+1)}$ thus $\displaystyle a^m+1$ will be divisible by $\displaystyle a+1$. Thus m must be even in all cases. Then suppose m is divisible by any odd prime p. We write m=kp. Then we can write $\displaystyle a^m = (a^k)^p$ which is just a positive integer to an odd power which we proved can't be one less than a prime above. Thus the only prime that can divide m is 2.

4. I think problem 2 is a trick question. Look at it mod 3, should see there are no such primes, except for n=0 giving the exponent odd, and the prime 7.

5. Originally Posted by undefined
Ah I think I've solved the first problem. For a odd, m can't be odd because then $\displaystyle a^m+1$ is even. For a even, we have $\displaystyle a \equiv -1 \pmod{ (a+1)}$ and for odd m we have $\displaystyle -1^m \equiv -1 \pmod{ (a+1)}$ thus $\displaystyle a^m+1$ will be divisible by $\displaystyle a+1$. Thus m must be even in all cases. Then suppose m is divisible by any odd prime p. We write m=kp. Then we can write $\displaystyle a^m = (a^k)^p$ which is just a positive integer to an odd power which we proved can't be one less than a prime above. Thus the only prime that can divide m is 2.
I think that the first few conclusions are not necessary for the proof. If some odd prime p divides m, such that m = kp, then $\displaystyle a^m + 1 = (a^k + 1)((a^k)^{p-1} - ..... - a^k + 1)$ If no odd prime divides m then it can be nothing but a power of 2.

6. I'm refering to problem 1). I will apply the following Algebraic identity: If $\displaystyle k\ge1$ is odd, then $\displaystyle x^k+1=(x+1)(x^{k-1}-x^{k-2}+\cdots-x+1)$.

Suppose that $\displaystyle m$ has an odd prime divisor $\displaystyle p$. Then write $\displaystyle m=pM$ for some integer $\displaystyle M$. Now $\displaystyle a^{m}+1=a^{pM}+1=(a^M+1)((a^M)^{p-1}-(a^M)^{p-2}+\cdots-a^M+1)$ by the identity, and we see that $\displaystyle a^M+1$ divides $\displaystyle a^{pM}+1$.
Since $\displaystyle a^M+1<a^{pM}+1$, it also follows that $\displaystyle a^{pM}+1$ is not prime.

Therefore, $\displaystyle m$ cannot have odd prime divisors, .i.e, $\displaystyle m=2^n$, where $\displaystyle n$ is a nonnegative integer.