Have questions about Fermat's little theorem? Learn more here!

[Dweirdo]

Hi, I have spme questions about Fermat's little theorem-http://en.wikipedia.org/wiki/Fermat%27s_little_theorem.

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

 

[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.

 

[Dweirdo]

cool,
Thank You hamster! :D