# Prime factorization of $\frac{100^{69}-1}{99}$?

I'm certain that I'm not the first person to ask this question, but I'm wondering what techniques can be used to attempt to find the prime factorization of $$m=\underbrace{696969\cdots 69}_{69\text{ times}}$$

I know that $$m=69\cdot\underbrace{101010\cdots 101}_{68\text{ times} }=3\cdot 23\cdot \sum\limits_{k=0}^{68}100^k=3\cdot 23\cdot\frac{100^{69}-1}{99}$$ From there, I'm not aware of any good way to find the prime factors $$\frac{100^{69}-1}{99}$$ Are there any methods that might lend themselves to factoring that number other than simply using a computer and trial and error?

• You need to put your TeX inside dollar signs Commented Oct 9, 2020 at 20:20
• I made an attempt to reformat your post. Please review what I did to confirm that I didn't introduce any errors.
– lulu
Commented Oct 9, 2020 at 20:24
• WolframAlpha hints that it might not be entirely trivial. A few of the factors you can probably find by hand, but it's mostly beyond what one can expect to do without computers. Commented Oct 9, 2020 at 20:30
• There may be some restrictions on potential prime factors $p$ satisfying $100^{69}\equiv1\pmod p$ Commented Oct 9, 2020 at 20:36
• Here we can exploit "algebraic factorizations" of cyclotomic polynomials, see the introduction in the monograph by Brillhart et al. mentioned here. Commented Oct 9, 2020 at 21:17

Most useful information comes from factorizing the polynomial $$F(x) = \frac{x^{138} - 1}{x^2 - 1}$$, which can be easily expressed as a product of cyclotomic polynomials:

$$F(x) = \phi_3(x)\phi_3(-x)\phi_{23}(x)\phi_{23}(-x)\phi_{69}(x)\phi_{69}(-x),$$ where $$\phi_n(x)$$ is the $$n$$-th cyclotomic polynomial.

Thus it suffices to factorize the numbers $$\phi_3(\pm 10)$$, $$\phi_{23}(\pm 10)$$, $$\phi_{69}(\pm 10)$$. I don't think there are any smart methods to do that, other than calculating the numbers and passing them to a factorization algorithm. This perhaps can be seen from the results: $$\begin{eqnarray} \phi_3(10) &=& 3 \times 37\\ \phi_3(-10) &=& 7 \times 13\\ \phi_{23}(10) &=& 11111111111111111111111\\ \phi_{23}(-10) &=& 47 \times 139 \times 2531 \times 549797184491917\\ \phi_{69}(10) &=& 277 \times 203864078068831 \times 1595352086329224644348978893\\ \phi_{69}(-10) &=& 31051 \times 143574021480139 \times 24649445347649059192745899.\\ \end{eqnarray}$$

In general we have

$$x^n - 1 = \prod_{d \mid n} \Phi_d(x)$$

where $$\Phi_d(x)$$ are the cyclotomic polynomials. This is the complete irreducible factorization of $$x^n - 1$$. Since $$100^{69} = 10^{138}$$ and $$138 = 2 \cdot 3 \cdot 23$$ this gives

$$10^{138} - 1 = \Phi_1(10) \Phi_2(10) \Phi_3(10) \Phi_6(10) \Phi_{23}(10) \Phi_{46}(10) \Phi_{69}(10) \Phi_{138}(10)$$

We have $$\Phi_1(10) = 9$$ and $$\Phi_2(10) = 11$$ which corresponds to the factor of $$99$$, so removing those factors gives

$$\frac{10^{138} - 1}{99} = \Phi_3(10) \Phi_6(10) \Phi_{23}(10) \Phi_{46}(10) \Phi_{69}(10) \Phi_{138}(10).$$

The next few factors are

• $$\Phi_3(10) = \frac{10^3 - 1}{10 - 1} = 111 = 3 \cdot 37$$
• $$\Phi_6(10) = \frac{10^3 + 1}{10 + 1} = 91 = 7 \cdot 17$$

and from here things get big. The next one is $$\Phi_{23}(10) = \frac{10^{23} - 1}{10 - 1} = \underbrace{111 \cdots 1}_{23 \text{ times}}$$ which has no more "obvious" factors. From here if you really want to do this by hand you can use the following fact:

Proposition: A prime $$p$$ divides $$\Phi_n(x)$$ if and only if $$x$$ has multiplicative order $$n \bmod p$$, and in particular $$p \equiv 1 \bmod n$$.

So to search for factors of $$\frac{10^{23} - 1}{9}$$ you can restrict your attention to primes congruent to $$1 \bmod 23$$, and so forth. But this isn't a big help considering how large it is. In fact it turns out to be prime but I don't know how you'd prove that by hand.

• cf. OEIS Commented Oct 9, 2020 at 20:43
• The standard reference for such cyclotomic "algebraic factroizations" of integers is John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr., Factorizations of $\,b^n\pm1,\,$ 2nd ed., Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, RI, 1988. Commented Oct 9, 2020 at 21:18

From $$x-1\mid x^n-1$$, we conclude that $$10^n-1$$ divides $$100^{69}-1$$ for all divisors $$n$$ of $$138=2\cdot 3\cdot 23$$. Of these $$10^1-1$$ and $$10^2-1$$ may cancel against the denominator, but $$10^3-1=999=3^3\cdot 37$$ certainly gives you an extra $$3$$ and $$37$$, etc.