Congruence modulo $n$ sorted the integers into $n$ residue classes. On this page we do arithmetic with the classes themselves: add them, multiply them, and (sometimes) divide them. It's the arithmetic a clock does when $11 + 3$ o'clock comes out as $2$, made precise. By the end, we'll find the last two digits of a number far too big to ever write down.
On Logic & Equivalence, Residue Rows wrapped $\mathbb{Z}$ into $n$ rows. Each row was one residue class, and the division algorithm picked out its representative $r$ with $0 \le r \le n - 1$.
From last time: for $n \in \mathbb{N}$ and $a, b \in \mathbb{Z}$, we define $$a \equiv b \pmod n \iff n \mid (a - b).$$ Congruence modulo $n$ is an equivalence relation on $\mathbb{Z}$, so it splits $\mathbb{Z}$ into equivalence classes, and there are exactly $n$ of them.
A complete set of distinct equivalence classes (residue classes) is $$\mathbb{Z}/n\mathbb{Z} = \{\overline{0}, \overline{1}, \overline{2}, \dots, \overline{n-1}\},$$ the integers modulo $n$. (We may also simply write $\mathbb{Z}/n\mathbb{Z} = \{0, 1, 2, \dots, n-1\}$.)
Why is it written $\mathbb{Z}/n\mathbb{Z}$? Here $n\mathbb{Z} = \{nk : k \in \mathbb{Z}\}$, and the residue class $\overline{a}$ is the set $a + n\mathbb{Z}$. On Quotient Groups, "$G/N$" will mean "the group of classes $g + N$," and $\mathbb{Z}/n\mathbb{Z}$ is the first example of one.
Before doing arithmetic with the classes, get a feel for them. Here is $\mathbb{Z}$ wrapping around a ring of $n$ classes.
Every integer lands in exactly one class, and each class keeps going forever in both directions. Negative numbers are no exception: $-1$ lands with $n - 1$. Now sort some yourself.
Keep in mind that each $\overline{a}$ is a whole infinite set. Modulo $5$, $\overline{2} = \{\dots, -8, -3, 2, 7, 12, \dots\}$. To add or multiply two infinite sets, the plan is simple: pick one member of each, do ordinary integer arithmetic, and take the class of the answer.
Addition modulo $n$: $\forall a, b \in \mathbb{Z}$, $\overline{a} + \overline{b} = \overline{a + b}$.
Multiplication works the same way.
Multiplication modulo $n$: $\forall a, b \in \mathbb{Z}$, $\overline{a} \cdot \overline{b} = \overline{a \cdot b}$.
Here is one computation done twice, with different representatives each time.
In $\mathbb{Z}/6\mathbb{Z}$, compute $\overline{4} + \overline{5}$ and $\overline{4} \cdot \overline{5}$, first with the representatives $4$ and $5$, then with $-2 \in \overline{4}$ and $11 \in \overline{5}$.
With $4$ and $5$: $4 + 5 = 9 \equiv 3$ and $4 \cdot 5 = 20 \equiv 2 \pmod 6$.
With $-2$ and $11$: $-2 + 11 = 9 \equiv 3$ and $(-2) \cdot 11 = -22 = -4 \cdot 6 + 2 \equiv 2 \pmod 6$.
Both times, $\overline{4} + \overline{5} = \overline{3}$ and $\overline{4} \cdot \overline{5} = \overline{2}$.
One more, modulo $5$: $\overline{3} + \overline{4} = \overline{7} = \overline{2}$ and $\overline{3} \cdot \overline{4} = \overline{12} = \overline{2}$. These two definitions raise some first questions:
The first question is the one that's easy to skip, and it's the most important. $\overline{3}$ is also $\overline{8}$ and $\overline{-2}$. If $\overline{3} + \overline{4}$ gave one class and $\overline{8} + \overline{4}$ gave another, "$+$" wouldn't be an operation on classes at all.
An operation on equivalence classes is well-defined if its answer does not depend on the representatives chosen. For addition mod $n$: if $\overline{a_1} = \overline{a_2}$ and $\overline{b_1} = \overline{b_2}$, then $\overline{a_1} + \overline{b_1} = \overline{a_2} + \overline{b_2}$.
Clocks have done mod $12$ arithmetic for centuries, and nobody ever made them prove it was well-defined.
Before proving anything, try to break it. Pick two classes, swap in different representatives, and see whether the answer ever lands in a different class. The third mode is a "fake" operation, $\overline{a}^{\,\overline{b}} := \overline{a^b}$, which looks just as reasonable as the other two.
Tap a representative in each class column. The ring lights up every class the answer has landed in.
Addition and multiplication never budge. The fake exponent breaks on the first try: modulo $5$, $\overline{1} = \overline{6}$, but $2^1 = 2$ and $2^6 = 64 \equiv 4$. So "well-defined" is a real condition that an operation can fail, and it needs a proof.
The same question comes up for rules from one $\mathbb{Z}/n\mathbb{Z}$ to another. Predict first, then let the widget try four representatives.
Swapping $a$ for $a + n$ moves $ka$ by $kn$, so the rule $f(\overline{a}) = \overline{ka}$ into $\mathbb{Z}/m\mathbb{Z}$ survives exactly when $m \mid kn$. Now invent a rule of your own and put it on the test bench.
A test can find a counterexample, but it can never prove that none exists. That takes a proof, and here is the first one.
Recall the definition: $\forall a, b \in \mathbb{Z}$, $\overline{a} + \overline{b} = \overline{a + b}$.
Addition modulo $n$ is well-defined.
Proof. Suppose $a_1, a_2, b_1, b_2 \in \mathbb{Z}$, $\overline{a_1} = \overline{a_2}$ and $\overline{b_1} = \overline{b_2}$. Then
$$\begin{align*}
a_1 &\equiv a_2 \pmod n \implies n \mid (a_1 - a_2) \implies a_1 - a_2 = nk \text{ for some } k \in \mathbb{Z} \\
b_1 &\equiv b_2 \pmod n \implies n \mid (b_1 - b_2) \implies b_1 - b_2 = nl \text{ for some } l \in \mathbb{Z}
\end{align*}$$
$\implies a_1 + b_1 = (a_2 + nk) + (b_2 + nl) = a_2 + b_2 + n(k + l)$
$\implies n \mid \big((a_1 + b_1) - (a_2 + b_2)\big) \implies a_1 + b_1 \equiv a_2 + b_2 \pmod n \implies \overline{a_1 + b_1} = \overline{a_2 + b_2}$. $\blacksquare$
Now that $+$ is a genuine binary operation on $\mathbb{Z}/n\mathbb{Z}$, we can ask whether it makes a group. That means three checks: the operation is associative, there's an identity, and everything has an inverse.
The next page, Groups & Basic Properties, makes "group" official: a set with an associative binary operation, an identity element, and an inverse for every element. $\mathbb{Z}/n\mathbb{Z}$ will be one of its main examples.
$(\mathbb{Z}/n\mathbb{Z}, +)$ is a group.
Proof. Each check is inherited from $\mathbb{Z}$.
Here is the whole group for $n = 4$ at once.
Write out the addition table of $\mathbb{Z}/4\mathbb{Z}$, and read off the inverse of each class.
Each entry is (row $+$ column) reduced mod $4$:
Each row has exactly one $0$, and its column is that row's inverse: $-0 = 0$, $-1 = 3$, $-2 = 2$, $-3 = 1$. The class $2$ is its own inverse, because $2 + 2 = 4 \equiv 0$.
Notice the diagonal stripes: each value slides one step left per row. The same picture works for every $n$.
It has two more properties worth naming.
On Groups of Order 1–3, $C_n$ is the cyclic group of order $n$, and its Power Wheel can label $C_n$ with $\mathbb{Z}/n\mathbb{Z}$. The second fact below is the reason that labeling works.
Furthermore, $(\mathbb{Z}/n\mathbb{Z}, +)$ is:
(For negative $k$, "$k$ copies of $\overline{1}$" means $|k|$ copies of $\overline{-1}$.) Inverses also give us subtraction for free.
Subtraction modulo $n$: $\overline{a} - \overline{b} = \overline{a} + (-\overline{b}) = \overline{a} + \overline{-b} = \overline{a + (-b)} = \overline{a - b}$.
Negative representatives are perfectly legal, and often the easiest ones to compute with. When you want an answer between $0$ and $n - 1$, add $n$.
$-3 \equiv 5 \pmod 8$, not $3$. Reduce a negative number by adding multiples of $n$ until you land in $\{0, \dots, n - 1\}$. Watch out for calculators and programming languages too: many of them report $-3 \bmod 8$ as $-3$.
Every class has exactly one additive inverse. Find them all on the ring.
When $n$ is even, $\frac{n}{2}$ is its own inverse, just like $2$ in $\mathbb{Z}/4\mathbb{Z}$. When $n$ is odd, only $0$ is.
Recall the definition: $\forall a, b \in \mathbb{Z}$, $\overline{a} \cdot \overline{b} = \overline{ab}$. The well-definedness proof has the same shape as before, with one more term to expand.
Multiplication modulo $n$ is well-defined.
Proof. Suppose $a_1, a_2, b_1, b_2 \in \mathbb{Z}$, $\overline{a_1} = \overline{a_2}$ and $\overline{b_1} = \overline{b_2}$. Then $a_1 - a_2 = nk$ and $b_1 - b_2 = nl$ for some $k, l \in \mathbb{Z}$. So $$\begin{align*} a_1 b_1 &= (a_2 + nk)(b_2 + nl) = a_2 b_2 + a_2 nl + b_2 nk + n^2 kl \\ &= a_2 b_2 + n(a_2 l + b_2 k + nkl) \end{align*}$$ $\implies n \mid (a_1 b_1 - a_2 b_2) \implies \overline{a_1 b_1} = \overline{a_2 b_2}$. $\blacksquare$
Repeated multiplication is safe too, as long as the exponent is an ordinary integer and not a class. That's exactly where the fake operation in the widget went wrong.
Fix an integer $k \ge 1$. Prove that $\overline{a}^{\,k} := \overline{a^k}$ is well-defined: if $\overline{a_1} = \overline{a_2}$, then $\overline{a_1^k} = \overline{a_2^k}$. Then explain why the widget's $\overline{a}^{\,\overline{b}} := \overline{a^b}$ is not well-defined.
Proof. Induction on $k$. For $k = 1$ there is nothing to prove. Suppose $\overline{a_1^k} = \overline{a_2^k}$. Since multiplication mod $n$ is well-defined, multiplying the equal classes $\overline{a_1^k} = \overline{a_2^k}$ by the equal classes $\overline{a_1} = \overline{a_2}$ gives $\overline{a_1^k a_1} = \overline{a_2^k a_2}$, that is, $\overline{a_1^{k+1}} = \overline{a_2^{k+1}}$. $\blacksquare$
For $\overline{a}^{\,\overline{b}}$, the representative of the exponent can change, and nothing above controls that. Modulo $5$, $\overline{1} = \overline{6}$, but $\overline{2^1} = \overline{2}$ while $\overline{2^6} = \overline{64} = \overline{4}$. Two representatives of the same class $\overline{b}$ give different answers.
From here on, writing bars over everything gets heavy, so we drop them.
We put bars on everything for a whole page just so we could take them off.
Notational convention: When working in $\mathbb{Z}/n\mathbb{Z}$, $a = \overline{a}$.
So is $(\mathbb{Z}/n\mathbb{Z}, \cdot)$ a group? Not if $n \ge 2$, and the culprit is easy to find.
Modulo $8$, the number $8$ is literally $0$. So I still can't divide by it. Even here.
(When $n = 1$, $0 = 1$ in $\mathbb{Z}/1\mathbb{Z} = \{0\}$, so the one-element set is a group. That's the only exception.) The fix is to throw out every element that has no inverse. Here is what that leaves for $n = 6$.
Which classes of $\mathbb{Z}/6\mathbb{Z}$ have a multiplicative inverse?
Multiply each class by all six classes and look for a $1$:
Only $1$ and $5$ have inverses (each is its own). The others, $0, 2, 3, 4$, all share a factor with $6$.
Keeping only the classes with an inverse gives the set we want.
Define $$(\mathbb{Z}/n\mathbb{Z})^\times = \{a \in \mathbb{Z}/n\mathbb{Z} : \exists b \in \mathbb{Z}/n\mathbb{Z} \text{ such that } ab \equiv 1 \pmod n\},$$ the primitive residue classes mod $n$, also called the units mod $n$.
Another way to spot the units: multiply the whole ring by $a$ and watch where everything goes.
A unit only shuffles the ring, so some class lands on $1$, and that class is its inverse. A non-unit crushes classes together and misses others, $1$ among them.
Throwing elements out can break an operation: the product of two survivors might be one of the elements we threw away. It isn't.
If $a_1, a_2 \in (\mathbb{Z}/n\mathbb{Z})^\times$, then $a_1 a_2 \in (\mathbb{Z}/n\mathbb{Z})^\times$. So multiplication, restricted to $(\mathbb{Z}/n\mathbb{Z})^\times$, is a binary operation.
Proof. If $a_1, a_2 \in (\mathbb{Z}/n\mathbb{Z})^\times$ then there are $b_1, b_2 \in \mathbb{Z}$ such that $a_1 b_1 \equiv 1 \pmod n$ and $a_2 b_2 \equiv 1 \pmod n$. Then $$(a_1 a_2)(b_1 b_2) = (a_1 b_1)(a_2 b_2) \equiv 1 \cdot 1 \equiv 1 \pmod n \implies a_1 a_2 \in (\mathbb{Z}/n\mathbb{Z})^\times. \quad \blacksquare$$
Now we can run the group checks again on the smaller set.
$((\mathbb{Z}/n\mathbb{Z})^\times, \cdot)$ is an Abelian group.
Proof.
Closure and the first group checks come for free. The last one is the reason we built $(\mathbb{Z}/n\mathbb{Z})^\times$ in the first place. From now on, each symbol below comes with its operation attached.
Notational conventions:
To find $(\mathbb{Z}/n\mathbb{Z})^\times$ by hand, go through the classes one at a time. Show each non-unit can't have an inverse, and find the inverse of each unit. Then ask which group you've got.
The Spicy Bonus on Groups of Order 1–3 proves there are exactly two groups of order $4$ (up to isomorphism): the cyclic one, $C_4$, and the one where every element squares to $e$, called $V_4$. A later page, Groups of Order 4–8, shows that order $6$ also has exactly two: $C_6$ and the non-Abelian $D_6$. Both facts are used below.
$n = 8$, $\mathbb{Z}/8\mathbb{Z} = \{0, 1, 2, 3, 4, 5, 6, 7\}$. Find $(\mathbb{Z}/8\mathbb{Z})^\times$ and its group structure.
$(\mathbb{Z}/8\mathbb{Z})^\times = \{1, 3, 5, 7\}$.
Scratch work:
Group structure: $|(\mathbb{Z}/8\mathbb{Z})^\times| = 4 \implies C_4$ or $V_4$. All elements of the group square to $1$, so it is not cyclic (the powers of any $g$ are just $1$ and $g$, never all four elements). Therefore $(\mathbb{Z}/8\mathbb{Z})^\times \cong V_4$.
Every unit mod $8$ is its own inverse. Mod $9$, the units pair up differently.
$n = 9$, $\mathbb{Z}/9\mathbb{Z} = \{0, 1, 2, 3, 4, 5, 6, 7, 8\}$. Find $(\mathbb{Z}/9\mathbb{Z})^\times$ and its group structure.
$(\mathbb{Z}/9\mathbb{Z})^\times = \{1, 2, 4, 5, 7, 8\}$.
Scratch work:
Group structure: $|(\mathbb{Z}/9\mathbb{Z})^\times| = 6 \implies (\mathbb{Z}/9\mathbb{Z})^\times \cong C_6$ or $D_6$. Since $(\mathbb{Z}/9\mathbb{Z})^\times$ is Abelian, $(\mathbb{Z}/9\mathbb{Z})^\times \cong C_6$.
Find a generator: $(\mathbb{Z}/9\mathbb{Z})^\times = \langle 2 \rangle$: $$2^1 = 2, \quad 2^2 = 4, \quad 2^3 = 8, \quad 2^4 = 7, \quad 2^5 = 5, \quad 2^6 = 1.$$
Notice the scratch work for $n = 9$ didn't check $0$, $3$, and $6$ one at a time. It used a single argument: anything sharing a factor with $9$ can't be a unit. That argument works for every $n$. Try one yourself.
Find $(\mathbb{Z}/12\mathbb{Z})^\times$. Is it isomorphic to $C_4$ or to $V_4$?
$0, 2, 3, 4, 6, 8, 9, 10$ each share a factor $d > 1$ with $12$, so the argument from Example 5 rules them out. The rest are units: $$1 \cdot 1 \equiv 5 \cdot 5 \equiv 7 \cdot 7 \equiv 11 \cdot 11 \equiv 1 \pmod{12}$$ ($25 = 2 \cdot 12 + 1$, $49 = 4 \cdot 12 + 1$, $121 = 10 \cdot 12 + 1$). So $(\mathbb{Z}/12\mathbb{Z})^\times = \{1, 5, 7, 11\}$.
It has order $4$, and every element squares to $1$, so it is not cyclic. Therefore $(\mathbb{Z}/12\mathbb{Z})^\times \cong V_4$.
Look at a whole multiplication table at once. A class $a$ is a unit exactly when its row contains a $1$. Look for which rows never contain one, and what those $a$ have in common with $n$.
Change $n$ with the arrows and tap any row. Rows that contain a $1$ are units. The switch shrinks the table down to $(\mathbb{Z}/n\mathbb{Z})^\times$.
A row with $\gcd(a, n) = d > 1$ only ever hits multiples of $d$, so it can never reach $1$. That's the whole theorem.
The second half of this proof is Bézout's lemma, used exactly as stated: when $\gcd(a, n) = 1$, there are integers with $ab + nk = 1$.
For $n \ge 2$, $$(\mathbb{Z}/n\mathbb{Z})^\times = \{1 \le a \le n-1 : \gcd(a, n) = 1\}.$$
Proof. Let $0 \le a \le n-1$, and write $d = \gcd(a, n)$.
Test the theorem on a few classes. Every drop shows the reason: an inverse, or a shared factor.
(For $a = 0$, $\gcd(0, n) = n > 1$, which is why the set starts at $1$. And $n \ge 2$ matters: in $\mathbb{Z}/1\mathbb{Z} = \{0\}$, the class $0$ is its own inverse.) The proof does more than say an inverse exists. Bézout's $b$ is the inverse, and the reverse Euclidean algorithm finds it.
Fast algorithm for computing $a^{-1} \pmod n$, when $\gcd(a, n) = 1$: (Reverse Euclidean algorithm) Run the Euclidean algorithm on $n$ and $a$, then run it in reverse to write $1 = ab + nk$. Then $a^{-1} \equiv b \pmod n$.
Here it is with a modulus too big for trial and error.
Let $n = 101$ (prime), $a = 45$. Compute $45^{-1} \pmod{101}$.
$$\begin{align*} 101 &= 2 \cdot 45 + 11 &&\implies 11 = 101 - 2 \cdot 45 \\ 45 &= 4 \cdot 11 + 1 &&\implies 1 = 45 - 4 \cdot 11 \\ 11 &= 11 \cdot 1 \end{align*}$$
So, $$\begin{align*} 1 &= 45 - 4 \cdot (101 - 2 \cdot 45) \\ &= 9 \cdot 45 - 4 \cdot 101 \end{align*}$$
$1 \equiv 9 \cdot 45 \pmod{101} \implies 45^{-1} \equiv 9 \pmod{101}$.
The inverse is the coefficient of $a$. The coefficient of $n$ gets thrown away, since $n \equiv 0$. Here is the same computation as a play-through, plus a few more.
Two habits keep this from going wrong.
Always check an inverse by multiplying: $45 \cdot 9 = 405 = 4 \cdot 101 + 1$. $\checkmark$ If the coefficient of $a$ comes out negative, add $n$ to get an answer between $0$ and $n - 1$. The negative one is still correct, just not reduced.
Checking is quick, so make it a habit. Work out an inverse on paper, then check it here.
Compute $7^{-1} \pmod{31}$.
$$\begin{align*} 31 &= 4 \cdot 7 + 3 &&\implies 3 = 31 - 4 \cdot 7 \\ 7 &= 2 \cdot 3 + 1 &&\implies 1 = 7 - 2 \cdot 3 \\ 3 &= 3 \cdot 1 \end{align*}$$
So $1 = 7 - 2(31 - 4 \cdot 7) = 9 \cdot 7 - 2 \cdot 31$, and $7^{-1} \equiv 9 \pmod{31}$. Check: $7 \cdot 9 = 63 = 2 \cdot 31 + 1$. $\checkmark$
Dividing by $a$ is multiplying by $a^{-1}$, so the question becomes: suppose $a, b \in \mathbb{Z}$. Is there a solution $x \in \mathbb{Z}$ to the equation $ax \equiv b \pmod n$? When $\gcd(a, n) = 1$, the inverse answers it: $x \equiv a^{-1}b$ works, since $a(a^{-1}b) \equiv (aa^{-1})b \equiv b \pmod n$. When $d = \gcd(a, n) > 1$ there is no inverse, but there is still a complete answer.
If $n \in \mathbb{N}$ and $a, b \in \mathbb{Z}$, then the equation $ax \equiv b \pmod n$ has a solution if and only if $d = \gcd(a, n) \mid b$.
Furthermore, if $d \mid b$ and $x_0 \in \mathbb{Z}$ is any integer satisfying $x_0 \equiv \left(\frac{a}{d}\right)^{-1} \left(\frac{b}{d}\right) \pmod{\frac{n}{d}}$, then the set of all solutions is $\{x_0 + \left(\frac{n}{d}\right)k : k \in \mathbb{Z}\}$.
Proof. ($\implies$) A solution $x$ gives $ax - b = nk$ for some $k \in \mathbb{Z}$, so $b = ax - nk$. Since $d \mid a$ and $d \mid n$, $d$ divides $ax - nk = b$.
($\impliedby$) If $d \mid b$, Bézout's lemma gives integers $u, v$ with $au + nv = d$. Multiplying by $\frac{b}{d}$ gives $a\left(u\frac{b}{d}\right) + n\left(v\frac{b}{d}\right) = b$, so $x = u\frac{b}{d}$ is a solution.
(The solution set.) Suppose $d \mid b$. Since $ax - b = d\left(\frac{a}{d}x - \frac{b}{d}\right)$ and $n = d \cdot \frac{n}{d}$, $$ax \equiv b \pmod n \iff n \mid (ax - b) \iff \tfrac{n}{d} \mid \left(\tfrac{a}{d}x - \tfrac{b}{d}\right) \iff \tfrac{a}{d}x \equiv \tfrac{b}{d} \pmod{\tfrac{n}{d}}.$$ Because $\gcd\left(\frac{a}{d}, \frac{n}{d}\right) = 1$, $\frac{a}{d}$ has an inverse mod $\frac{n}{d}$. Multiplying by it (or, going back, by $\frac{a}{d}$) shows that the last congruence holds exactly when $x \equiv \left(\frac{a}{d}\right)^{-1}\frac{b}{d} \equiv x_0 \pmod{\frac{n}{d}}$, that is, exactly when $x = x_0 + \frac{n}{d}k$ for some $k \in \mathbb{Z}$. $\blacksquare$
Read modulo $n$, that solution set is $d$ different classes spaced $\frac{n}{d}$ apart. So a congruence has no solutions, exactly one, or several, and $d$ tells you which. Watch it happen around a ring.
Set $a$, $b$, and $n$ with the arrows. Tap an $x$ in the strip to see where $ax$ lands on the ring.
Now predict before you look.
Now one with numbers big enough that the theorem has to do the work.
Determine the set of all solutions $x \in \mathbb{Z}$ to the equation $115x \equiv 69 \pmod{667}$.
Step 1: Compute $d = \gcd(115, 667)$: $$\begin{align*} 667 &= 5 \cdot 115 + 92 \\ 115 &= 1 \cdot 92 + 23 \\ 92 &= 4 \cdot 23 \implies d = 23. \end{align*}$$
Step 2: Since $23 \mid 69$, the equation has solutions. Now $\frac{115}{d} = 5$, $\frac{69}{d} = 3$, $\frac{667}{d} = 29$, so we want to compute $x_0 \equiv 5^{-1} \cdot 3 \pmod{29}$.
Step 3: To compute $5^{-1} \pmod{29}$, use the Euclidean algorithm: $$\begin{align*} 29 &= 5 \cdot 5 + 4 &&\implies 4 = 29 - 5 \cdot 5 \\ 5 &= 1 \cdot 4 + 1 &&\implies 1 = 5 - 1 \cdot 4 \\ 4 &= 4 \cdot 1 \end{align*}$$ Then use the reverse Euclidean algorithm: $$\begin{align*} 1 &= 5 - 1 \cdot 4 \\ &= 5 - 1 \cdot (29 - 5 \cdot 5) = 6 \cdot 5 - 1 \cdot 29 \end{align*}$$ This gives $6 \cdot 5 \equiv 1 \pmod{29} \implies 5^{-1} \equiv 6 \pmod{29}$.
Step 4: Then $x_0 \equiv 6 \cdot 3 \equiv 18 \pmod{29}$, so the set of all solutions is $\{18 + 29k : k \in \mathbb{Z}\}$.
Check: $115 \cdot 18 = 2070 = 69 + 3 \cdot 667$. $\checkmark$
The step that's easy to forget is the one that changes the modulus.
When you divide $a$ and $b$ by $d$, divide $n$ by $d$ too. The answer to $115x \equiv 69$ is "$x \equiv 18 \pmod{29}$", not "$x \equiv 18 \pmod{667}$". Modulo $667$, that's $23$ different solutions: $18, 47, 76, \dots$ Reporting only one of them misses $22$.
Here is the whole recipe on a ring, including the step that changes the modulus.
Find all solutions to $12x \equiv 18 \pmod{30}$. Then show that $12x \equiv 20 \pmod{30}$ has no solutions.
$d = \gcd(12, 30) = 6$, and $6 \mid 18$, so solutions exist. Dividing by $6$: $2x \equiv 3 \pmod 5$. Since $2 \cdot 3 = 6 \equiv 1 \pmod 5$, $2^{-1} \equiv 3$, so $x_0 \equiv 3 \cdot 3 = 9 \equiv 4 \pmod 5$.
The set of all solutions is $\{4 + 5k : k \in \mathbb{Z}\}$ (six classes mod $30$: $4, 9, 14, 19, 24, 29$). Check: $12 \cdot 4 = 48 = 18 + 30$. $\checkmark$
For the second equation, $d = 6 \nmid 20$, so by the theorem there is no solution. (Directly: $12x - 30k$ is always a multiple of $6$, and $20$ isn't.)
The rest of this page is four important results, stated without proof, for now. Most of the proofs need group theory we haven't built yet. We'll still use them right away, because they turn impossible-looking computations into a few lines. The first one counts the units.
The Euler phi function is $\varphi(n) = |(\mathbb{Z}/n\mathbb{Z})^\times|$.
The count in Unit Finder was $\varphi(n)$ all along. By the theorem above, $\varphi(n)$ counts the $a$ between $1$ and $n - 1$ that are relatively prime to $n$. You don't have to list them, because $\varphi(n)$ can be read off the prime factorization.
If $n = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}$, for distinct primes $p_1, \dots, p_k$ and for $\alpha_1, \dots, \alpha_k \in \mathbb{N}$, then $$\begin{align*} \varphi(n) &= (p_1 - 1)p_1^{\alpha_1 - 1} \cdot (p_2 - 1)p_2^{\alpha_2 - 1} \dots (p_k - 1)p_k^{\alpha_k - 1} \\ &= \prod_{i=1}^k (p_i - 1)p_i^{\alpha_i - 1} \end{align*}$$
For a small $n$, the formula and a list agree.
Find $\varphi(12)$ by listing the units, then by the formula.
Listing: the $a$ with $1 \le a \le 11$ and $\gcd(a, 12) = 1$ are $1, 5, 7, 11$, so $\varphi(12) = 4$.
Formula: $12 = 2^2 \cdot 3$, so $\varphi(12) = (2 - 1) \cdot 2^1 \cdot (3 - 1) \cdot 3^0 = 2 \cdot 2 = 4$. $\checkmark$
There are two more ways to use it.
The second form reads like a sieve. Out of $n$ numbers, cross off the multiples of $2$ (half of them), then the multiples of $3$ (a third of what's left), and so on for each prime dividing $n$. Watch it run.
For a prime, the sieve has almost nothing to do.
If $p$ is prime, find $|(\mathbb{Z}/p\mathbb{Z})^\times|$.
$|(\mathbb{Z}/p\mathbb{Z})^\times| = \varphi(p) = p - 1$. (Every nonzero class is a unit.)
That one could be done without the formula. This one can't, at least not quickly.
$n = 9000 = 2^3 \cdot 3^2 \cdot 5^3$. Find $|(\mathbb{Z}/n\mathbb{Z})^\times|$.
$$\begin{align*} |(\mathbb{Z}/n\mathbb{Z})^\times| &= \varphi(n) = 9000 \cdot \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right)\left(1 - \frac{1}{5}\right) \\ &= 9000 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 2400 \end{align*}$$
A trap to avoid: the formula needs the distinct primes, each counted once.
$\varphi(8) \neq \varphi(2)\varphi(2)\varphi(2) = 1$. The rule $\varphi(mn) = \varphi(m)\varphi(n)$ needs $\gcd(m, n) = 1$. Use the prime-power piece instead: $\varphi(2^3) = (2 - 1) \cdot 2^2 = 4$, which matches $\{1, 3, 5, 7\}$.
Why does the rule need $\gcd(m, n) = 1$? Put each $x$ from $0$ to $mn - 1$ in a grid by its remainders mod $m$ and mod $n$ (the same grid comes back in the CRT section).
Compute $\varphi(360)$.
$360 = 2^3 \cdot 3^2 \cdot 5$, so $$\varphi(360) = (2 - 1)2^2 \cdot (3 - 1)3^1 \cdot (5 - 1)5^0 = 4 \cdot 6 \cdot 4 = 96.$$ Or: $360 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 96$.
Powers mod $n$ eventually come back around to $1$. For a prime modulus, Fermat tells you exactly when.
Fermat's (little) theorem: If $p$ is prime, $a \in \mathbb{Z}$, and $p \nmid a$, then $a^{p-1} \equiv 1 \pmod p$.
(Also stated as: $\forall a \in \mathbb{Z}$, $a^p \equiv a \pmod p$.)
A small case first, and a look at why the hypothesis $p \nmid a$ is there.
Check Fermat's theorem for $p = 7$ and $a = 3$. Then try $a = 14$.
$3^2 = 9 \equiv 2$, $3^3 \equiv 2 \cdot 3 = 6$, and $3^6 = (3^3)^2 \equiv 6^2 = 36 \equiv 1 \pmod 7$. $\checkmark$
But $7 \mid 14$, and $14^6 \equiv 0^6 = 0 \pmod 7$, not $1$. That's why the theorem asks for $p \nmid a$. The other form still holds: $14^7 \equiv 0 \equiv 14 \pmod 7$.
Slide the exponent and watch the powers come back around.
So exponents only matter modulo $p - 1$. Reduce the exponent first, then compute what's left by repeated squaring, which needs only a handful of multiplications.
Compute $43^{2023} \pmod{103}$.
Step 1: $103$ is prime, and $103 \nmid 43$, so $43^{102} \equiv 1 \pmod{103}$. Write $2023 = 19 \cdot 102 + 85$, so that $$43^{2023} = 43^{19 \cdot 102 + 85} = (43^{102})^{19} \cdot 43^{85} \equiv 1^{19} \cdot 43^{85} \equiv 43^{85} \pmod{103}.$$
Step 2: Compute $43^{85} \pmod{103}$. (Use the square and multiply algorithm.)
Conclusion: $43^{2023} \equiv 57 \pmod{103}$.
Here is Step 2 as a play-through.
Two habits made that work: switching to negative representatives ($98 \equiv -5$) to keep the numbers small, and reducing after every single multiplication. Fermat's theorem only works for a prime modulus. Euler's theorem works for any modulus, with $\varphi(n)$ playing the role of $p - 1$.
Euler's theorem: If $n \in \mathbb{N}$ and $a \in \mathbb{Z}$ satisfies $\gcd(a, n) = 1$, then $a^{\varphi(n)} \equiv 1 \pmod n$.
When $n$ is prime, $\varphi(n) = n - 1$, so this reduces to Fermat's theorem. And there's an even more general result hiding behind both.
If $G$ is a finite group, then $\forall g \in G$, $g^{|G|} = e$. Euler's theorem is the case $G = (\mathbb{Z}/n\mathbb{Z})^\times$, where $|G| = \varphi(n)$. The proof comes from Lagrange's theorem, which is why this page states these results without proof for now.
The RSA encryption mentioned on Properties of Integers runs on Euler's theorem. A message is encrypted by raising it to a power mod $n$, and Euler's theorem is why raising the result to a second, secret power gets the message back.
The hypothesis $\gcd(a, n) = 1$ can't be dropped.
Does Euler's theorem hold for $a = 2$ and $n = 10$?
No. $\varphi(10) = 4$, but $2^4 = 16 \equiv 6 \pmod{10}$. In fact no power $2^k$ with $k \ge 1$ is $\equiv 1 \pmod{10}$: $2^k$ is even, so $2^k - 1$ is odd, and $10$ can't divide it. Since $\gcd(2, 10) = 2$, the class $2$ is not a unit, and its powers never come back to $1$.
The classic use is finding the last digits of a huge power. "Units digit" just means "modulo $10$."
Find the units digit of $43^{2023}$.
Let $n = 10 = 2^1 \cdot 5^1$. Then $\gcd(43, n) = 1$ and $\varphi(n) = (2-1)(5-1) = 4$, so $43^4 \equiv 1 \pmod{10}$. $$\implies 43^{2023} = 43^{4 \cdot 505 + 3} = (43^4)^{505} \cdot 43^3 \equiv 1^{505} \cdot 3^3 \equiv 27 \equiv 7 \pmod{10}$$ So, the units digit is $7$.
Now the showpiece. Graham's number is a tower of $3$s so tall that the universe doesn't have room to write it down, but we can still find its last two digits. The idea is to apply Euler's theorem once for each level of the tower, with a smaller modulus each time.
Find the tens and units digits of "Graham's number": $g = 3^{3^{3^{\dots}}}$.
Idea: We are trying to compute $g \pmod{100}$, with $a = 3$, $b_1 = 3^{3^{3^{\dots}}}$, and $n = 100 = 2^2 \cdot 5^2$. Since $\gcd(a, n) = 1$ and $\varphi(n) = 2(2-1) \cdot 5(5-1) = 40$, we should try to write $b_1 = q_1 \cdot 40 + r_1$ with $0 \le r_1 \le 39$. In other words, we want to determine $b_1 \pmod{40}$. Then repeat one level up.
Now work back up: $$\begin{align*} \implies b_3 &\equiv 3^{4q_4 - 1} = (3^4)^{q_4} \cdot 3^{-1} \equiv 1 \cdot 3^{-1} \equiv 3 \pmod 8 \\ \implies b_2 &\equiv 3^{8q_3 + 3} = (3^8)^{q_3} \cdot 3^3 \equiv 1 \cdot 27 \equiv 11 \pmod{16} \\ \implies b_1 &\equiv 3^{16q_2 + 11} = (3^{16})^{q_2} \cdot 3^{11} \equiv 27 \pmod{40} \\ \implies g &\equiv 3^{40q_1 + 27} = (3^{40})^{q_1} \cdot 3^{27} \equiv 3^{27} \pmod{100} \end{align*}$$ $3^{27} = 3^1 \cdot 3^2 \cdot 3^8 \cdot 3^{16} \equiv 3 \cdot 9 \cdot 61 \cdot 21 \equiv 87 \pmod{100}$.
Answer: $g = \dots 87$.
Two details in there are worth a second look. The $3^{-1}$ in the first line back up makes sense because we're working in the group $(\mathbb{Z}/8\mathbb{Z})^\times$, where $3 \cdot 3 \equiv 1$. And the moduli shrink, $100 \to 40 \to 16 \to 8 \to 4$, which is why the tower can be stopped after a few levels. Here is the whole descent and climb as a play-through, for $3$ and for other bases.
Find the units digit of $7^{2026}$.
$\gcd(7, 10) = 1$ and $\varphi(10) = 4$, so $7^4 \equiv 1 \pmod{10}$. Write $2026 = 4 \cdot 506 + 2$. Then $$7^{2026} = (7^4)^{506} \cdot 7^2 \equiv 1^{506} \cdot 49 \equiv 9 \pmod{10}.$$ The units digit is $9$.
We saw that $(\mathbb{Z}/9\mathbb{Z})^\times$ is cyclic and $(\mathbb{Z}/8\mathbb{Z})^\times$ is not. Which moduli give a cyclic group? There's a complete (and slightly strange) answer.
Primitive root theorem: For $n \in \mathbb{N}$, the group $(\mathbb{Z}/n\mathbb{Z})^\times$ is cyclic if and only if $n = 1, 2, 4, p^k$ or $2p^k$ with $p$ an odd prime and $k \in \mathbb{N}$.
Sort some $n$ by the theorem. Factor each one first.
So $9 = 3^2$ makes the list and $8 = 2^3$ doesn't. When the group is cyclic, its generators get a special name.
If $(\mathbb{Z}/n\mathbb{Z})^\times$ is cyclic, then any generator for the group is called a primitive root modulo $n$.
To test whether $a$ is a primitive root, keep multiplying by $a$ until you get back to $1$. If every unit showed up along the way, it's a primitive root. Try it below.
Choose $n$, tap a unit $a$ on the ring, then press "× a" to hop from $a^k$ to $a^{k+1}$. If the orbit visits every unit before returning to $1$, $a$ is a primitive root.
Here are three examples, starting with orbits you can check in the widget.
$n = 7$: $(\mathbb{Z}/7\mathbb{Z})^\times$ is cyclic. Which of $2$ and $3$ are primitive roots?
$\langle 2 \rangle = \{1, 2, 4\}$, and $\langle 3 \rangle = (\mathbb{Z}/7\mathbb{Z})^\times \implies 3$ is a primitive root.
Scratch work: $$\begin{align*} 2^{3j} &= 2^0 = 1 & 3^0 &= 1 \\ 2^{3j+1} &= 2^1 = 2 & 3^1 &= 3 \\ 2^{3j+2} &= 2^2 = 4 & 3^2 &= 2 \\ & & 3^3 &= 6 \\ & & 3^4 &= 4 \\ & & 3^5 &= 5 \end{align*}$$
Note: $5$ is also a primitive root, but $1, 4$, and $6$ are not.
The same orbits, drawn as polygons: a primitive root's path runs through every unit before it closes.
We already found one generator mod $9$ in the Two Examples section.
$n = 9$: find all primitive roots.
$(\mathbb{Z}/9\mathbb{Z})^\times = \langle 2 \rangle$ (from Example 5).
Primitive roots mod 9: $2, 5$.
Non-primitive roots mod 9: $1, 4, 7, 8$.
The payoff of a primitive root is that it turns multiplication into addition of exponents. An equation about powers mod $103$ becomes a linear congruence mod $102$, which the Division section already knows how to solve.
Given that $5$ is a primitive root modulo $103$, find all residue classes $x \pmod{103}$ which satisfy $x^3 \equiv 1 \pmod{103}$.
(Note: $|(\mathbb{Z}/103\mathbb{Z})^\times| = \varphi(103) = 102$.)
Write $g = 5$. Then $(\mathbb{Z}/103\mathbb{Z})^\times = \{g^0, g^1, g^2, \dots, g^{101}\}$.
It is not difficult to show, using the division algorithm, that $g^j \equiv 1 \pmod{103} \iff j = 102k$ for some $k \in \mathbb{Z}$ $(j \equiv 0 \pmod{102})$.
Any solution of $x^3 \equiv 1$ is a unit, since $x \cdot x^2 \equiv 1$. So every solution has the form $x = g^m$, for some $0 \le m \le 101$, and we have: $$\begin{align*} x^3 \equiv g^{3m} \equiv 1 \pmod{103} &\iff 3m \equiv 0 \pmod{102} \\ &\iff m \equiv 0 \pmod{\left(\tfrac{102}{3}\right)} \\ &\iff m \equiv 0 \pmod{34}. \end{align*}$$ Thus $m = 0, 34$, or $68$.
Therefore there are three solutions mod 103: $$\begin{align*} x &= g^0 \equiv 1 \pmod{103}, \\ x &= g^{34} = 5^{34} = \dots \equiv 56 \pmod{103}, \text{ and} \\ x &= g^{68} = 5^{68} = \dots \equiv 46 \pmod{103}. \end{align*}$$
The step $3m \equiv 0 \pmod{102} \iff m \equiv 0 \pmod{34}$ is the Division theorem with $d = \gcd(3, 102) = 3$. The two "$\dots$" are square and multiply, exactly as in the Fermat example. Drag through the exponents below to see the same trick for a smaller prime.
Show that $2$ is a primitive root modulo $11$. Then find all $x \pmod{11}$ with $x^5 \equiv 1 \pmod{11}$.
The powers of $2$ mod $11$ are $$2^0, 2^1, \dots, 2^9 \equiv 1, 2, 4, 8, 5, 10, 9, 7, 3, 6,$$ which is all ten units, so $2$ is a primitive root.
Write $x = 2^m$ with $0 \le m \le 9$. Then $x^5 = 2^{5m} \equiv 1 \iff 5m \equiv 0 \pmod{10} \iff m \equiv 0 \pmod 2$. So $m = 0, 2, 4, 6, 8$, giving $$x \equiv 1, 4, 5, 9, 3 \pmod{11}.$$ (Check one: $4^5 = 1024 = 93 \cdot 11 + 1$. $\checkmark$)
The last result is about solving several congruences at once, each with its own modulus. If the moduli share no factors, there's always exactly one answer.
Chinese remainder theorem (CRT): If $n_1, \dots, n_k \in \mathbb{N}$ satisfy $\gcd(n_i, n_j) = 1$, $\forall i \neq j \le k$ (pairwise relatively prime), then $\forall a_1, \dots, a_k \in \mathbb{Z}$, there is an integer $x \in \mathbb{Z}$ such that $$\begin{align*} x &\equiv a_1 \pmod{n_1} \\ x &\equiv a_2 \pmod{n_2} \\ &\vdots \\ x &\equiv a_k \pmod{n_k} \end{align*}$$ and this integer $x$ is unique mod $(n_1 n_2 \dots n_k)$.
For two moduli there's a picture. Make a grid with a row for each remainder mod $n_1$ and a column for each remainder mod $n_2$, and put each $x$ in the cell $(x \bmod n_1, x \bmod n_2)$. As $x$ counts up, it walks diagonally and wraps around the edges. The CRT says that when $\gcd(n_1, n_2) = 1$, the first $n_1 n_2$ values of $x$ fill every cell exactly once.
Set $n_1$ and $n_2$, then press STEP to place the next $x$. Tap any cell to ask which $x$ lands there.
For small moduli, walking through the candidates works fine.
$k = 2$, $n_1 = 10$, $n_2 = 21$, $a_1 = 7$, $a_2 = 3$. Solve the system.
$\gcd(n_1, n_2) = 1$, and we are looking for an integer $x$ satisfying $x \equiv 7 \pmod{10}$ and $x \equiv 3 \pmod{21}$.
Trial and error (numbers $\equiv 3 \pmod{21}$): $\dots, 24, 45, 66, 87, \dots$, and $87$ is the first one ending in $7$.
Therefore, the set of all solutions is $\{87 + 210m : m \in \mathbb{Z}\}$.
Trial and error is just turning two clocks at once. Try it.
The moduli really do need to be relatively prime.
Solve $x \equiv 0 \pmod 4$ and $x \equiv 1 \pmod 6$.
There is no solution. Here $\gcd(4, 6) = 2$: the first congruence makes $x$ even, and the second makes $x = 1 + 6k$ odd. With a common factor, the two congruences can contradict each other mod $2$.
When they don't, as with $x \equiv 0 \pmod 4$ and $x \equiv 2 \pmod 6$ (solutions $8, 20, 32, \dots$), the solution is only unique mod $\operatorname{lcm}(4, 6) = 12$, not mod $24$.
For bigger moduli, you can build the answer directly out of inverses.
A "faster" way to find an integer $x$ satisfying the system of equations in the CRT for $k = 2$:
Each term is built to vanish modulo one of the moduli and equal the right remainder modulo the other. Here it is on a system you'd rather not do by trial and error.
$k = 2$, $n_1 = 15$, $n_2 = 37$, $a_1 = 8$, $a_2 = 27$. Solve $x \equiv 8 \pmod{15}$, $x \equiv 27 \pmod{37}$.
Compute: $m_1 \equiv 15^{-1} \pmod{37}$: $$\begin{align*} 37 &= 2 \cdot 15 + 7 &&\implies 7 = 37 - 2 \cdot 15 \\ 15 &= 2 \cdot 7 + 1 &&\implies 1 = 15 - 2 \cdot 7 \\ 7 &= 7 \cdot 1 \end{align*}$$ $1 = 15 - 2 \cdot (37 - 2 \cdot 15) = 5 \cdot 15 - 2 \cdot 37$.
Thus $1 \equiv 5 \cdot 15 \pmod{37} \implies m_1 = 5$, and $1 \equiv -2 \cdot 37 \pmod{15} \implies m_2 = -2$.
Finally: $$\begin{align*} x &= 15 \cdot m_1 \cdot 27 + 37 \cdot m_2 \cdot 8 \pmod{15 \cdot 37} \\ &= 15 \cdot 5 \cdot 27 + 37 \cdot (-2) \cdot 8 \pmod{555} \\ &\equiv 2025 - 592 \equiv 1433 \equiv 323 \pmod{555}. \end{align*}$$
Notice that one run of the reverse Euclidean algorithm gave both inverses at once. That always happens.
Comment: When you already know $m_1 \equiv n_1^{-1} \pmod{n_2}$, no matter how you found it, there is always a shortcut to compute $m_2 \equiv n_2^{-1} \pmod{n_1}$: $$n_1 m_1 \equiv 1 \pmod{n_2} \implies n_1(-m_1) \equiv -1 \pmod{n_2}$$ So $n_1(-m_1) + 1 = n_2 k \implies k = \frac{n_1(-m_1) + 1}{n_2} \equiv n_2^{-1} \pmod{n_1}$. (In Example 21: $k = \frac{15 \cdot (-5) + 1}{37} = -2$.)
With more than two congruences, combine them two at a time.
For $k \ge 3$: First find an integer $x_1$ satisfying $x_1 \equiv a_1 \pmod{n_1}$ and $x_1 \equiv a_2 \pmod{n_2}$. (Note that $x_1$ is unique mod $n_1 n_2$.)
Next, find $x_2 \in \mathbb{Z}$ satisfying $x_2 \equiv x_1 \pmod{n_1 n_2}$ and $x_2 \equiv a_3 \pmod{n_3}$.
Finally find $x = x_{k-1}$ satisfying $x_{k-1} \equiv x_{k-2} \pmod{n_1 n_2 \dots n_{k-1}}$ and $x_{k-1} \equiv a_k \pmod{n_k}$.
Example 21 turns out to be the middle step of a bigger one.
$k = 4$, $n_1 = 3$, $n_2 = 5$, $n_3 = 37$, $n_4 = 101$, $a_1 = 2$, $a_2 = 3$, $a_3 = 27$, $a_4 = 81$.
Set of all solutions: $\{44723 + 56055 \cdot m : m \in \mathbb{Z}\}$.
The CRT also works in reverse. A congruence modulo a composite $n$ splits into congruences modulo its prime-power pieces. Solve each piece separately, then glue the answers back together.
Let $n = 605 = 5 \cdot 11^2$. Find all residue classes $x \pmod n$ which satisfy the equation $x^2 \equiv 1 \pmod n$.
Observation (CRT): $x^2 \equiv 1 \pmod n \iff x^2 \equiv 1 \pmod 5$ and $x^2 \equiv 1 \pmod{11^2}$.
Plan: Find all $a_1 \pmod 5$ with $a_1^2 \equiv 1 \pmod 5$ and all $a_2 \pmod{121}$ with $a_2^2 \equiv 1 \pmod{121}$, then combine all pairs of solutions $(a_1 \pmod 5, a_2 \pmod{121}) \implies (x \pmod n)$ using the CRT.
Fact: If $p \ge 3$ is prime and $k \in \mathbb{N}$, then the only solutions to $x^2 \equiv 1 \pmod{p^k}$ are $x \equiv \pm 1 \pmod{p^k}$.
Proof. $x^2 \equiv 1 \pmod{p^k} \implies p^k \mid (x^2 - 1) = (x - 1)(x + 1) \implies p^k \mid (x - 1)$ or $p^k \mid (x + 1)$. ($p$ is prime and $\ge 3$, so it can't divide both $x - 1$ and $x + 1$, which differ by $2$. So all $k$ factors of $p$ land in the same one.) $\blacksquare$
Using the fact: $a_1^2 \equiv 1 \pmod 5 \implies a_1 \equiv \pm 1 \pmod 5$, and $a_2^2 \equiv 1 \pmod{121} \implies a_2 \equiv \pm 1 \pmod{121}$.
4 cases ($n_1 = 5$, $n_2 = 121$, $n = n_1 n_2 = 605$):
So, there are 4 solutions mod 605 to $x^2 \equiv 1 \pmod{605}$: $x \equiv 1, 241, 364$, and $604 \pmod{605}$.
Four square roots of $1$, not two. In $\mathbb{Z}$, $x^2 = 1$ only has $x = \pm 1$, but modulo a number with two different prime factors, the CRT lets you choose the sign separately for each one. Pick the signs yourself.
Your turn to solve a system.
Solve $x \equiv 2 \pmod 7$, $x \equiv 3 \pmod{10}$ using the "faster" method.
$n_1 = 7$, $n_2 = 10$, $a_1 = 2$, $a_2 = 3$. Since $7 \cdot 3 = 21 \equiv 1 \pmod{10}$, $m_1 = 3$. By the shortcut, $m_2 = \frac{7 \cdot (-3) + 1}{10} = -2$ (check: $10 \cdot (-2) = -20 \equiv 1 \pmod 7$).
$$x = 7 \cdot 3 \cdot 3 + 10 \cdot (-2) \cdot 2 = 63 - 40 = 23.$$
The set of all solutions is $\{23 + 70m : m \in \mathbb{Z}\}$. Check: $23 = 3 \cdot 7 + 2$ and $23 = 2 \cdot 10 + 3$. $\checkmark$
Every question below makes a new version each time you press the button, in the same order as the lesson. Every wrong choice is a real mistake, and choosing one tells you which.
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
Loading practice engine...
The units mod $n$ formed a group because we threw out everything without an inverse. When do we only have to throw out $0$? The Unit Finder hinted at the answer.
Let $n \in \mathbb{N}$. Prove that $(\mathbb{Z}/n\mathbb{Z} \setminus \{0\}, \cdot)$ is a group if and only if $n$ is prime.
Proof. ($\impliedby$) Suppose $n = p$ is prime. If $1 \le a \le p - 1$, then $\gcd(a, p)$ is a positive divisor of $p$ smaller than $p$, so $\gcd(a, p) = 1$. By the theorem on $(\mathbb{Z}/n\mathbb{Z})^\times$, $\mathbb{Z}/p\mathbb{Z} \setminus \{0\} = (\mathbb{Z}/p\mathbb{Z})^\times$, which we proved is a group.
($\implies$) Suppose $n$ is not prime. If $n = 1$, then $\mathbb{Z}/1\mathbb{Z} \setminus \{0\} = \emptyset$, which has no identity element, so it is not a group. Otherwise $n = cd$ with $1 < c, d < n$. Then $c, d \in \mathbb{Z}/n\mathbb{Z} \setminus \{0\}$, but $c \cdot d = n \equiv 0$. So multiplication is not even a binary operation on $\mathbb{Z}/n\mathbb{Z} \setminus \{0\}$, and it is not a group. $\blacksquare$
Moral: modulo a prime, you can divide by anything except $0$, exactly as in $\mathbb{Q}$ or $\mathbb{R}$. That makes $\mathbb{Z}/p\mathbb{Z}$ our first example of a finite field.