Factors of Mersenne Number M67

From ProofWiki
Jump to: navigation, search

Theorem

The Mersenne number $M_{67}$ has the factors:

$193 \, 707 \, 721$
$761 \, 838 \, 257 \, 287$


Proof

First we calculate $M_{67}$, which is $2^{67} - 1$:

$2^2 = 2 \times 2 = 4$


\(\displaystyle 2^4\) \(=\) \(\displaystyle 2^2 \times 2^2\)
\(\displaystyle \) \(=\) \(\displaystyle 4 \times 4\)
\(\displaystyle \) \(=\) \(\displaystyle 16\)


\(\displaystyle 2^8\) \(=\) \(\displaystyle 2^4 \times 2^4\)
\(\displaystyle \) \(=\) \(\displaystyle 16 \times 16\)
\(\displaystyle \) \(=\) \(\displaystyle 256\)


\(\displaystyle 2^{16}\) \(=\) \(\displaystyle 2^8 \times 2^8\)
\(\displaystyle \) \(=\) \(\displaystyle 256 \times 256\)
\(\displaystyle \) \(=\) \(\displaystyle 65 \, 536\)

as follows:

   256
 x 256
------
 1 536
12 800
51 200
------
65 536
------


\(\displaystyle 2^{32}\) \(=\) \(\displaystyle 2^{16} \times 2^{16}\)
\(\displaystyle \) \(=\) \(\displaystyle 65 \, 536 \times 65 \, 536\)
\(\displaystyle \) \(=\) \(\displaystyle 4 \, 924 \, 967 \, 296\)

as follows:

       65 536
     x 65 536
      -------
      393 216
    1 966 080
   32 768 000
  327 680 000
3 932 160 000
-------------
4 924 967 296
-------------


\(\displaystyle 2^{64}\) \(=\) \(\displaystyle 2^{32} \times 2^{32}\)
\(\displaystyle \) \(=\) \(\displaystyle 4 \, 924 \, 967 \, 296 \times 4 \, 924 \, 967 \, 296\)
\(\displaystyle \) \(=\) \(\displaystyle 18 \, 446 \, 744 \, 073 \, 709 \, 551 \, 616\)

as follows:

             4 294 967 296
           x 4 294 967 296
            --------------
            25 769 803 776
           386 547 056 640
           858 993 459 200
        30 064 771 072 000
       257 698 037 760 000
     3 865 470 566 400 000
    17 179 869 184 000 000
   386 547 056 640 000 000
   858 993 459 200 000 000
17 179 869 184 000 000 000
--------------------------
18 446 744 073 709 551 616
--------------------------
 1 233 444 664 532 221 1


\(\displaystyle 2^{67}\) \(=\) \(\displaystyle 2^{64} \times 2^3\)
\(\displaystyle \) \(=\) \(\displaystyle 18 \, 446 \, 744 \, 073 \, 709 \, 551 \, 616 \times 8\)
\(\displaystyle \) \(=\) \(\displaystyle 147 \, 573 \, 952 \, 589 \, 676 \, 412 \, 928\)

as follows:

 18 446 744 073 709 551 616
x                         8
---------------------------
147 573 952 589 676 412 928
---------------------------
 63 355 33  525  74 414 14


Subtracting $1$ to get $M_{67}$:

\(\displaystyle 2^{67} - 1\) \(=\) \(\displaystyle 147 \, 573 \, 952 \, 589 \, 676 \, 412 \, 928 - 1\)
\(\displaystyle \) \(=\) \(\displaystyle 147 \, 573 \, 952 \, 589 \, 676 \, 412 \, 927\)


Now to calculate $193 \, 707 \, 721 \times 761 \, 838 \, 257 \, 287$:

                193 707 721
          x 761 838 257 287
--------------------------
              1 355 954 047
             15 496 617 680
             38 741 544 200
          1 355 954 047 000
          9 685 386 050 000
         38 741 544 200 000
      1 549 661 768 000 000
      5 811 231 630 000 000
    154 966 176 800 000 000
    193 707 721 000 000 000
 11 622 463 260 000 000 000
135 595 404 700 000 000 000
---------------------------
147 573 952 589 676 412 927
---------------------------
  1 223 254 435 432 22  1

Thus:

\(\displaystyle 2^{67} - 1\) \(=\) \(\displaystyle 147 \, 573 \, 952 \, 589 \, 676 \, 412 \, 927\)
\(\displaystyle \) \(=\) \(\displaystyle 193 \, 707 \, 721 \times 761 \, 838 \, 257 \, 287\)

as we were to demonstrate.

$\blacksquare$


Historical Note

The Factors of Mersenne Number $M_{67}$ were demonstrated by Frank Nelson Cole in a famously dramatic presentation On The Factorization of Large Numbers to a meeting of the American Mathematical Society in October $1903$.

It is noted that Marin Mersenne had originally listed $M_{67}$ as one of the integers of the form $2^p - 1$ to be prime.

When called to give his lecture, he walked to the blackboard, and worked out the calculation, longhand, of $2^{67}$. Then he carefully subtracted $1$.

Moving to another area of the board, he then multiplied out $193, 707, 721 \times 761, 838, 257, 287$.

The numbers matched.

Cole returned to his seat to thunderous applause, having delivered the only lecture in history in which not a word was spoken.


When asked how long it had taken him to find these factors, he reportedly replied:

Three years of Sundays.


Sources