Results 1 to 2 of 2

Thread: Help

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    39

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by felixmcgrady View Post
    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 $\displaystyle 3$ is a primitive root modulo $\displaystyle p$. If $\displaystyle 3$ is not a primitive root then $\displaystyle 3$ must be a quadradic residue. This is because $\displaystyle 3^{(p-1)/2}\equiv \pm 1(\bmod p)$. It cannot be $\displaystyle -1$ for that would force $\displaystyle p-1$ to be the order of $\displaystyle 3$ since $\displaystyle p-1$ is a power of $\displaystyle 2$. Therefore, there is $\displaystyle a$ such that $\displaystyle a^2 \equiv - 3(\bmod p)$. Let $\displaystyle x$ be the solution to $\displaystyle 2x\equiv a - 1(\bmod p)$. Then, $\displaystyle (2x)^3 \equiv (a-1)^3 (\bmod p)$ and so $\displaystyle 8x^3 \equiv (a^3+3a) - (1+3a^2)\equiv 8(\bmod p)$. Thus, we see that $\displaystyle x$ has order $\displaystyle 3$. That gives us a contradiction because then $\displaystyle 3$ divides $\displaystyle (p-1)$ which is impossible. Since $\displaystyle 3$ is a primitive root it means $\displaystyle (3/p)=-1$ and so $\displaystyle 3^{(p-1)/2}\equiv -1(\bmod p)$. We see that $\displaystyle p$ divides $\displaystyle 3^{(p-1)/2}+1$.
    Follow Math Help Forum on Facebook and Google+


/mathhelpforum @mathhelpforum