Fermat's little theorem is a fundamental theorem in number theory, named after the French mathematician Pierre de Fermat. It states that for any prime number p and any integer a, the remainder when a is divided by p is equal to a raised to the power of p-1, when divided by p.
Fermat's little theorem is a powerful tool for proving divisibility and primality in number theory. It has many applications in cryptography, including the RSA cryptosystem, which relies on the fact that it is difficult to find the prime factors of a large number.
Fermat's little theorem is used in the RSA cryptosystem to ensure that the private key cannot be easily determined from the public key. This is because the private key is the inverse of the public key modulo phi(n), which is difficult to compute without knowing the prime factors of n.
No, Fermat's little theorem only holds for prime moduli. It can be generalized to the Euler's theorem, which states that for any positive integer n and any integer a that is relatively prime to n, a raised to the power of phi(n) (Euler's totient function) is congruent to 1 modulo n.
Yes, there are some exceptions known as Fermat pseudoprimes. These are composite numbers that satisfy Fermat's little theorem even though they are not prime. However, these numbers are rare and can be identified using other tests for primality.
