Lowest prime factor of 300^300-1

I saw a neat little facebook puzzle: find the lowest prime factor of 300³⁰⁰-1. It took me a while to puzzle it out, but I figured it out completely in my head.

First pass filter of what it cannot be:

2, 3 and 5 are all prime factors of 300³⁰⁰, so they cannot be prime factors of 300³⁰⁰-1. So the first candidate is 7.

The answer (without proof):

The correct answer is 7

The method to prove it:

Use modulo arithmetic. You don't even have to do the whole thing, just find the pattern.

Further spoiler for that method:

If x is the prime factor we're looking for, then (300³⁰⁰-1) modulo x is 0, which also means (300³⁰⁰) modulo x is 1. But you can do the modulo at any time and keep doing it, you don't have to multiply out the whole number and then do the modulo.

Even more spoilers for that method:

300³⁰⁰ = 3³⁰⁰*2⁶⁰⁰*5⁶⁰⁰. If each of these modulo x gets you to 1, then the whole thing gets you to 1.

Proof:

Let's try modulo 7. There are 7 digits: 0 through 6. But when we're constructing 300³⁰⁰ by multiplying all the factors, we know that at no step are we ever going to run into 0, because that only happens if the number can be factored by 7, which it can't. It must also hit every digit from 1 to 6 once within each cycle since 7 is prime, and it must do so on a repeating basis. Let's try 3, for example:

3^0 = 1, mod 7 = 1
3^1 = 3, mod 7 = 3
3^2 = 9, mod 7 = 2
3^3 = 27, mod 7 =6
Note that we can either do 27 - 21 = 6, or do the modulo first and note that 3^3 mod 7 = 3 * (3^2 mod 7) mod 7 = 3*2 mod 7 = 6
Keep doing the mod early so the numbers never get big.
3^4 mod 7 = 18 mod 7 = 4
3^5 mod 7 = 12 mod 7 = 5
3^6 mod 7 = 15 mod 7 = 1

And we've come full circle. The cycle will repeat, and it repeats every 7-1 = 6 multiplies. 3³⁰⁰ mod 7 = 3⁶⁵⁰ mod 7 = (3⁶ mod 7)⁵⁰ mod 7 = 1⁵⁰ mod 7 = 1.

The same thing happens with 2 and 5. So that means 300³⁰⁰ mod 7 = 1, and 300³⁰⁰-1 mod 7 = 0. So 300³⁰⁰-1 is divisible by 7, and that's the smallest prime factor.

via International Skeptics Forum https://ift.tt/2XJQ2YC