# Puzzle and meta-puzzle: Factorisation — SOLUTION

In an earlier post I posed the following problem:

Find the prime factorization of ${12318876808768112319}$.

Solution.

Write $z:=12318876808768112319$. As a first attempt we shall ask some straightforward questions:

1. Is ${z}$ even? No.
2. Is ${z}$ divisible by ${3}$? We use the “sum the digits” trick, and find that — yes — ${z}$ is divisible by ${3^{4}}$, but not divisible by ${3^{5}}$.
3. Is ${z}$ divisible by ${5}$? No.

Etc. We can directly calculate for other small primes, and if we push on we will find a factor of ${11}$.

Taking out these factors, namely ${3^{4}}$ and ${11}$, we are still left with a large number:

$\displaystyle 13825899897607309.$

How should we proceed? We seek a more systematic approach, or at least some sort of shortcut.

Fortunately, in this special case, such a short cut is available: we exploit the repetition of various strings of digits in the base-${10}$ representation of ${z}$. Let ${x:=12319}$ and let ${y:=10^{5}}$. Then ${y-x=87681}$, and $z=y^{3}(x-1)+y^{2}(y-x-1)+y(y-x)+x$. Rearranging, we get

$\begin{array}{rl} z &= y^{3}x-y^{2}x-yx+x\\ &= x(y^{3}-y^{2}-y+1)\\ &= x(y-1)^{2}(y+1). \end{array}$

It now remains to find the prime factorizations of ${x=12319}$, ${y-1=99999}$, and ${y+1=100001}$. The most attractive place to begin is with ${y-1=99999}$:

$\begin{array}{rl} y-1 &= 99999\\ &= 3^{2}\cdot11111\\ &= 3^{2}\cdot41\cdot271. \end{array}$

I don’t know of any particularly neat way of finding the factors ${41}$ and ${271,}$ but it’s very easy by hand.

Next we consider ${y+1=10^{5}+1}$:

$y+1 = 100001 = 11\cdot9091.$

The factor of ${11}$ is easy to find, but I don’t know a quick way to verify that ${9091}$ is prime, other than trial division, by checking for prime factors up to ${\lfloor\sqrt{9091}\rfloor=95}$.

Finally, we consider ${x=12319}$:

$x = 12319 = 97\cdot127.$

Again, I don’t know an easy way to find these factors, other than trial division, by checking for prime factors up to ${\lfloor\sqrt{12319}\rfloor=110}$.

Putting all of this together, we have the prime factorization

$12318876808768112319 = 3^{4}\cdot11\cdot41^{2}\cdot97\cdot127\cdot271^{2}\cdot9091.$

As mentioned in the original post, perhaps the real challenge is to come up with a problem that retains the trickiness of this example, but avoids the cumbersome checking.