Exercise 2.4.16 (Pollard $p-1\ $ method)

Proof.

a)

We show first that $2^{n!}-1\mid 2^{(n+1)!}-1$. $$\begin{array}{llll}\hfill 2^{(n+1)!}-1& ={\left(2^{n!}\right)}^{n+1}-1& \hfill & \\ \hfill & =(2^{n!}-1)\underset{i=0}{\overset{n}{\sum }}{2}^{n!i}.& \hfill & \end{array}$$

This shows that

$$2^{n!}-1\mid 2^{(n+1)!}-1.$$

From $(2^{n!}-1)\wedge m\mid 2^{n!}-1\mid 2^{(n+1)!}-1$ and $(2^{n!}-1)\wedge m\mid m$, the characterization of the gcd shows that

$$(2^{n!}-1)\wedge m\mid (2^{(n+1)!}-1)\wedge m,$$

do $d_n\mid d_{n+1}.$

b)

Assume that $p-1\mid n!$, where $p$ is a prime factor of an odd integer $m$. By Problem 15, where we take $Q=n!$, we obtain that $(2^{n!}-1)\wedge m>1$, that is $d_n>1$. This gives a proper divisor $d_n$ of $m$.

c)

The following code in Sage

     sage: m = 403
     sage: for n in range(1,9):
     ....:     dn = 2^factorial(n) - 1
     ....:     print(n, ’=>’,gcd(dn,m))
     ....:
     (1, ’=>’, 1)
     (2, ’=>’, 1)
     (3, ’=>’, 1)
     (4, ’=>’, 13)
     (5, ’=>’, 403)
     (6, ’=>’, 403)
     (7, ’=>’, 403)
     (8, ’=>’, 403)

Explicitly:

$d_3=2^6-1=63$, and $d_3\wedge 403=1$,

$d_4=2^{24}-1=16777215$, and $d_4\wedge 403=13$,

$d_5=2^{120}-1=1329227995784915872903807060280344575$, and $d_5\wedge 403=403$.

Thus a proper divisor of $403$ is $d_4\wedge 13$ ( $403=13\times 31)$. The least $n$ that gives a factor is $n=4$, and the least $n$ for which $d_n=403$ is $n=5$.

( $2^{10!}-1$ has more than $10^6$ digits! To avoid big numbers, see Problem 17.) □