1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Fermat Little Theorem?

  1. Jul 29, 2013 #1
    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. jcsd
  3. Jul 29, 2013 #2
    Why not simplify your problem using the identity ##a^2 - b^2 = (a-b)(a+b)##?
  4. Jul 29, 2013 #3
    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?
  5. Jul 29, 2013 #4
    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?
  6. Jul 29, 2013 #5
    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?
  7. Jul 29, 2013 #6
    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
  8. Jul 29, 2013 #7


    User Avatar
    Homework Helper

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

    What is (10^12 - 1) (mod 9)?
  9. Jul 29, 2013 #8


    User Avatar
    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).

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


    User Avatar
    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.
  11. Jul 30, 2013 #10


    User Avatar
    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?

  12. Jul 30, 2013 #11
    Thanks guys, very helpful.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted