Is 3 always a primitive root for mersenne primes?

[juergen]

Hello,

the subject sais it all.

Is 3 always a primitive root for primes of the form 2^x-1 for x>2?
In other words:

If 2^x-1 is prime is then

Ord 3 (mod 2^x-1) always 2^x-2 = 2(2^(x-1)-1)?

I checked this up to 127, okay thats not a lot, but I guess that this is really right and I wonder if there is already a proof for that.

kind regards Jürgen

[abiessu]

Actually, it's that 'ord 3 (2^p-1) divides 2^p-2'. But there's an even better congruence:

3^(2^(p-1)) = -3 (mod 2^p-1).

[akruppa]

Originally Posted by abiessu

Actually, it's that 'ord 3 (2^p-1) divides 2^p-2'. But there's an even better congruence:

3^(2^(p-1)) = -3 (mod 2^p-1).

The first follows from Lagrange's theorem. The second follows from the fact that 3 is a quadratic non-residue (mod 2^p-1) for Mersenne primes with odd p. Neither answers the original question.

Alex

[abiessu]

Sorry, I meant it like this:

'yes, 2^p-2 is always an order of 3 mod 2^p-1 given the conditions you've described, and it just so happens that...'

I got a little carried away, new to the forum and all...

But... umm... doesn't that answer the original?

[akruppa]

The order of an element a is the smallest positive integer n so that a^n == 1. You showed that 2^p-2 is a multiple of the order of 3 (which is what Lagrange's theorem states, the order of an element divides the order of the group), but not that 2^p-2 is equal to the order of 3.

Alex

[R.D. Silverman]

Originally Posted by akruppa

The order of an element a is the smallest positive integer n so that a^n == 1. You showed that 2^p-2 is a multiple of the order of 3 (which is what Lagrange's theorem states, the order of an element divides the order of the group), but not that 2^p-2 is equal to the order of 3.

Alex

Disproof by counter-example.

A short search reveals that 3^910 = 1 mod (2^13-1).

Thus, 3 is not primitive.

What compels people to make such speculations without even a minimal
attempt at some numerical verification?

[R.D. Silverman]

Originally Posted by R.D. Silverman

Disproof by counter-example.

A short search reveals that 3^910 = 1 mod (2^13-1).

Thus, 3 is not primitive.

What compels people to make such speculations without even a minimal
attempt at some numerical verification?

Another example: Let P = 2^61-1, then 3^( (P-1)/3) = 1 mod P.

Enuf said?????

[Primeinator]

Please pardon me, I'm only a sophomore in an american high school. Could someone please explain to me what a primitive root is? (I know what square roots and cubic roots and 4th roots, etc etc are).

[philmoore]

Suppose p is prime. Then the congruence classes 1, 2, 3, ..., p-1 form a group under multiplication. (Example: p = 11, then 2*7 = 14 = 3 mod 11.) A primitive root is a congruence class that generates all the other congruence classes when you take its powers. So the consecutive powers of 2 mod 11 are: 2, 4, 8, 5, 10, 9, 7, 3, 6, and 1, so 2 is a primitive root mod 11. On the other hand, the powers of 3 mod 11 are: 3, 9, 3, 4, 1, 3, 9, 3, 4, 1, etc., so 3 is not a primitive root.

[abiessu]

Originally Posted by R.D. Silverman

Disproof by counter-example.

A short search reveals that 3^910 = 1 mod (2^13-1).

Thus, 3 is not primitive.

What compels people to make such speculations without even a minimal
attempt at some numerical verification?

(No, I'm not saying that you mis-used terms.)

I think I missed the point the original poster was aiming at. My apologies.