Fermat Little Theorem?

1. Jul 29, 2013

ribbon

1. The problem statement, all variables and given/known data
Find 3 different prime factors of 10^12 -1.

2. Relevant equations

3. The attempt at a solution
I began trying to solve this with help from F.L.T. - if p is prime and p does NOT divide a, then a^(p-1) is congruent to 1 (mod p).

So I re-wrote, 10^(13-1) is congruent to 1 (mod13). Subtracting 1 from both sides of the congruence I have:

10^12 is congruent to 1 (mod13).
I believe 3 will be one prime factor since any multiple of 10 divided by 3 will yield 1 remainder. But I am stumped for others, and don't even know if finding 3 was systematically correct?

Now I also have a theorem that says I can divide both sides of the congruence under certain conditions, but I do not see that it will help? Any guidance, is FLT even a correct approach to this problem?

2. Jul 29, 2013

micromass

Staff Emeritus
Why not simplify your problem using the identity $a^2 - b^2 = (a-b)(a+b)$?

3. Jul 29, 2013

ribbon

Interesting... So we could have (10^6 +1)(10^6 - 1) is congruent to 1(mod13).

Can I now use this theorem?
"If p is a prime number and x is an integer satisfying x^2 - 1
(mod p), then either x  is congruent to 1 (mod p) or x is congruent to p-1 (mod p)."

But does it even help?

4. Jul 29, 2013

micromass

Staff Emeritus
You already used FLT to obtain that 13 divides your number. This is correct.

You have decomposed your number into $(10^6 + 1)(10^6 - 1)$. Can you use FLT again?
Can you continue and decompose $10^6 - 1$ into something?

5. Jul 29, 2013

ribbon

Oh wow, yes I can now write 10^6 - 1 using FLT again and it becomes 10^6 is congruent to 1(MOD7)!

So now I have 2 primes that divide according to the condition, 7 and 13. However is the third prime found by a similar technique?

6. Jul 29, 2013

ribbon

Haha why am I even asking, of course I can... I think its getting too late for me!

I will just simplify 10^6 - 1 into (10^3 + 1)(10^3 - 1) and following by the same algorithm, 3 will be my appropriate divisor and thus final prime factor.

Thanks Micromass.

EDIT: Wait I made a careless error this is not correct because I would have p=4 so that when subtracted 1 would equal 3, however 4 is not prime so then I would not be able to rewrite it the way I thought...

Last edited: Jul 29, 2013
7. Jul 29, 2013

Curious3141

For the last prime factor, you don't need any fancy "trickery".

What is (10^12 - 1) (mod 9)?

8. Jul 29, 2013

ehild

Without any theorem, just go on factorizing, using in addition to a2-b2=(a-b)(a+b) the identities for the cubes : a3-b3=(a-b)(a2+ab+b2) and a3+b3=(a-b)(a2-ab+b2) . You will find three prime factors quite easily (and even more).

ehild

Last edited: Jul 30, 2013
9. Jul 30, 2013

Curious3141

I was thinking of something much simpler, like seeing the pattern of (10-1), (10^2-1), etc...

The results are obviously divisible by 9 (and hence divisible by the only prime factor of 9).

A more rigorous development would be:

$$10\equiv 1\pmod{9}$$

$$10^{12}\equiv 1\pmod{9}$$

and so forth. Either way, Fermat's Little Theorem is not needed for this part.

10. Jul 30, 2013

ehild

One more method: 1012 is 1 followed by twelve zeros. Subtracting 1, twelve 9-s remain. 1012-1=999999999999. The number in the parentheses is twelve 9-s following each other, so obviously divisible by 9. 999999999999=9*111111111111.
111111111111 is six (11)-s, divisible by 11.
But it is also four (111) and 111=3*37....Do you find more prime divisors?

ehild

11. Jul 30, 2013