Puzzle and meta-puzzle: Factorisation — SOLUTION

In an earlier post I posed the following problem:

Find the prime factorization of {12318876808768112319}.


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.

Please leave a reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s