Results 1 to 2 of 2

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


/mathhelpforum @mathhelpforum