PlanetMath: Mersenne numbers, two small results on

(more info)

Math for the people, by the people.

donor list - find out how

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (237)
Orphanage
Unclass'd
Unproven (550)
Corrections (54)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Copyright
About

Entry average rating: No information on entry rating

two small results on Mersenne numbers

(Result)

This entry presents two simple results on Mersenne numbers ¹, namely that any two Mersenne numbers are relatively prime and that any prime dividing a Mersenne number is greater than . We prove something slightly stronger for both these results:

Theorem 1 If is a prime such that $q\div M_p$ , then $p \div (q-1)$ .

Proof. By definition of

, we have $2^p \equiv 1 \pmod q$ . Since

is prime, this implies that

has order

in the multiplicative group $\mathbb{Z}_q\mathbin{\setminus}\{0\}$ and, by Lagrange's Theorem, it divides the order of this group, which is

. $\qedsymbol$

Theorem 2 If and are relatively prime positive integers, then and are also relatively prime.

Proof. Let $d := \gcd(2^n-1,2^m-1)$ . Since

is odd,

is a unit in $\mathbb{Z}_d$ and, since $2^n \equiv 1 \pmod d$ and $2^m \equiv 1 \pmod d$ , the order of

divides both

and

: it is

. Thus $2 \equiv 1 \pmod d$ and

. $\qedsymbol$

Note that these two facts can be easily converted into proofs of the infinity of primes: indeed, the first one constructs a prime bigger than any prime

and the second easily implies that, if there were finitely many primes, every

(since there would be as many Mersenne numbers as primes) is a prime power, which is clearly false (consider $M_{11} = 23\cdot89$ ).

Footnotes

...http://planetmath.org/encyclopedia/MersennePrime.html ¹: In this entry, the Mersenne numbers are indexed by the primes.

"two small results on Mersenne numbers" is owned by Cosmin.

(view preamble | get metadata)