fermat little theorem Algorithm
Fermat's Little Theorem is a fundamental algorithm in number theory, named after the French mathematician Pierre de Fermat. This theorem states that if p is a prime number and a is an integer not divisible by p, then a^(p-1) is congruent to 1 modulo p. In other words, a^(p-1) - 1 is a multiple of p. The algorithm is particularly useful in various applications such as primality testing, modular arithmetic, and cryptography.
The algorithm builds on the idea that prime numbers have unique properties when it comes to divisibility and modular arithmetic. For example, consider the prime number p = 5 and the integer a = 3. According to Fermat's Little Theorem, 3^(5-1) should be congruent to 1 modulo 5. Indeed, 3^4 = 81, and 81 - 1 = 80, which is a multiple of 5. The theorem can be proved using different methods, such as mathematical induction, group theory, or elementary number theory techniques. Overall, Fermat's Little Theorem is a powerful tool that deepens our understanding of prime numbers and their unique properties in the realm of number theory.
# Python program to show the usage of Fermat's little theorem in a division
# According to Fermat's little theorem, (a / b) mod p always equals a * (b ^ (p - 2)) mod p
# Here we assume that p is a prime number, b divides a, and p doesn't divide b
# Wikipedia reference: https://en.wikipedia.org/wiki/Fermat%27s_little_theorem
def binary_exponentiation(a, n, mod):
if n == 0:
return 1
elif n % 2 == 1:
return (binary_exponentiation(a, n - 1, mod) * a) % mod
else:
b = binary_exponentiation(a, n / 2, mod)
return (b * b) % mod
# a prime number
p = 701
a = 1000000000
b = 10
# using binary exponentiation function, O(log(p)):
print((a / b) % p == (a * binary_exponentiation(b, p - 2, p)) % p)
# using Python operators:
print((a / b) % p == (a * b ** (p - 2)) % p)
