Factorise the following integers into their prime factors:
(a) 9999 (b) 999 999
Hint: Consider $10^n− 1$.
(c) Repunits $R_n$ are given by.
$$ R_n = \underbrace{11 \ldots 1}_{n \text{ ones}} $$
For example $R_5 = \overbrace{11 \ldots 1}^{n \text{ ones}}$.
Factorize (i) $R_4$ (ii) $R_6$.
(a) We start with $9999=10^4-1= (10^2)^2 - 1^2$.
And so
$$ \begin{align} 9999 & \equiv 0 \pmod {9999} \\ \\ (10^2)^2 - 1^2 & \equiv 0 \pmod {9999} \\ \\ (10^2)^2 & \equiv 1^2 \pmod {9999} \end{align} $$
Here $10^2 \not \equiv \pm 1 \pmod {9999}$ and so $\gcd(10^2-1,9999)=99$ is a non-trivial factor of 9999.
Here 99 is easier to factor into $99 = 3^2 \times 11$.
And so $9999 = 3^2 \times 11 \times 101$.
(b) We start with $999999=10^6-1= (10^3)^2 - 1^2$.
And so
$$ \begin{align} 999999 & \equiv 0 \pmod {999999} \\ \\ (10^3)^2 - 1^2 & \equiv 0 \pmod {999999} \\ \\ (10^3)^2 & \equiv 1^2 \pmod {999999} \end{align}$$
Here $10^3 \not \equiv \pm 1 \pmod {999999}$ and so $\gcd(10^3-1, 999999) = 999$ is a non-trivial factor of 999999.
Here 999 is easier to factor into $999 = 3^3 \times 37$. Also $999999/999 = 1001 = 7 \times 11 \times 13$.
And so $999999 = 3^3 \times 7 \times 11 \times 13 \times 37$.
(c) (i) We start with $R_4 = 1111 = 9999 / 3^2 $, and using the above factorisation of 9999, we have
$$ R_4 = 1111 = 11 \times 101$$
(ii) We start with $R_6=111111 = 999999 / 3^2$, and using the above factorisation of 999999, we have
$$ R_6 = 111111 = 3 \times 7 \times 11 \times 13 \times 37 $$