Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Fermat's little theorem

  1. Nov 30, 2009 #1
    Hi, I have spme questions about Fermat's little theorem-http://en.wikipedia.org/wiki/Fermat%27s_little_theorem. [Broken]

    I need to think about a mathematical algorithm to deal with this theorem- finding pseudo-primes ,aka, Carmichael numbers.
    When I'm dealing with huge numbers ,it is very difficult,let's say:
    a is 5, n is 200
    than getting a number like 5^200 is stupid, and thus I need another method which will prevent the calculation of this number.
    anybody can point me to the right direction?

    another thing that I noticed is, if we do the test for non prime numbers such as 15
    then we get pairs of reminders, I mean:
    (7^15)%15 =13
    (13^15)%15=7
    just something cool(it's not just for these numbers!! )

    Thanks in advance!

    DW
     
    Last edited by a moderator: May 4, 2017
  2. jcsd
  3. Nov 30, 2009 #2
    Since 200 = 128 + 64 + 8, all you need is to calculate 5^8 mod 200, 5^64 mod 200, and 5^128 mod 200, and multiply those together ... and it's easy to calculate those because

    5^2 mod 200 = ((5 mod 200)*(5 mod 200)) mod 200 = 25

    5^4 mod 200 = ((5^2 mod 200)*(5^2 mod 200)) mod 200 = 625 mod 200 = 25

    etc.

    so you can check each b using simple integer arithmetic in log(n) time.
     
  4. Nov 30, 2009 #3
    cool,
    Thank You hamster! :D
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Fermat's little theorem
  1. Fermat's theorem (Replies: 1)

Loading...