# Thread: A Couple Problems with Primes

1. ## A Couple Problems with Primes

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

2) Find all primes of the form $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 $a^m + 1$ is an odd prime, then $m = 2^n$ for some nonnegative integer n.

2) Find all primes of the form $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)

$2^{2^n}+5$

3. Ah I think I've solved the first problem. For a odd, m can't be odd because then $a^m+1$ is even. For a even, we have $a \equiv -1 \pmod{ (a+1)}$ and for odd m we have $-1^m \equiv -1 \pmod{ (a+1)}$ thus $a^m+1$ will be divisible by $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 $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 $a^m+1$ is even. For a even, we have $a \equiv -1 \pmod{ (a+1)}$ and for odd m we have $-1^m \equiv -1 \pmod{ (a+1)}$ thus $a^m+1$ will be divisible by $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 $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 $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 $k\ge1$ is odd, then $x^k+1=(x+1)(x^{k-1}-x^{k-2}+\cdots-x+1)$.

Suppose that $m$ has an odd prime divisor $p$. Then write $m=pM$ for some integer $M$. Now $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 $a^M+1$ divides $a^{pM}+1$.
Since $a^M+1, it also follows that $a^{pM}+1$ is not prime.

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