Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Fermat’s little theorem states that if p is a prime number, then for any integer a, the number (a
- p−a)
- is an integer multiple of p. In the notation of modular arithmetic, this is expressed as
- a
- p ≡ a(mod p)
- For example, if a = 2 and p = 7, 2
- 7 = 128, and 128 − 2 = 7 × 18 is an integer multiple of 7. We can
- also write 128%7 = 2, here % is the modulo operator used in C/C++ or Java.
- If a is not divisible by p, Fermat’s little theorem is equivalent to the statement that a
- p−1 − 1 is an
- integer multiple of p, or in symbols
- a
- p−1 ≡ 1(mod p)
- For example, if a = 2 and p = 7 then 2
- 6 = 64 and 64 − 1 = 63 is a multiple of 7. We can also write
- 64%7 = 1.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement