Abstract algebra and number theory
Introduced| English | Meaning |
|---|---|
| integral domain/ˈɪntɪɡrəl dəˈmeɪn/ | A commutative ring with identity distinct from zero and no zero divisors. |
| kernel/ˈkɜːnl/ | The set of elements sent to the identity. |
| zero divisor/ˈzɪərəʊ dɪˈvaɪzə/ | A nonzero element whose product with some nonzero element is zero. |
When division fails on a clock
- A clock calculation keeps only a remainder. Modulo 8, $3\cdot3\equiv1$, so multiplying by 3 undoes multiplication by 3. But $2x\equiv1\pmod8$ has no integer solution: an even number cannot differ from 1 by a multiple of 8.
- The available operations depend on the structure: group, ring, integral domain 整环 or field. Throughout, $\mathbb Z_n$ means integer residue classes modulo $n$, with $n\ge2$; use the stated operation.
A group needs an operation and inverses
- A group has a closed associative operation, an identity and an inverse for every element. Commutativity is an extra property, called abelian. Inverses are relative to the operation: additive inverses are negatives; multiplicative inverses are reciprocals.
- $(\mathbb Z,+)$ and $(\mathbb Q\setminus\{0\},\times)$ are groups. The integers under multiplication fail because 2 has no integer inverse; the nonzero residues modulo 8 fail even closure, since $2\cdot4\equiv0$.
Which is a group?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The others lack inverses (or closure).
Subgroups and element orders
- A nonempty subset $H$ of a group is a subgroup if $ab^{-1}\in H$ for every $a,b\in H$. For additive groups, check $a-b\in H$. The subgroup generated by one element is cyclic; its order is the number of distinct elements it contains.
- In $(\mathbb Z_6,+)$, the element 2 generates $\{0,2,4\}$ and has order 3. Lagrange's theorem says a subgroup's size divides the size of a finite group. A subset of a suitable size still needs the subgroup test: $\{0,1\}$ has size 2 but is not closed under addition modulo 6.
Group or not?
Check closure, associativity, identity and inverses for each set with its stated operation.
What is the order of the element 4 in the additive group $\mathbb Z_{12}$?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
The successive multiples are 4, 8, 0 modulo 12. The least positive number of additions returning to 0 is 3.
A student says that $\{0,1\}$ must be a subgroup of $(\mathbb Z_6,+)$ because 2 divides 6. Refute the claim and find a subgroup of order 2.
Lagrange gives a necessary size condition, not a subgroup test for an arbitrary subset. The proposed subset fails closure: $1+1=2$ modulo 6 is outside it. The set $\{0,3\}$ is a subgroup: it contains 0, $3+3=0$, and both elements have additive inverses in the set. Its order is 2.
A homomorphism preserves the operation
- A group homomorphism $\varphi:G\to H$ satisfies $\varphi(ab)=\varphi(a)\varphi(b)$. Its kernel 核 is the set of elements sent to the identity. Thus $\ker\varphi=\{g:\varphi(g)=e_H\}$; the image is the set of outputs actually reached.
- The homomorphism is injective exactly when its kernel is $\{e_G\}$. If $\varphi(a)=\varphi(b)$, then $\varphi(ab^{-1})=e_H$; a trivial kernel forces $a=b$. A nontrivial kernel instead sends different inputs to the same output.
A homomorphism is injective exactly when its ____ is trivial.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Only the identity maps to the identity.
Quotients collect inputs with the same output
- For a normal subgroup $N$ ($gNg^{-1}=N$ for all $g\in G$), the cosets $gN$ form a quotient group, with $(gN)(hN)=(gh)N$. Normality makes this independent of representatives. Every kernel $K$ is normal, and $gK\mapsto\varphi(g)$ gives $G/K\cong\operatorname{im}\varphi$.
- For reduction $\varphi:\mathbb Z_{12}\to\mathbb Z_4$, the kernel is $\{0,4,8\}$. Two residues have the same output exactly when their difference is in that kernel. There are four cosets of size 3, so $\mathbb Z_{12}/\ker\varphi\cong\mathbb Z_4$. In general the quotient matches the image, which need not be the whole codomain.
For reduction $\varphi:\mathbb Z_{12}\to\mathbb Z_4$, how many elements are in the kernel?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
The inputs sent to 0 modulo 4 are 0, 4 and 8. These are three distinct residues modulo 12.
Consider reduction $\psi:\mathbb Z_{18}\to\mathbb Z_6$. Show it is a well-defined additive homomorphism, find its kernel and image, and identify $\mathbb Z_{18}/\ker\psi$.
Representatives differing by a multiple of 18 also differ by a multiple of 6, so reduction is well-defined. Reduction preserves addition. The kernel is $\{0,6,12\}$ and every class modulo 6 occurs, so the image is $\mathbb Z_6$. The map from a kernel coset to its common output is an isomorphism, giving $\mathbb Z_{18}/\ker\psi\cong\mathbb Z_6$. There are six cosets of size 3.
Rings, zero divisors and fields
- A ring has an abelian additive group and associative multiplication distributing over addition; here it also has a multiplicative identity. An integral domain is a commutative ring with identity distinct from zero and no zero divisors. A zero divisor 零因子 is a nonzero element whose product with some nonzero element is zero.
- A field is a commutative ring with $1\ne0$ in which every nonzero element has a multiplicative inverse. Every field is a domain: if $ab=0$ and $a\ne0$, multiply by $a^{-1}$ to get $b=0$. The zero ring, where $1=0$, is excluded from both definitions.
Classify the structure, then calculate
- $\mathbb Z$ is a domain but not a field: 2 has no integer reciprocal. So is $\mathbb Q[x]$, the polynomial ring over the rationals: nonzero leading coefficients cannot multiply to zero, but the polynomial $x$ has no polynomial inverse.
- $\mathbb Z_6$ has $2\cdot3=0$ with both factors nonzero, so it is not a domain. For $n\ge2$, $\mathbb Z_n$ is a domain exactly when $n$ is prime; in that case it is a field. Composite moduli give nonzero factors of $n$ whose product is zero modulo $n$.
$\mathbb Z_7$ is an integral domain.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
For n ≥ 2, the ring $\mathbb Z_n$ has no nonzero zero divisors exactly when n is prime. Since 7 is prime, $\mathbb Z_7$ is a field and hence an integral domain.
Which ring is an integral domain under the convention that 1 and 0 are distinct?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
In $\mathbb Q[x]$, the product of nonzero polynomials has nonzero leading coefficient, so there are no zero divisors. In $\mathbb Z_6$, 2·3 = 0; in $\mathbb Z_4$, 2·2 = 0. The zero ring has 1 = 0.
Why a finite domain is a field
- Fix a nonzero $a$ in a finite integral domain $D$. The map $f(x)=ax$ is injective: $ax=ay$ gives $a(x-y)=0$, so $x=y$ because there are no zero divisors.
- An injective map from a finite set to itself is surjective. Hence some $x$ satisfies $ax=1$, giving an inverse for every nonzero $a$. Finiteness matters: multiplication by 2 on $\mathbb Z$ is injective but misses 1, so an infinite domain need not be a field.
Reconstruct the proof that every finite integral domain is a field. Explain separately why multiplication by 2 on $\mathbb Z$ and on $\mathbb Z_8$ cannot give the same conclusion.
For nonzero $a$ in a domain, $ax=ay$ implies $a(x-y)=0$, so $x=y$. Multiplication by $a$ is injective. On a finite domain, it is then surjective, so 1 has a preimage, giving an inverse of $a$. On $\mathbb Z$, multiplication by 2 is injective but not surjective because the set is infinite: 1 is missing. On $\mathbb Z_8$, the set is finite but there are zero divisors: $2\cdot0=2\cdot4=0$, so injectivity fails.
Find an inverse with Bézout's identity
- For integers $a$ and $n\ge2$, $a$ has an inverse modulo $n$ exactly when $\gcd(a,n)=1$. Bézout's identity writes this gcd as $ua+vn$; when it is 1, the coefficient $u$ is an inverse of $a$ modulo $n$.
- To invert 17 modulo 43, use $43=2\cdot17+9$, $17=9+8$, $9=8+1$. Back-substitution gives $1=2\cdot43-5\cdot17$, so the inverse is $-5\equiv38\pmod{43}$. Check: $17\cdot38=646=15\cdot43+1$.
Which residue has a multiplicative inverse modulo 9?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
$\gcd(4, 9) = 1$; $4 \cdot 7 = 28 \equiv 1$.
Find the least nonnegative inverse of 17 modulo 43.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Bézout gives 1 = 2·43 − 5·17. Thus −5, or 38 modulo 43, is the inverse. Direct check: 17·38 = 646 = 15·43 + 1.
A gcd counts the solutions
- For $ax\equiv b\pmod n$, let $d=\gcd(a,n)$. There are no solutions if $d\nmid b$. If $d\mid b$, there are exactly $d$ distinct solution classes modulo $n$; reduce to $(a/d)x\equiv b/d\pmod{n/d}$ and then lift back.
- For $6x\equiv9\pmod{15}$, $d=3$. The reduced equation $2x\equiv3\pmod5$ gives $x\equiv4\pmod5$. Lifting gives $x\equiv4,9,14\pmod{15}$: three classes, not one.
Find the least non-negative $x$ with $5x \equiv 3 \pmod 7$.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
$5 \cdot 2 = 10 \equiv 3$.
How many distinct solution classes modulo 15 satisfy $6x\equiv9\pmod{15}$?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
The gcd is 3, which divides 9. Dividing both sides and the modulus gives 2x ≡ 3 (mod 5), so x ≡ 4 (mod 5). The three classes modulo 15 are 4, 9 and 14.
Cancelling can change the modulus
- Cancelling an invertible factor keeps the modulus. In general, $ab\equiv ac\pmod n$ is equivalent to $b\equiv c\pmod{n/\gcd(a,n)}$. A common factor may be cancelled if the modulus is adjusted correctly.
- Thus $2x\equiv4\pmod8$ becomes $x\equiv2\pmod4$, giving the two classes $2,6$ modulo 8. Keeping modulus 8 after dividing would lose a solution. By contrast, $2x\equiv1\pmod8$ has no solution, since $\gcd(2,8)=2$ does not divide 1.

How many residue classes?
Count distinct solution classes modulo the stated modulus, using the gcd criterion.
Reduce powers only with the right hypotheses
- Euler's theorem gives $a^{\phi(n)}\equiv1\pmod n$ when $\gcd(a,n)=1$; $\phi(n)$ counts invertible residue classes. For prime $p$, Fermat gives $a^{p-1}\equiv1\pmod p$ if $p\nmid a$. The form $a^p\equiv a\pmod p$ holds for every integer $a$.
- Since $100=16\cdot6+4$, $3^{100}\equiv3^4\equiv4\pmod7$. Do not drop the coprimality condition: $\phi(8)=4$ but $2^4\equiv0\pmod8$, not 1.
Find the least nonnegative residue of $3^{100}$ modulo 7.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Since 7 is prime and does not divide 3, 3⁶ ≡ 1 (mod 7). Then 3¹⁰⁰ ≡ 3⁴ = 81 ≡ 4 (mod 7).
Combine congruences with compatible remainders
- The Chinese remainder theorem says that for coprime positive moduli $m,n$, any pair of remainders determines exactly one class modulo $mn$. For $x\equiv2\pmod3$ and $x\equiv3\pmod5$, write $x=2+3k$: $3k\equiv1\pmod5$, so $k\equiv2\pmod5$ and $x\equiv8\pmod{15}$.
- Without coprimality, check compatibility: remainders $a,b$ must agree modulo $\gcd(m,n)$. If they do, the combined class is unique modulo $\operatorname{lcm}(m,n)$, not necessarily $mn$. If they disagree, no integer satisfies both congruences.
Find the least nonnegative integer satisfying $x\equiv2\pmod3$ and $x\equiv3\pmod5$.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Write x = 2 + 3k. Modulo 5, 3k ≡ 1, so k ≡ 2 and x ≡ 8 (mod 15). Because 3 and 5 are coprime, this class is unique modulo 15.
Name the structure and keep the hypotheses
- Check the operation, identity and inverses before calling a set a group. Form quotient groups by normal subgroups; a homomorphism's quotient by its kernel matches its image. A finite domain is a field, but an infinite domain need not be.
- Before dividing or reducing a power, compute the gcd. Track the modulus when cancelling and lift all residue classes. For simultaneous congruences, check compatibility and report the correct combined modulus.
Solve $x\equiv2\pmod6$, $x\equiv5\pmod9$, giving all integers and the correct combined modulus. Then decide whether replacing the second remainder by 4 leaves any solution.
The gcd of 6 and 9 is 3, and remainders 2 and 5 agree modulo 3. Write $x=2+6k$. Then $6k\equiv3\pmod9$, so $2k\equiv1\pmod3$ and $k\equiv2\pmod3$. Thus $x=14+18t$ for $t\in\mathbb Z$, a unique class modulo $\operatorname{lcm}(6,9)=18$, not 54. Remainders 2 and 4 disagree modulo 3, so the changed pair has no solution.