Mathematical Recreations and Essays
Mersenne's Numbers
Excerpts
Mersenne's Numbers
It is evident that, if $p$ is not a prime, then $N$ is composite, and two or more of its factors can be written down by inspection.
Mersenne's Numbers
We know by Fermat’s Theorem that if $x + 1$ is a prime then $2^x-1$ is divisible by $x + 1$.
Mersenne's Numbers
The number $N$ when expressed in the binary scale, consists of $1$ repeated $p$ times.
Mersenne's Numbers
that, if $4n + 3$ and $8n + 7$ are primes, then $2^{4n+3}-1 \equiv 0 \pmod{8n + 7}$.
Mersenne's Numbers
Comme de $25$, qui est un quarré, ôtez $2$; le reste $23$ mesurera la 11e puissance $-1$;
Mersenne's Numbers
but the riddle as to how it was discovered is still, after nearly 250 years, unsolved.
Mersenne's Numbers
Qui vndecim alios repererit, nouerit se analysim omnem, quae fuerit hactenus, superasse:
Equations
Mersenne's Numbers
N=2^p - 1N, the number used in this chapter, is defined as 2 to the power p minus 1, for a prime p.
Mersenne's Numbers
2^{4n+3}-1 \equiv 0 \pmod{8n + 7}If 4n+3 and 8n+7 are both prime, then 2^(4n+3) - 1 is divisible by 8n+7, so 8n+7 is a factor of the Mersenne number for p = 4n+3 (Euler's proposition, proved by Lagrange in 1775).
Mersenne's Numbers
N = n^2 + a = (n + b)^2 - (b^2 + 2bn - a)Since N can be written as n squared plus a, it can also be written as the difference of the squares (n+b)^2 and (b^2 + 2bn - a), which is the starting point for the indeterminate-equation method.
Mersenne's Numbers
x^2 = (2py + H)^2 - 4(K - y)An indeterminate equation in integers x and y whose integral solutions with y < K give values of u and v, and hence factors of N.
Mersenne's Numbers
4s + t = \alpha + 8pxThe first of two linked conditions obtained from writing (2pt+1)(8ps+1) = 2^p - 1, giving a second indeterminate equation for the factor parameters s and t.
Mersenne's Numbers
st = \beta - xThe second of the two linked conditions for the factor parameters s and t, with x not greater than beta.
Mersenne's Numbers
2^{2pt}-1 \equiv 0By Fermat's Theorem, when 2pt+1 is prime, 2 raised to the power 2pt minus 1 is divisible by 2pt+1.
Mersenne's Numbers
(2^p-1)(1+2^p+2^{2p}+\dotsb+2^{(2t-1)p}) \equiv 0Modulo the prime 2pt+1, the product of 2^p-1 and the geometric sum of powers of 2^p is zero, so a factor of 2^p-1 is found when the second factor is prime to 2pt+1.
Mersenne's Numbers
(2^p-1)(2^p + 1)\equiv 0With t = 1 and 2p+1 prime, the product (2^p - 1)(2^p + 1) vanishes modulo 2p+1, the basis of Euler's 1732 theorem.
Mersenne's Numbers
2^p\equiv1Modulo 2p+1, 2^p is congruent to 1 when 2^p + 1 is prime to 2p+1, which holds for p = 4m + 3, so 2p+1 divides N.
Mersenne's Numbers
2^{p+y} \equiv zThe Canon Arithmeticus method: a prime q and exponents y and z are sought with 2 to the power p+y congruent to z modulo q.
Mersenne's Numbers
2^y (2^p - 1) \equiv 0Combining the two congruences modulo q gives 2^y times (2^p - 1) congruent to zero, from which the book concludes that q divides N.
Mersenne's Numbers
2^p = 1The book concludes that 2^p = 1 from the preceding congruences, so q is a divisor of N. The printed sign appears to be a transcription loss: the argument requires the congruence 2^p ≡ 1 (mod q), not an equality, which is how it is read here.
Mersenne's Numbers
2^{u-v} \equiv 1If the remainders of powers of 2 agree for exponents u and v modulo a prime q, then 2 to the power u minus v is congruent to 1 modulo q.
Mersenne's Numbers
2^u \equiv 2^vIf the remainders of 2^x modulo a prime q agree for x = u and x = v, then 2^u is congruent to 2^v modulo q.
Mersenne's Numbers
2047 = 23 \times 89The Mersenne number for p = 11 factors as 23 times 89, so it is composite.
Mersenne's Numbers
137438953471 = 223 \times 616318177The Mersenne number for p = 37 factors as 223 times 616318177, so it is composite; the factorization was given by Fermat.
Mersenne's Numbers
8i \pm 1Any prime factor of a Mersenne number must be of one of the forms 8i plus or minus 1, since N is of the form 2A^2 minus B^2 with A even and B odd.
Problems
No exercises in this chapter.