Mersenne numbers, two small results on

This entry presents two simple results on Mersenne numbers¹¹In this entry, the Mersenne numbers are indexed by the primes., namely that any two Mersenne numbers are relatively prime and that any prime dividing a Mersenne number $M_{p}$ is greater than $p$ . We prove something slightly stronger for both these results:

Theorem.

If $q$ is a prime such that $q\\!\\mid\\!M_{p}$ , then $p\\!\\mid\\!(q-1)$ .

Proof.

By definition of $q$ , we have $2^{p}\\equiv 1\\pmod{q}$ . Since $p$ is prime, this implies that $2$ has order $p$ in the multiplicative group $\\mathbb{Z}_{q}\\mathbin{\\setminus}\\{0\\}$ and, by Lagrange’s Theorem, it divides the order of this group (http://planetmath.org/Group), which is $q-1$ .∎

Theorem.

If $m$ and $n$ are relatively prime positive integers, then $2^{m}-1$ and $2^{n}-1$ are also relatively prime.

Proof.

Let $d:=\\gcd(2^{n}-1,2^{m}-1)$ . Since $d$ is odd, $2$ 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 $2$ divides both $m$ and $n$ : it is $1$ . Thus $2\\equiv 1\\pmod{d}$ and $d=1$ .∎

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 $p$ and the second easily implies that, if there were finitely many primes, every $M_{p}$ (since there would be as many Mersenne numbers as primes) is a prime power, which is clearly false (consider $M_{11}=23\\cdot 89$ ).

单词	MersenneNumbersTwoSmallResultsOn
释义	Mersenne numbers, two small results on This entry presents two simple results on Mersenne numbers¹¹In this entry, the Mersenne numbers are indexed by the primes., namely that any two Mersenne numbers are relatively prime and that any prime dividing a Mersenne number $M_{p}$ is greater than $p$ . We prove something slightly stronger for both these results: Theorem. If $q$ is a prime such that $q\\!\\mid\\!M_{p}$ , then $p\\!\\mid\\!(q-1)$ . Proof. By definition of $q$ , we have $2^{p}\\equiv 1\\pmod{q}$ . Since $p$ is prime, this implies that $2$ has order $p$ in the multiplicative group $\\mathbb{Z}_{q}\\mathbin{\\setminus}\\{0\\}$ and, by Lagrange’s Theorem, it divides the order of this group (http://planetmath.org/Group), which is $q-1$ .∎ Theorem. If $m$ and $n$ are relatively prime positive integers, then $2^{m}-1$ and $2^{n}-1$ are also relatively prime. Proof. Let $d:=\\gcd(2^{n}-1,2^{m}-1)$ . Since $d$ is odd, $2$ 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 $2$ divides both $m$ and $n$ : it is $1$ . Thus $2\\equiv 1\\pmod{d}$ and $d=1$ .∎ 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 $p$ and the second easily implies that, if there were finitely many primes, every $M_{p}$ (since there would be as many Mersenne numbers as primes) is a prime power, which is clearly false (consider $M_{11}=23\\cdot 89$ ).
随便看	Permutation permutation PermutationGroup permutation group PermutationMatrix permutation matrix PermutationModel permutation model PermutationNotation permutation notation PermutationOperator permutation operator PermutationPattern permutation pattern PermutationRepresentation permutation representation PerpendicularBisector perpendicular bisector PerpendicularityInEuclideanPlane perpendicularity in Euclidean plane PerrinPseudoprime Perrin pseudoprime PerrinSequence Perrin sequence PerronFamily