The Central Idea
Powers modulo \(n\) often repeat.
For example, modulo \(5\),
\[ 2^1\equiv2, \] \[ 2^2\equiv4, \] \[ 2^3\equiv3, \] \[ 2^4\equiv1\pmod5. \]Once a power becomes congruent to \(1\), later exponents can often be reduced using the cycle.
Fermat's and Euler's theorems give general conditions under which this behavior is guaranteed.
Fermat's Little Theorem
Let \(p\) be prime. If
\[ \gcd(a,p)=1, \]then
\[ \boxed{ a^{p-1}\equiv1\pmod p }. \]Because \(p\) is prime, the condition \(\gcd(a,p)=1\) is equivalent to saying that \(p\nmid a\).
A First Fermat Example
Since \(7\) is prime and
\[ \gcd(3,7)=1, \]Fermat's Little Theorem gives
\[ 3^{7-1}\equiv1\pmod7. \]Therefore,
\[ \boxed{3^6\equiv1\pmod7}. \]Why the Prime Condition Matters
The theorem is stated for a prime modulus.
If the modulus is composite, the exponent \(n-1\) does not generally produce \(1\).
For example,
\[ 2^5=32 \]and
\[ 32\equiv2\pmod6, \]not \(1\).
Thus one cannot replace the prime \(p\) in Fermat's theorem by an arbitrary modulus.
An Equivalent Fermat Form
Fermat's Little Theorem is also commonly written
\[ \boxed{ a^p\equiv a\pmod p }. \]This form is valid for every integer \(a\), including multiples of \(p\).
If \(p\nmid a\), multiplying
\[ a^{p-1}\equiv1\pmod p \]by \(a\) gives the result immediately.
Example: The Equivalent Form
Let
\[ a=10 \]and
\[ p=7. \]Fermat's equivalent form gives
\[ 10^7\equiv10\pmod7. \]Since
\[ 10\equiv3\pmod7, \]this can also be written
\[ 10^7\equiv3\pmod7. \]Reducing Large Exponents with Fermat
Suppose \(p\) is prime and \(\gcd(a,p)=1\).
Since
\[ a^{p-1}\equiv1\pmod p, \]powers of \(a\) can be reduced in blocks of \(p-1\).
If
\[ k=q(p-1)+r, \]then
\[ a^k = \left(a^{p-1}\right)^q a^r \equiv a^r \pmod p. \]Example: \(3^{100}\pmod7\)
Since \(7\) is prime,
\[ 3^6\equiv1\pmod7. \]Divide the exponent \(100\) by \(6\):
\[ 100=6(16)+4. \]Therefore,
\[ 3^{100} = (3^6)^{16}3^4 \equiv 3^4 \pmod7. \]Now
\[ 3^4=81\equiv4\pmod7. \]Hence
\[ \boxed{3^{100}\equiv4\pmod7}. \]Another Fermat Example
Find
\[ 5^{222}\pmod{11}. \]Since \(11\) is prime and \(11\nmid5\),
\[ 5^{10}\equiv1\pmod{11}. \]Reduce the exponent:
\[ 222=10(22)+2. \]Therefore,
\[ 5^{222}\equiv5^2=25\equiv3\pmod{11}. \]Thus
\[ \boxed{5^{222}\equiv3\pmod{11}}. \]Fermat and Modular Inverses
If \(p\) is prime and \(p\nmid a\), then
\[ a^{p-1}\equiv1\pmod p. \]Rewrite this as
\[ a\cdot a^{p-2}\equiv1\pmod p. \]Therefore,
\[ \boxed{ a^{-1}\equiv a^{p-2}\pmod p }. \]Fermat's theorem can therefore produce modular inverses under a prime modulus.
Example: Inverse from Fermat's Theorem
Find the inverse of \(3\) modulo \(7\).
Fermat gives
\[ 3^{-1}\equiv3^{7-2}=3^5\pmod7. \]Since
\[ 3^5=243\equiv5\pmod7, \]we obtain
\[ \boxed{3^{-1}\equiv5\pmod7}. \]Indeed,
\[ 3\cdot5=15\equiv1\pmod7. \]Euler's Totient Function
Euler's theorem extends the Fermat pattern to composite moduli.
The key quantity is Euler's totient function,
\[ \boxed{\varphi(n)}. \]The value \(\varphi(n)\) counts the positive integers from \(1\) through \(n\) that are relatively prime to \(n\).
Example: \(\varphi(8)\)
Consider
\[ 1,2,3,4,5,6,7,8. \]The numbers relatively prime to \(8\) are
\[ 1,\ 3,\ 5,\ 7. \]Therefore,
\[ \boxed{\varphi(8)=4}. \]Example: \(\varphi(10)\)
The integers from \(1\) through \(10\) relatively prime to \(10\) are
\[ 1,\ 3,\ 7,\ 9. \]Therefore,
\[ \boxed{\varphi(10)=4}. \]Totient of a Prime
If \(p\) is prime, every positive integer
\[ 1,2,\ldots,p-1 \]is relatively prime to \(p\).
Therefore,
\[ \boxed{\varphi(p)=p-1}. \]This is why Euler's theorem reduces to Fermat's Little Theorem for prime moduli.
Totient of a Prime Power
If \(p\) is prime and \(k\ge1\), then
\[ \boxed{ \varphi(p^k)=p^k-p^{k-1} }. \]Equivalently,
\[ \boxed{ \varphi(p^k)=p^k\left(1-\frac1p\right) }. \]The excluded values are precisely the multiples of \(p\).
Example: \(\varphi(27)\)
Since
\[ 27=3^3, \]the prime-power formula gives
\[ \varphi(27) = 27-9 = 18. \]Therefore,
\[ \boxed{\varphi(27)=18}. \]Totient from Prime Factorization
If
\[ n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}, \]then
\[ \boxed{ \varphi(n) = n \left(1-\frac1{p_1}\right) \left(1-\frac1{p_2}\right) \cdots \left(1-\frac1{p_k}\right) }. \]Only the distinct prime divisors of \(n\) appear in the product.
Example: \(\varphi(36)\)
Factor
\[ 36=2^2\cdot3^2. \]Then
\[ \varphi(36) = 36 \left(1-\frac12\right) \left(1-\frac13\right). \]Therefore,
\[ \varphi(36) = 36\cdot\frac12\cdot\frac23 = 12. \]Thus
\[ \boxed{\varphi(36)=12}. \]Euler's Theorem
If
\[ \gcd(a,n)=1, \]then Euler's theorem states
\[ \boxed{ a^{\varphi(n)}\equiv1\pmod n }. \]This generalizes Fermat's Little Theorem from prime moduli to arbitrary positive moduli, provided the base is relatively prime to the modulus.
A First Euler Example
Find a guaranteed exponent cycle for powers of \(3\) modulo \(10\).
Since
\[ \gcd(3,10)=1 \]and
\[ \varphi(10)=4, \]Euler's theorem gives
\[ \boxed{3^4\equiv1\pmod{10}}. \]Example: \(3^{100}\pmod{10}\)
From Euler's theorem,
\[ 3^4\equiv1\pmod{10}. \]Since
\[ 100=4(25), \]we have
\[ 3^{100} = (3^4)^{25} \equiv 1^{25} \equiv1 \pmod{10}. \]Therefore,
\[ \boxed{3^{100}\equiv1\pmod{10}}. \]Example: A Composite Modulus
Compute
\[ 7^{100}\pmod{15}. \]Since
\[ \gcd(7,15)=1 \]and
\[ \varphi(15) = 15 \left(1-\frac13\right) \left(1-\frac15\right) = 8, \]Euler's theorem gives
\[ 7^8\equiv1\pmod{15}. \]Completing the Composite-Modulus Example
Reduce the exponent:
\[ 100=8(12)+4. \]Therefore,
\[ 7^{100} \equiv 7^4 \pmod{15}. \]Compute:
\[ 7^2=49\equiv4\pmod{15}, \] \[ 7^4\equiv4^2=16\equiv1\pmod{15}. \]Hence
\[ \boxed{7^{100}\equiv1\pmod{15}}. \]The Relative-Primality Condition Is Essential
Euler's theorem requires
\[ \gcd(a,n)=1. \]For example,
\[ \varphi(8)=4. \]But if \(a=2\), then
\[ \gcd(2,8)=2\neq1. \]Indeed,
\[ 2^4=16\equiv0\pmod8, \]not \(1\).
Fermat as a Special Case of Euler
If \(p\) is prime, then
\[ \varphi(p)=p-1. \]Euler's theorem becomes
\[ a^{\varphi(p)} = a^{p-1} \equiv1\pmod p, \]which is exactly Fermat's Little Theorem for \(p\nmid a\).
Euler and Modular Inverses
If
\[ \gcd(a,n)=1, \]Euler's theorem gives
\[ a^{\varphi(n)}\equiv1\pmod n. \]Therefore,
\[ a\cdot a^{\varphi(n)-1}\equiv1\pmod n. \]Hence
\[ \boxed{ a^{-1}\equiv a^{\varphi(n)-1}\pmod n }. \]Example: Euler Inverse
Find an inverse of \(3\) modulo \(10\).
Since
\[ \varphi(10)=4, \]Euler's theorem gives
\[ 3^{-1}\equiv3^{3}=27\equiv7\pmod{10}. \]Therefore,
\[ \boxed{3^{-1}\equiv7\pmod{10}}. \]Check:
\[ 3\cdot7=21\equiv1\pmod{10}. \]The Guaranteed Exponent May Not Be the Smallest
Euler's theorem guarantees that
\[ a^{\varphi(n)}\equiv1\pmod n \]when \(\gcd(a,n)=1\).
But the powers of \(a\) may return to \(1\) earlier.
For example, modulo \(8\),
\[ \varphi(8)=4, \]yet
\[ 3^2=9\equiv1\pmod8. \]Thus the actual repeating cycle can be shorter than \(\varphi(n)\).
Multiplicative Order
When \(\gcd(a,n)=1\), the smallest positive integer \(k\) satisfying
\[ a^k\equiv1\pmod n \]is called the multiplicative order of \(a\) modulo \(n\).
Euler's theorem guarantees that such a positive exponent exists and that the order divides the repeating behavior governed by \(\varphi(n)\).
At this stage, the main practical lesson is simply that a smaller cycle may be available.
Example: Finding a Shorter Cycle
Consider powers of \(2\) modulo \(7\):
\[ 2^1\equiv2, \] \[ 2^2\equiv4, \] \[ 2^3\equiv1\pmod7. \]Fermat guarantees
\[ 2^6\equiv1\pmod7, \]but the actual cycle returns to \(1\) after only \(3\) powers.
Using a Shorter Cycle Efficiently
To compute
\[ 2^{100}\pmod7, \]using the observed cycle \(2^3\equiv1\pmod7\) is faster.
Since
\[ 100=3(33)+1, \]we have
\[ 2^{100} \equiv 2 \pmod7. \]Therefore,
\[ \boxed{2^{100}\equiv2\pmod7}. \]Euler's Theorem as a Cycle Guarantee
Euler's theorem can be interpreted as saying that the invertible residue classes modulo \(n\) have finite multiplicative behavior.
If
\[ \gcd(a,n)=1, \]then repeated multiplication by \(a\) cannot wander indefinitely without repeating. Euler's theorem guarantees a return to the multiplicative identity class:
\[ [a]_n^{\varphi(n)}=[1]_n. \]Computing the Last Digit of a Large Power
The last decimal digit of an integer is its remainder modulo \(10\).
Find the last digit of
\[ 7^{2026}. \]Since
\[ \gcd(7,10)=1 \]and
\[ \varphi(10)=4, \]reduce the exponent:
\[ 2026\equiv2\pmod4. \]Completing the Last-Digit Example
Therefore,
\[ 7^{2026}\equiv7^2=49\equiv9\pmod{10}. \]Hence the last digit is
\[ \boxed{9}. \]Computing the Last Two Digits
The last two decimal digits are determined modulo \(100\).
If the base is relatively prime to \(100\), Euler's theorem can help.
Since
\[ 100=2^2\cdot5^2, \]the totient is
\[ \varphi(100) = 100 \left(1-\frac12\right) \left(1-\frac15\right) = 40. \]Example: Last Two Digits
Find
\[ 3^{42}\pmod{100}. \]Since
\[ \gcd(3,100)=1 \]and
\[ 3^{40}\equiv1\pmod{100}, \]we have
\[ 3^{42} \equiv 3^2 = 9 \pmod{100}. \]Therefore the last two digits are
\[ \boxed{09}. \]Common Error: Using Fermat with a Composite Modulus
Fermat's Little Theorem requires a prime modulus.
The statement
\[ a^{n-1}\equiv1\pmod n \]is not generally true when \(n\) is composite.
For composite moduli, Euler's theorem is the appropriate general result, provided the base is relatively prime to the modulus.
Common Error: Forgetting Relative Primality
Euler's theorem requires
\[ \gcd(a,n)=1. \]Before using
\[ a^{\varphi(n)}\equiv1\pmod n, \]always check the GCD.
Without this condition, the conclusion may fail.
Common Error: Reducing the Exponent Without Justification
One cannot automatically reduce every exponent modulo
\[ p-1 \]or
\[ \varphi(n). \]The appropriate theorem and its hypotheses must first be established.
Exponent reduction is a consequence of the modular cycle, not a universal exponent rule.
Common Error: Confusing \(\varphi(n)\) with \(n-1\)
The identity
\[ \varphi(n)=n-1 \]holds when \(n\) is prime.
For a composite number, the totient is usually smaller.
For example,
\[ \varphi(10)=4, \]not \(9\).
Common Error: Assuming \(\varphi(ab)=\varphi(a)\varphi(b)\) Always
The totient function is multiplicative for relatively prime inputs:
\[ \gcd(a,b)=1 \implies \varphi(ab)=\varphi(a)\varphi(b). \]But this cannot be applied without checking relative primality.
The prime-factorization formula is a safer general method.
A Reliable Procedure for Fermat Problems
- Confirm that the modulus \(p\) is prime.
- Check whether \(p\nmid a\) when using \(a^{p-1}\equiv1\pmod p\).
- Use the exponent cycle length \(p-1\).
- Reduce the large exponent modulo \(p-1\).
- Compute the remaining smaller power.
- Reduce the final result modulo \(p\).
A Reliable Procedure for Euler Problems
- Identify the modulus \(n\).
- Check that \(\gcd(a,n)=1\).
- Factor \(n\) if needed.
- Compute \(\varphi(n)\).
- Use \(a^{\varphi(n)}\equiv1\pmod n\).
- Reduce the exponent modulo \(\varphi(n)\).
- Compute the remaining smaller power.
- Reduce the result modulo \(n\).
Example: Full Fermat Workflow
Compute
\[ 11^{1234}\pmod{13}. \]The modulus \(13\) is prime, and
\[ 13\nmid11. \]Therefore,
\[ 11^{12}\equiv1\pmod{13}. \]Reduce the exponent:
\[ 1234=12(102)+10. \]Hence
\[ 11^{1234}\equiv11^{10}\pmod{13}. \]Completing the Fermat Workflow
Since
\[ 11\equiv-2\pmod{13}, \]we have
\[ 11^{10}\equiv(-2)^{10}=2^{10}\pmod{13}. \]Compute by repeated squaring:
\[ 2^4=16\equiv3\pmod{13}, \] \[ 2^8\equiv9\pmod{13}, \] \[ 2^{10}\equiv9\cdot4=36\equiv10\pmod{13}. \]Therefore,
\[ \boxed{11^{1234}\equiv10\pmod{13}}. \]Example: Full Euler Workflow
Compute
\[ 7^{222}\pmod{40}. \]First,
\[ \gcd(7,40)=1. \]Factor
\[ 40=2^3\cdot5. \]Therefore,
\[ \varphi(40) = 40 \left(1-\frac12\right) \left(1-\frac15\right) = 16. \]Completing the Euler Workflow
Euler gives
\[ 7^{16}\equiv1\pmod{40}. \]Reduce the exponent:
\[ 222=16(13)+14. \]Therefore,
\[ 7^{222}\equiv7^{14}\pmod{40}. \]Notice that
\[ 7^2=49\equiv9\pmod{40}, \] \[ 7^4\equiv9^2=81\equiv1\pmod{40}. \]Thus a shorter cycle is available:
\[ 7^{14} = (7^4)^3 7^2 \equiv 9 \pmod{40}. \]Hence
\[ \boxed{7^{222}\equiv9\pmod{40}}. \]Practice 1: Fermat Directly
Use Fermat's Little Theorem to state the value of
\[ 4^6\pmod7. \]Practice 2: Reduce a Large Exponent
Compute
\[ 2^{100}\pmod{11}. \]Practice 3: Equivalent Fermat Form
Simplify
\[ 15^{13}\pmod{13}. \]Practice 4: Compute a Totient
Find
\[ \varphi(18). \]Practice 5: Prime-Power Totient
Find
\[ \varphi(49). \]Practice 6: Euler's Theorem
Compute
\[ 5^{100}\pmod{12}. \]Practice 7: Check the Hypotheses
Can Euler's theorem be applied directly to
\[ 6^{20}\pmod{15}? \]Explain.
Practice 8: Modular Inverse
Use Fermat's Little Theorem to find the inverse of
\[ 5 \]modulo \(11\).
Practice 9: Last Digit
Find the last digit of
\[ 3^{2026}. \]Practice 10: Identify the Error
A student says:
“Since \(\varphi(12)=4\), we always have \(a^4\equiv1\pmod{12}\).”
Explain the missing condition.
Practice Answers
Practice 1
Since \(7\) is prime and \(7\nmid4\),
\[ 4^{7-1}\equiv1\pmod7. \]Therefore,
\[ \boxed{4^6\equiv1\pmod7}. \]Practice 2
Since \(11\) is prime,
\[ 2^{10}\equiv1\pmod{11}. \]Since
\[ 100=10(10), \]we get
\[ \boxed{2^{100}\equiv1\pmod{11}}. \]Practice 3
Fermat's equivalent form gives
\[ a^{13}\equiv a\pmod{13}. \]Therefore,
\[ 15^{13}\equiv15\equiv2\pmod{13}. \]Thus
\[ \boxed{2}. \]Practice 4
\[ 18=2\cdot3^2. \]Therefore,
\[ \varphi(18) = 18 \left(1-\frac12\right) \left(1-\frac13\right) = 6. \]Hence
\[ \boxed{\varphi(18)=6}. \]Practice 5
\[ 49=7^2. \]Therefore,
\[ \varphi(49)=49-7=42. \]Thus
\[ \boxed{\varphi(49)=42}. \]Practice 6
Since
\[ \gcd(5,12)=1 \]and
\[ \varphi(12) = 12 \left(1-\frac12\right) \left(1-\frac13\right) = 4, \]Euler's theorem gives
\[ 5^4\equiv1\pmod{12}. \]Since
\[ 100=4(25), \]we conclude
\[ \boxed{5^{100}\equiv1\pmod{12}}. \]Practice 7
No. Euler's theorem requires
\[ \gcd(a,n)=1. \]But
\[ \gcd(6,15)=3. \]Therefore Euler's theorem cannot be applied directly.
Practice 8
Since \(11\) is prime,
\[ 5^{-1}\equiv5^{11-2}=5^9\pmod{11}. \]A shorter calculation gives
\[ 5\cdot9=45\equiv1\pmod{11}. \]Therefore,
\[ \boxed{5^{-1}\equiv9\pmod{11}}. \]Practice 9
Since
\[ \varphi(10)=4 \]and
\[ 2026\equiv2\pmod4, \]we have
\[ 3^{2026}\equiv3^2=9\pmod{10}. \]Therefore the last digit is
\[ \boxed{9}. \]Practice 10
Euler's theorem requires
\[ \gcd(a,12)=1. \]The statement
\[ a^4\equiv1\pmod{12} \]is guaranteed only for integers \(a\) relatively prime to \(12\).
For example, \(a=2\) gives
\[ 2^4=16\equiv4\pmod{12}, \]not \(1\).
What to Remember
- If \(p\) is prime and \(p\nmid a\), then \(a^{p-1}\equiv1\pmod p\).
- An equivalent Fermat form is \(a^p\equiv a\pmod p\) for every integer \(a\).
- Euler's totient \(\varphi(n)\) counts the integers from \(1\) through \(n\) that are relatively prime to \(n\).
- If \(n=p_1^{a_1}\cdots p_k^{a_k}\), then \[ \varphi(n)=n\prod_{i=1}^{k}\left(1-\frac1{p_i}\right). \]
- If \(\gcd(a,n)=1\), then \(a^{\varphi(n)}\equiv1\pmod n\).
- Fermat's Little Theorem is the prime-modulus case of Euler's theorem.
- Both theorems can reduce very large exponents and help compute modular inverses.
- The theorem exponent gives a guaranteed cycle, but the actual cycle may be shorter.
The central operating rule is: verify the hypotheses first, identify the guaranteed exponent cycle, reduce the exponent, and then finish the smaller modular calculation.
Where We Go Next
Fermat's and Euler's relationships make large modular powers manageable and show how relative primality controls multiplicative behavior. The next lesson, Introductory Cryptography, applies these ideas to encoding, modular inverses, public and private keys, and the number-theoretic structure behind elementary cryptographic systems.