In an earlier post I posed the following problem:
Find the prime factorization of .
Write . As a first attempt we shall ask some straightforward questions:
- Is even? No.
- Is divisible by ? We use the “sum the digits” trick, and find that — yes — is divisible by , but not divisible by .
- 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.