Fermat’s Little Theorem
In this article, I will introduce Fermat’s Little Theorem and a simple algorithm problem where this theorem can be applied.
Fermat’s little theorem states that if p is a prime number, then for all real integers a, (aᵖ-a) is an integer multiple of p. This is represented in the following modular arithmetic notation.
If p is not a prime number, but satisfies the equation above for all real integers a, then that number is called a Carmichael number. Some Carmichael numbers are: 561, 1105, 1729, 2465, 2821…
Proof of Fermat’s Little Theorem
I will prove Fermat’s Little Theorem using mathematical induction.
Application in Competitive Programming
You can easily calculate the modular inverse using binary exponentation. There are many problems that require modulus of 1000000007 or 998244353, which are both prime numbers.
References
Long, C. L. (1965). Elementary introduction to number theory. http://ci.nii.ac.jp/ncid/BA00965634
Singh, N. (2022, August 21). Fermat’s little theorem. GeeksforGeeks. https://www.geeksforgeeks.org/fermats-little-theorem/
