Thread: Factors of Mersenne Numbers View Single Post
2002-09-14, 05:11   #2
toferc

Aug 2002

2·3·5 Posts

I am assuming that you read the proof on Chris Caldwell's Prime Pages. I'll quote it:

Quote:
 Let p and q be odd primes. If p divides Mq, then p = 1 (mod q) and p = +/-1 (mod 8). Below we give a proof and an example. Proof. If p divides Mq, then 2^q = 1 (mod p) and the order of 2 (mod p) divides the prime q, so it must be q. By Fermat's Little Theorem the order of 2 also divides p-1, so p-1 = 2kq. This gives 2^[(p-1)/2] = 2^qk = 1 (mod p) so 2 is a quadratic residue mod p and it follows p = +/-1 (mod 8), which completes the proof.
This proof is not very user-friendly unless you happen to know the number theory involved, I'll try to explain it a little better. Since I don't know who is going to read this, I'll try to be pretty basic, nobody should think I'm trying to insult their intelligence.

First off, in case you don't know, the statement "x = y (mod z)" is read "x is congruent to y modulo z". The equals sign should really have three horizontal lines in this notation, but we'll have to make do with two. The *meaning* of the statement is "When you divide x by z, the remainder is the same as the remainder when you divide y by z".

Examples:

20 = 2 (mod 3) --- 20 / 3 = 6 with remainder 2
21 = 0 (mod 3) --- 21 / 3 = 7 with remainder 0
22 = 25 (mod 3) --- 22 / 3 = 7 with remainder 1; 25 / 3 = 8 with remainder 1

Modulo arithmetic makes number theory a lot easier. We'll need to know that if

x = a (mod z) and
y = b (mod z), then
(x+y) = (a+b) (mod z).
Also, x*y = a*b (mod z).

Examples:

5 = 2 (mod 3) and
10 = 1 (mod 3) so
5 + 10 = 2 + 1 (mod 3), or 15 = 3 (mod 3.
5 * 10 = 2 * 1 (mod 3), or 50 = 2 (mod 3)

We'll need to know this too:

Definition: the order of a number x modulo another number y is the lowest power of x which is congruent to 1 modulo y. This number does not always exist, but when it does, it is at most equal to (y-1). In our case, the orders we will be looking at are known to exist.

Example:
The order of 2 mod 5 is 4, since 2^4 = 16 = 1 (mod 5)

The application of this is that if the order of x mod y is, say, 4, then x to any multiple of 4 is congruent to 1 modulo y. Also, *only* multiples of 4 have this property.

Example:
The order of 2 is 3 (mod 7)
2^3 = 8 = 1 (mod 7)
2^6 = 64 = 1 (mod 7)
2^1872459261927651 = (a huge number) = 1 (mod 7)

Usage note: The term "divides" as used in this proof means "divides evenly". "p divides q" means p = 0 (mod q)

On to the proof!

Quote:
 If p divides Mq, then 2^q = 1 (mod p)
We are about to look at things that are true for all numbers p which are factors of Mq.

p divides Mq -> Mq = 0 (mod p) -> Mq + 1 = 1 (mod p) ->
(2^q - 1) + 1 = 1 (mod p) -> 2^q = 1 (mod p)

Quote:
 and the order of 2 (mod p) divides the prime q, so it must be q.
We know that the order divides q because only numbers x which are even multiples of the order have the property 2^x = 1 (mod p). However, the only numbers which divide q are 1 and q. The order can't be 1, so it must be q.

Quote:
 By Fermat's Little Theorem the order of 2 also divides p-1
Let's just say that this is true. Trying to understand FLT is left to the reader ;)

Quote:
 so p-1 = 2kq
Remember that the order is q, so p-1 is some multiple of q, call it r.

p-1 = qr

Now... p is odd, and so is q, so r must be even. So r = 2k for some number k.

p-1 = qr = 2kq -> p = 2kq + 1

Which is the first half of our result.

Quote:
 This gives 2^[(p-1)/2] = 2^qk = 1 (mod p)
(p-1)/2 = 2kq/2 = kq, and 2 to any multiple of q is congruent to 1 mod p because q is the order of 2 (mod p)

Quote:
 so 2 is a quadratic residue mod p
Woops, I forgot to mention quadratic residues. Saying that 2 is a quadratic residue (mod p) means that at least one number x exists with the property x^2 = 2 (mod p).

Example:
2 is a quadratic residue (mod 7) because 3^2 = 9 = 2 (mod 7).

[Edit: ewmayer pointed out that my original explanation was incorrect. Here is his version:]

2^q = 1 (mod p)

Multiplying by 2, we have

2^(q+1) = 2 (mod p),

and since q odd, the exponent of 2 in the left-hand side is even,
i.e. the LHS is a perfect square.

Quote:
 and it follows p = +/-1 (mod 8), which completes the proof.
This follows from another theorem I won't be explaining here.
It is a useful fact because it allows you to eliminate any numbers which have remainder 3 or 5 when divided by 8. I should mention that
p = -1 (mod 8)
is another way of saying
p = 7 (mod 8).

I hope you made it to the bottom of the post without falling asleep, and I hope it helps![/b]