Fermat Little Theorem?

  • Thread starter ribbon
  • Start date
  • #1
38
0

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?
 

Answers and Replies

  • #2
22,129
3,297
Why not simplify your problem using the identity ##a^2 - b^2 = (a-b)(a+b)##?
 
  • #3
38
0
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
22,129
3,297
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
38
0
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?
 
  • #6
38
0
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:
  • #7
Curious3141
Homework Helper
2,850
87
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)?
 
  • #8
ehild
Homework Helper
15,543
1,914
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:
  • #9
Curious3141
Homework Helper
2,850
87
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
ehild
Homework Helper
15,543
1,914
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
38
0
Thanks guys, very helpful.
 

Related Threads on Fermat Little Theorem?

  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
1
Views
2K
Replies
4
Views
3K
Replies
6
Views
983
Replies
3
Views
2K
Replies
4
Views
3K
Replies
4
Views
2K
  • Last Post
Replies
0
Views
1K
Top