Introduction
Modular arithmetic is a system of arithmetic for integers, where numbers wrap around after reaching a certain value, known as the modulus. Fermat’s Little Theorem is a useful tool for simplifying calculations in modular arithmetic, especially when dealing with large exponents.
Fermat’s Little Theorem
Fermat’s Little Theorem states that if $p$ is a prime number and $a$ is an integer not divisible by $p$, then:
$a^{p-1} equiv 1 pmod{p}$
This can be rearranged to solve various modular equations. For instance, if we need to find $a^{k} mod p$ for large $k$, Fermat’s theorem helps reduce the exponent.
Example 1: Simplifying Large Exponents
Suppose we need to compute $3^{100} mod 7$. Direct calculation would be tedious, but using Fermat’s Little Theorem, we know:
$3^{6} equiv 1 pmod{7}$
Since $100 = 6 times 16 + 4$, we can write:
$3^{100} = 3^{6 times 16 + 4} = (3^{6})^{16} times 3^{4} equiv 1^{16} times 3^{4} equiv 3^{4} pmod{7}$
Now, we only need to compute $3^{4} mod 7$:
$3^{4} = 81 equiv 4 pmod{7}$
Thus, $3^{100} mod 7 = 4$
Example 2: Finding Modular Inverses
Fermat’s Little Theorem is also useful for finding modular inverses. The modular inverse of $a$ modulo $p$ is a number $b$ such that $a times b equiv 1 pmod{p}$. According to Fermat’s theorem:
$a^{p-1} equiv 1 pmod{p}$
Multiplying both sides by $a^{-1}$, we get:
$a^{p-2} equiv a^{-1} pmod{p}$
So, $a^{-1} equiv a^{p-2} pmod{p}$
For example, to find the modular inverse of $3$ modulo $7$, we compute:
$3^{7-2} = 3^{5} pmod{7}$
Calculating $3^{5}$:
$3^{5} = 243 equiv 5 pmod{7}$
Thus, the modular inverse of $3$ modulo $7$ is $5$
Conclusion
Fermat’s Little Theorem is a powerful tool in modular arithmetic, making it easier to handle large exponents and find modular inverses. By understanding and applying this theorem, we can simplify and solve complex modular equations efficiently.
2. Brilliant – Fermat’s Little Theorem3. Art of Problem Solving – Fermat’s Little Theorem