Exercise 2.4.3 (Composite repunits)

Proof. Note that, if $\underset{p}{\underset{⏟}{111\cdots 11}}$ is prime, then $p$ is prime (why?). The converse is false, as the following counterexamples show it.

a)

Applying the algorithm of fast exponentiation (and the Python program) given in problem 2, we obtain for $m=11111$, $$2^{m-1}\equiv 10536\not\equiv 1(\mathit{mod}m).$$

If $m$ was prime, we would obtain by Fermat’s theorem $2^{m-1}\equiv 1(\mathit{mod}m)$. This is false, so $m$ is composite.

b)

If $m=1111111$, then $$2^{m-1}\equiv 553891,$$

so $m$ is composite.

c)

If $m=11111111111$, then $$2^{m-1}\equiv 1496324899,$$

so $m$ is composite.

d)

If $m=1111111111111$, then $$2^{m-1}\equiv 1015669396877,$$

so $m$ is composite.

ipython:

     In [13]: m = 1111111111111
     
     In [14]: powermod(2,m-1,m)
     Out[14]: 1015669396877