Back to the on-screen lesson ·
Fermat's theorem for any modulus, with the totient in the exponent, and the algorithm that makes an enormous power cheap.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to state Euler's theorem with its one hypothesis and see Fermat's little theorem as its prime case, reduce an exponent modulo the totient of the modulus, compute the remaining power by square-and-multiply with reduction at every step, and handle a base that is not coprime to the modulus by splitting the modulus instead.
Lesson 11 proved $a^{p-1} \equiv 1 \pmod p$ by showing the multiples of $a$ are the non-zero residues rearranged. Lesson 12 counted how many residues are units modulo any $n$, and called that count $\varphi(n)$.
Run the same proof modulo a composite and it almost works: the multiples of $a$ are not all the residues, but they are all the units rearranged, provided $a$ is itself a unit. The list has $\varphi(n)$ entries instead of $p - 1$, and the conclusion comes out with $\varphi(n)$ in the exponent. Fermat's theorem is what this becomes when $n$ is prime, because $\varphi(p) = p - 1$.
Euler's theorem is $a^{\varphi(n)} \equiv 1 \pmod n$ for $\gcd(a, n) = 1$.
A reduced residue system modulo $n$ is one representative of each unit class — $\varphi(n)$ numbers in all. The proof below multiplies one of these by $a$ and observes it is another.
Square-and-multiply (also called binary or fast exponentiation) computes $a^{k}$ with about $\log_2 k$ squarings and at most that many multiplications, by reading the binary expansion of $k$. It is what makes exponentiation modulo a thousand-digit number a routine operation rather than an impossible one.
Euler's theorem. If $\gcd(a, n) = 1$ then $a^{\varphi(n)} \equiv 1 \pmod n$.
Proof. Let $u_1, \ldots, u_{\varphi(n)}$ be a reduced residue system. Each $au_i$ is again a unit (a product of units is a unit), and no two are congruent (cancel the unit $a$). So $au_1, \ldots, au_{\varphi(n)}$ is the same set rearranged. Multiplying both lists, $$a^{\varphi(n)}\prod u_i \equiv \prod u_i \pmod n,$$ and $\prod u_i$ is a product of units, so it cancels.
The structure is exactly lesson 11's, with unit everywhere lesson 11 said non-zero residue. That substitution is the whole generalisation.
Reducing exponents. Since $a^{\varphi(n)} \equiv 1$, $$a^{k} \equiv a^{k \bmod \varphi(n)} \pmod n \qquad \text{when } \gcd(a, n) = 1.$$ Exponents live modulo $\varphi(n)$; values live modulo $n$.
Computing what is left. After the reduction the exponent is below $\varphi(n)$, which may still be large. Square-and-multiply handles it: write the exponent in binary, square repeatedly to build $a, a^2, a^4, a^8, \ldots$ modulo $n$, and multiply together the ones the binary digits select. Reducing after every step keeps every intermediate value below $n^2$.
The cost is about $\log_2 k$ squarings — for a $2048$-bit exponent, roughly three thousand multiplications of $2048$-bit numbers. That is a few microseconds, and it is why public-key cryptography is possible at all.
A caution. $\varphi(n)$ is an exponent that returns every unit to $1$; it is not necessarily the smallest. The smallest is the order of $a$, which divides $\varphi(n)$ — lesson 16 — and the smallest that works for every unit at once is the Carmichael function $\lambda(n)$, which can be much smaller than $\varphi(n)$.
Another way: steps
Another way: example
$7^{222} \bmod 15$. $\gcd(7, 15) = 1$ and $\varphi(15) = \varphi(3)\varphi(5) = 2 \cdot 4 = 8$. Then $222 = 27 \cdot 8 + 6$, so $7^{222} \equiv 7^{6}$. Squaring: $7^2 = 49 \equiv 4$, $7^4 \equiv 16 \equiv 1$, so $7^{6} = 7^{4} \cdot 7^{2} \equiv 1 \cdot 4 = 4$. Answer $4$ — and notice $7^4$ was already $1$, so the order of $7$ is $4$, not $8$.
Euler's theorem has one hypothesis, and a learner meets it as a restriction on what can be computed. It is not: the case it excludes is handled by taking the modulus apart, and the technique is worth having because it is exactly what RSA decryption needs.
Suppose $n = pq$ with $p, q$ distinct primes, and suppose $p \mid a$ so that $\gcd(a, n) \ne 1$. Euler's theorem is unavailable. But the Chinese remainder theorem splits the question: compute $a^{k}$ modulo $p$ and modulo $q$ separately, and recombine.
Modulo $p$ the answer is easy, because $a \equiv 0$, so every positive power is $0$. Modulo $q$ we do have $\gcd(a, q) = 1$, so Fermat applies and the exponent reduces modulo $q - 1$. Two easy computations, then one reconstruction.
That is exactly how RSA proves $m^{ed} \equiv m \pmod{n}$ for every message $m$, including the rare ones sharing a factor with the modulus. Working modulo $p$: either $p \mid m$, when both sides are $0$, or Fermat gives $m^{ed} = m^{1 + t(p-1)} \equiv m$. Same modulo $q$. Both congruences hold for every $m$, so by the Chinese remainder theorem the congruence holds modulo $n$. The scheme is correct on all inputs, not merely on most.
The same split is a speed technique. Decrypting modulo $p$ and modulo $q$ separately uses numbers half the size and exponents reduced by $p-1$ and $q-1$ rather than by $\varphi(n)$; since multiplication costs roughly the square of the size, two half-size exponentiations beat one full-size one by about a factor of four. Every serious implementation does this, and the private key stores $p$ and $q$ for the purpose.
Reducing the exponent modulo $n$. It reduces modulo $\varphi(n)$. Modulo $10$, $\varphi(10) = 4$: $3^{14} \equiv 3^{2} = 9$, while reducing the exponent by $10$ would give $3^{4} \equiv 1$.
Dropping the coprimality check. $2^{\varphi(4)} = 2^{2} = 4 \equiv 0 \pmod 4$, not $1$. When the base shares a factor with the modulus, split the modulus instead.
Taking $\varphi(n)$ for the order. It is a multiple of the order, not the order. $7^{4} \equiv 1 \pmod{15}$ although $\varphi(15) = 8$. Nothing is wrong when the power returns to $1$ early.
Computing the power before reducing the exponent. $3^{1000}$ has nearly five hundred digits. Reducing the exponent first is not an optimisation, it is the method.
Reducing only at the end. Reduce after every multiplication. The answer is the same and the numbers stay small — which for cryptographic sizes is the difference between a microsecond and not finishing.
Find $11^{2024} \bmod 21$. $\gcd(11, 21) = 1$, and $\varphi(21) = \varphi(3)\varphi(7) = 2 \cdot 6 = 12$.
Coprimality and the totient before anything else.
$2024 = 168 \cdot 12 + 8$, so $11^{2024} \equiv 11^{8} \pmod{21}$.
The exponent reduced by $12$, not by $21$.
Squaring: $11^2 = 121 \equiv 16$, $11^4 \equiv 16^2 = 256 \equiv 4$, $11^{8} \equiv 4^2 = 16$. So the answer is $16$.
Three squarings for an exponent of two thousand.
Compute $5^{13} \bmod 21$. In binary $13 = 1101$, so $5^{13} = 5^{8} \cdot 5^{4} \cdot 5^{1}$.
The binary digits select which squares to use.
Build the squares modulo $21$: $5^{1} \equiv 5$, $5^{2} \equiv 4$, $5^{4} \equiv 16$, $5^{8} \equiv 16^{2} = 256 \equiv 4$.
Three squarings, each reduced.
Multiply the selected ones: $4 \cdot 16 \cdot 5 = 320 \equiv 320 - 15 \cdot 21 = 5 \pmod{21}$. Five multiplications in all, against twelve for the naive route — and the gap widens exponentially.
Cost grows with the number of digits of the exponent, not with the exponent.
The last digit is the residue modulo $10$, and $\varphi(10) = 4$ with $\gcd(7, 10) = 1$.
Name the modulus, then its totient.
$1001 = 250 \cdot 4 + 1$, so $7^{1001} \equiv 7^{1} \pmod{10}$.
The exponent reduces by $4$.
So the last digit is $7$. Checking the cycle confirms it: the last digits of the powers of $7$ run $7, 9, 3, 1$ and repeat every four.
You are computing $5^{202}$ modulo $22$. Put the steps into the order you carry them out.
Number the steps in order (write the number in the box):
What is $5^{202}$ modulo $21$?
Answer:
Working modulo $15$, give $2$, its square, and the square of that.
| Least residue | |
|---|---|
| $2^{1}$ | |
| $2^{2}$ | |
| $2^{4}$ |
Is this true: $2^{\varphi(4)} \equiv 1 \pmod 4$?
Working modulo $19$, match each power of $10$ to its least residue.
| $10$ | $5$ | $12$ | $6$ | |
|---|---|---|---|---|
| $10^{1}$ | ||||
| $10^{2}$ | ||||
| $10^{3}$ | ||||
| $10^{4}$ |
What are the last two digits of $11^{357}$?
last two digits a
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
You are computing $2^{404}$ modulo $15$. Put the steps into the order you carry them out.
Number the steps in order (write the number in the box):
You can compute a power with an enormous exponent modulo any number, by reducing the exponent and squaring repeatedly. Say in your own words which modulus the exponent reduces by, and what to do when the base shares a factor with the modulus. Next: a theorem about the product of all the units at once.
9. Your turn: find the last digit of $7^{1001}$, step 3