Using Fermat's Little Theorem to Find Prime Factors of 10^12 -1

[ribbon]

Homework Statement

Find 3 different prime factors of 10^12 -1.

Homework Equations

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?

 

[micromass]

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

 

[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?

 

[micromass]

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?

 

[ribbon]

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?

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?

 

[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...

 

[Curious3141]

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...

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

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

 

[ehild]

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

 

[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.

 

[ehild]

One more method: 10¹² is 1 followed by twelve zeros. Subtracting 1, twelve 9-s remain. 10¹²-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

 

[ribbon]

Thanks guys, very helpful.