TAOCP 4.5.4 Exercise 5
Let N=11111.
Section 4.5.4: Factoring into Primes
Exercise 5. [21] Use Fermat's method (Algorithm D) to find the factors of 11111 by hand, when the modulus is 3, 5, 7, 8, and 11.
Verified: no
Solve time: 7m10s
Solution
Let
$$ N=11111. $$
Fermat's method seeks integers $x\ge \lceil\sqrt N\rceil$ and $y\ge0$ such that
$$ N=x^2-y^2=(x-y)(x+y). $$
Define
$$ Q=x^2-N. $$
We search for $x$ such that $Q$ is a perfect square. Algorithm D accelerates the search by requiring $Q$ to be a quadratic residue modulo a chosen modulus $m$.
Since
$$ 105^2=11025<11111<11236=106^2, $$
the search begins at $x=106$.
The actual factorization of $11111$ is
$$ 11111=41\cdot271, $$
hence the corresponding Fermat representation is
$$ x=\frac{41+271}{2}=156,\qquad y=\frac{271-41}{2}=115, $$
and indeed
$$ 156^2-11111=24336-11111=13225=115^2. $$
Thus the first successful value is $x=156$.
We now determine the admissible residue classes for each modulus and then locate the solution.
Modulus $3$
Since
$$ 11111\equiv2\pmod3, $$
we have
$$ Q\equiv x^2-2\pmod3. $$
The quadratic residues modulo $3$ are $0$ and $1$.
If $x\equiv0\pmod3$, then
$$ Q\equiv0-2\equiv1\pmod3, $$
which is a quadratic residue.
If $x\equiv1$ or $2\pmod3$, then
$$ Q\equiv1-2\equiv2\pmod3, $$
which is not a quadratic residue.
Hence the admissible class is
$$ x\equiv0\pmod3. $$
Starting from $106$, the admissible values are
$$ 108,111,114,\ldots,156. $$
At
$$ x=156 $$
we obtain
$$ Q=156^2-11111=13225=115^2, $$
so
$$ 11111=(156-115)(156+115)=41\cdot271. $$
Modulus $5$
Since
$$ 11111\equiv1\pmod5, $$
we have
$$ Q\equiv x^2-1\pmod5. $$
The quadratic residues modulo $5$ are
$$ 0,1,4. $$
A computation gives
$$ \begin{array}{c|c} x\bmod5 & x^2-1\bmod5\ \hline 0 & 4\ 1 & 0\ 2 & 3\ 3 & 3\ 4 & 0 \end{array} $$
Therefore the admissible classes are
$$ x\equiv0,\pm1\pmod5. $$
Since
$$ 156\equiv1\pmod5, $$
the solution $x=156$ survives the sieve, and
$$ 156^2-11111=115^2. $$
Hence
$$ 11111=41\cdot271. $$
Modulus $7$
Since
$$ 11111\equiv2\pmod7, $$
we have
$$ Q\equiv x^2-2\pmod7. $$
The quadratic residues modulo $7$ are
$$ 0,1,2,4. $$
We require $x^2-2$ also to be a quadratic residue:
$$ \begin{array}{c|c} x^2\bmod7 & x^2-2\bmod7\ \hline 0 & 5\ 1 & 6\ 2 & 0\ 4 & 2 \end{array} $$
Only the last two entries are quadratic residues. Thus
$$ x^2\equiv2 \text{ or }4\pmod7. $$
Since
$$ x^2\equiv2 \iff x\equiv3,4\pmod7, $$
and
$$ x^2\equiv4 \iff x\equiv2,5\pmod7, $$
the admissible classes are
$$ x\equiv2,3,4,5\pmod7. $$
Because
$$ 156\equiv2\pmod7, $$
the solution is admissible, and again
$$ 156^2-11111=115^2. $$
Modulus $8$
Since
$$ 11111\equiv7\pmod8, $$
we have
$$ Q\equiv x^2-7\pmod8. $$
The quadratic residues modulo $8$ are
$$ 0,1,4. $$
Checking the possibilities,
$$ \begin{array}{c|c} x^2\bmod8 & x^2-7\bmod8\ \hline 0 & 1\ 1 & 2\ 4 & 5 \end{array} $$
Only $1$ is a quadratic residue modulo $8$. Therefore
$$ x^2\equiv0\pmod8, $$
which implies
$$ x\equiv0\pmod4. $$
Thus only multiples of $4$ need be examined.
Since
$$ 156\equiv0\pmod4, $$
the solution is admissible and yields
$$ 156^2-11111=115^2. $$
Modulus $11$
Since
$$ 11111\equiv1\pmod{11}, $$
we have
$$ Q\equiv x^2-1\pmod{11}. $$
The quadratic residues modulo $11$ are
$$ 0,1,3,4,5,9. $$
We compute
$$ \begin{array}{c|c} x^2\bmod11 & x^2-1\bmod11\ \hline 0 & 10\ 1 & 0\ 3 & 2\ 4 & 3\ 5 & 4\ 9 & 8 \end{array} $$
Hence $x^2-1$ is a quadratic residue only when
$$ x^2\equiv1,4,5\pmod{11}. $$
Therefore
$$ x\equiv\pm1,\pm2,\pm4,\pm5\pmod{11} $$
are admissible, while
$$ x\equiv0,\pm3\pmod{11} $$
are excluded.
Since
$$ 156\equiv2\pmod{11}, $$
the solution survives the sieve, and
$$ 156^2-11111=115^2. $$
Summary
The admissible residue classes are
$$ \begin{array}{c|c} m & \text{admissible }x\pmod m\ \hline 3 & 0\ 5 & 0,\pm1\ 7 & 2,3,4,5\ 8 & 0\pmod4\ 11 & \pm1,\pm2,\pm4,\pm5 \end{array} $$
For each modulus, the search eventually reaches
$$ x=156, $$
for which
$$ 156^2-11111=115^2. $$
Hence
$$ 11111=(156-115)(156+115)=41\cdot271. $$
Therefore
$$ \boxed{11111=41\cdot271}. $$