# Math Help - Help

1. ## Help

Could some please help me with the following problem,

1. Let n be an integer >1, and suppose that p= (2^n)+1 is a prime. Show that 3^((p-1)/2) + 1 is divisible by p.
I know that im supposed to prove that n is an even number first..but how? and after i ve done that, wat am i supposed to do?

2. if p= 2^n +1, n>1, 3^((p-1)/2) = -1 (mod p), show p is a prime.

thank you so much.

2. Originally Posted by felixmcgrady
1. Let n be an integer >1, and suppose that p= (2^n)+1 is a prime. Show that 3^((p-1)/2) + 1 is divisible by p.
I know that im supposed to prove that n is an even number first..but how? and after i ve done that, wat am i supposed to do?
We will show that $3$ is a primitive root modulo $p$. If $3$ is not a primitive root then $3$ must be a quadradic residue. This is because $3^{(p-1)/2}\equiv \pm 1(\bmod p)$. It cannot be $-1$ for that would force $p-1$ to be the order of $3$ since $p-1$ is a power of $2$. Therefore, there is $a$ such that $a^2 \equiv - 3(\bmod p)$. Let $x$ be the solution to $2x\equiv a - 1(\bmod p)$. Then, $(2x)^3 \equiv (a-1)^3 (\bmod p)$ and so $8x^3 \equiv (a^3+3a) - (1+3a^2)\equiv 8(\bmod p)$. Thus, we see that $x$ has order $3$. That gives us a contradiction because then $3$ divides $(p-1)$ which is impossible. Since $3$ is a primitive root it means $(3/p)=-1$ and so $3^{(p-1)/2}\equiv -1(\bmod p)$. We see that $p$ divides $3^{(p-1)/2}+1$.