Puzzle and meta-puzzle: Factorisation — SOLUTION

In an earlier post I posed the following problem:

Find the prime factorization of .

Solution.

Write . As a first attempt we shall ask some straightforward questions:

1. Is even? No.
2. Is divisible by ? We use the “sum the digits” trick, and find that — yes — is divisible by , but not divisible by .
3. Is divisible by ? No.

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

Taking out these factors, namely and , we are still left with a large number:

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- representation of . Let and let . Then , and . Rearranging, we get

It now remains to find the prime factorizations of , , and . The most attractive place to begin is with :

I don’t know of any particularly neat way of finding the factors and but it’s very easy by hand.

Next we consider :

The factor of is easy to find, but I don’t know a quick way to verify that is prime, other than trial division, by checking for prime factors up to .

Finally, we consider :

Again, I don’t know an easy way to find these factors, other than trial division, by checking for prime factors up to .

Putting all of this together, we have the prime factorization

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.

Advertisement