Fermat's little theorem

1. Nov 30, 2009

Dweirdo

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!! )

DW

Last edited by a moderator: May 4, 2017
2. Nov 30, 2009

hamster143

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.

3. Nov 30, 2009

Dweirdo

cool,
Thank You hamster! :D