# Fermat Little Theorem?

## Homework Statement

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

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

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

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?

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?

• 1 person
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?

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:
Curious3141
Homework Helper
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
Homework Helper
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:
Curious3141
Homework Helper
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.

• 1 person
ehild
Homework Helper
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

• 1 person