Can $2^{1947}\times 5+1|2^{2^{1945}}+1$ be shown by hand?

109 Views Asked by At

A long tima ago, I read in a book that it would be easy to show that the number

$2^{1947}\times 5+1$ divides the Fermat number $2^{2^{1945}}+1$

I do not know, if the author meant, that it can be done by hand, or that it can be quickly checked with a computer. I have done it with PARI/GP, and this is actually the case.

So, I wonder

Can $2^{1947}\times 5+1\ |\ 2^{2^{1945}}+1$ be shown by hand ?

If this would be possible, it could be proven easily that $2^{1947}\times 5+1$ is prime by hand, and this could work for even larger examples.

1

There are 1 best solutions below

0
On

I think the author meant that it could be quickly checked with a computer. Mind you, even this is a nontrivial statement, as $m=5\times2^{1947}+1$ has 587 digits, and $F_{1945}=2^{2^{1945}}+1$ has too many digits to store in any computer. Sierpinski explains how to do it on pages 77 to 78 of his book, A Selection of Problems in the Theory of Numbers:

You define a sequence $r_1,r_2,\dots$ by $r_1=2^2$, $r_{k+1}$ is $r_k^2$ reduced modulo $m$. You prove (by induction, but it's a standard property of modular arithmetic) that $m$ divides $2^{2^k}-r_k$ for $k=1,2,\dots$. Letting $k=1945$, you get that $m$ divides $F_{1945}-r_{1945}-1$. So all we have to do is to prove that $m$ divides $r_{1945}+1$.

Now to calculate $r_{1945}$, we have to square 1944 numbers, each having not more than 587 digits, and then divide those squares, each having not more than 1175 digits, by $m$, which has 587 digits. That was within the capabilities of a computer in 1964, when Sierpinski published his book, and for all I know it's within the capabilities of a smartphone, or maybe even a wristwatch, today.