Congruences, divisibility and arithmetic functions
Introduced| English | Meaning |
|---|---|
| congruence/ˈkɒŋɡruːəns/ | A statement that two integers have the same remainder modulo a specified positive integer. |
| Chinese remainder theorem/tʃaɪˈniːz rɪˈmeɪndə ˈθɪərəm/ | The result that congruences with pairwise coprime moduli have exactly one common residue class modulo the product of their moduli. |
| totient/ˈtəʊʃənt/ | The number of residue classes coprime to the modulus. |
When cycles line up
- One gear repeats every $4$ minutes, another every $7$. Being at position $2$ on the first cycle and $3$ on the second means finding a time $x$ with $x\equiv2\pmod4$ and $x\equiv3\pmod7$.
- Congruences 同余 describe repeated positions. The Chinese remainder theorem 中国剩余定理 combines them; gcd tests, modular inverses and prime exponents tell us which algebraic steps are valid.
Congruence means divisibility
- A congruence is a statement that two integers have the same remainder modulo a specified positive integer. Here all variables are integers and moduli satisfy $n\geq2$; $a\equiv b\pmod n$ means exactly that $n$ divides $a-b$.
- For $ax\equiv b\pmod n$, put $d=\gcd(a,n)$. Any solution gives $ax-b=kn$ for some integer $k$. Since $d$ divides both $a$ and $n$, it must divide $b$; if $d\nmid b$, there is no solution.
Why the gcd also counts solutions
- The condition $d\mid b$ is sufficient too. Bézout gives integers $u,v$ with $ua+vn=d$; multiplying by $b/d$ shows that $x=u(b/d)$ is a solution of the original congruence.
- If $d<n$, divide the coefficient, target and modulus by $d$. The reduced coefficient is invertible modulo $n/d$, giving one class $x\equiv x_0\pmod{n/d}$. Its lifts are $x_0+k(n/d)$ for $k=0,\ldots,d-1$: exactly $d$ distinct residues modulo $n$. The case $d=n$ is handled separately below.
How many solutions modulo 20 does $8x \equiv 12 \pmod{20}$ have?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
The gcd is 4 and divides 12, so there are four residues modulo 20. Reducing gives 2x ≡ 3 (mod 5), hence x ≡ 4 (mod 5). The four lifts are 4, 9, 14 and 19 modulo 20.
Reduce, solve and lift
- For $6x\equiv9\pmod{15}$, the gcd is $3$ and divides $9$. Divide all three numbers by $3$ to get $2x\equiv3\pmod5$. Since $2^{-1}\equiv3\pmod5$, the reduced solution is $x\equiv4\pmod5$.
- Lift back to the original modulus by adding $5$: the residues are $4,9,14$ modulo $15$. Substituting them gives $24,54,84$, each congruent to $9$ modulo $15$; the solution count is $3$, not $1$.
Which congruence is equivalent to $6x\equiv9\pmod{15}$ after dividing by the gcd?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The gcd is 3, so the coefficient 6, target 9 and modulus 15 all divide by 3. The reduced class modulo 5 lifts to three classes modulo 15.
Cancellation and the zero coefficient
- Dividing only the coefficient and target changes the problem: replacing $6x\equiv9\pmod{15}$ by $2x\equiv3\pmod{15}$ would give only $x\equiv9\pmod{15}$ and lose the other two solutions. The modulus must shrink during the division step.
- If $n\mid a$, then $ax\equiv0\pmod n$ for every $x$. There are all $n$ residue solutions when $n\mid b$, and none otherwise. Thus $0x\equiv0\pmod6$ has six solutions, while $0x\equiv1\pmod6$ has none; no inverse modulo $1$ is needed.
How many solutions?
Use gcd(a, n) to count solutions of ax ≡ b (mod n).
How many residue classes modulo $6$ satisfy $0x\equiv0\pmod6$?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Every residue 0, 1, 2, 3, 4 and 5 works. The gcd is gcd(0, 6) = 6, which divides the target 0.
Solve $18x\equiv30\pmod{42}$ and list every residue solution modulo $42$. Explain why your list is complete.
The gcd is $\gcd(18,42)=6$, which divides 30. Divide the coefficient, target and modulus by 6 to obtain $3x\equiv5\pmod7$. Since the inverse of 3 modulo 7 is 5, this gives $x\equiv25\equiv4\pmod7$. The six lifts modulo 42 are $4,11,18,25,32,39$. Each lift satisfies the original congruence. There are exactly six distinct lifts because the reduced period is 7 and the original modulus is 42.
Find inverses by extended Euclid
- The inverse of $a$ modulo $n$ exists exactly when $\gcd(a,n)=1$. For $7$ and $26$, Euclid gives $26=3\cdot7+5$, then $7=5+2$, then $5=2\cdot2+1$; the last nonzero remainder is $1$.
- Since $2=7-5$, back-substituting gives $1=3\cdot5-2\cdot7$. Next use $5=26-3\cdot7$ to obtain $1=3\cdot26-11\cdot7$. Hence $7^{-1}\equiv-11\equiv15\pmod{26}$; check that $7\cdot15=105\equiv1\pmod{26}$.
Find the inverse of 5 modulo 13 (between 1 and 12).
Difficulty 2/5 · 140 coins + a small bonus on first completion today
We need 5x ≡ 1 (mod 13). 5 · 8 = 40 = 3 · 13 + 1, so the inverse is 8. (The Euclidean algorithm finds it systematically.)
Combine coprime cycles
- The Chinese remainder theorem is the result that congruences with pairwise coprime moduli have exactly one common residue class modulo the product of their moduli. For two moduli, substitute $x=r+mk$ into $x\equiv s\pmod n$; the coefficient $m$ is invertible modulo $n$.
- In the gear example, write $x=2+4k$. The second condition becomes $4k\equiv1\pmod7$, so $k\equiv2\pmod7$ and $x\equiv10\pmod{28}$. The least positive time is $10$; the whole solution set is $10+28t$ for integer $t$.
Find the least positive $x$ with $x \equiv 1 \pmod 3$ and $x \equiv 4 \pmod 5$.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
List numbers ≡ 4 (mod 5): 4, 9, 14, … The first, 4, already leaves remainder 1 when divided by 3, so x = 4. By the CRT the solution is unique mod 15.
Non-coprime moduli: test compatibility
- For $x\equiv r\pmod m$ and $x\equiv s\pmod n$, a solution exists exactly when $\gcd(m,n)$ divides $s-r$. Substituting $x=r+mk$ gives $mk\equiv s-r\pmod n$, so the linear gcd test applies. A compatible system gives one class modulo $\operatorname{lcm}(m,n)$.
- For $x\equiv1\pmod4$ and $x\equiv3\pmod6$, substitute $x=1+4k$ to get $4k\equiv2\pmod6$. Reduce to $2k\equiv1\pmod3$, giving $k\equiv2\pmod3$ and $x\equiv9\pmod{12}$. But residues $0$ modulo $4$ and $3$ modulo $6$ are incompatible: one requires an even number, the other an odd number.
Find the least positive integer $x$ with $x\equiv3\pmod8$ and $x\equiv7\pmod{12}$.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
The gcd is 4, which divides the difference 7 − 3. Put x = 3 + 8k. Then 8k ≡ 4 (mod 12), so 2k ≡ 1 (mod 3) and k ≡ 2 (mod 3). Thus x ≡ 19 (mod 24), with least positive member 19.
The period and the least positive solution
- Two solutions of the same system differ by a multiple of both moduli, hence by their lcm. Conversely, adding the lcm to a solution preserves both conditions. This proves the claimed period and uniqueness of the residue class.
- A least nonnegative representative need not be positive. For $x\equiv0\pmod4$ and $x\equiv0\pmod6$, the class is $0$ modulo $12$; its least positive member is $12$, not $0$. Read the requested range before choosing the final representative.
Solve $x\equiv2\pmod6$, $x\equiv8\pmod{10}$. Give the full residue class and least positive solution. Then explain what changes if the first residue is changed to $1$.
The gcd is 2 and divides $8-2=6$, so the first system is compatible. Write $x=2+6k$; then $6k\equiv6\pmod{10}$, so $3k\equiv3\pmod5$ and $k\equiv1\pmod5$. Hence $x\equiv8\pmod{30}$, where $30=\operatorname{lcm}(6,10)$. Its least positive solution is 8. If the first residue becomes 1, the required difference is $8-1=7$, which is not divisible by the gcd 2. Equivalently, the two congruences demand odd and even parity, so no solution exists.
Totient: count the invertible residues
- The totient 欧拉函数 is the number of residue classes coprime to the modulus. For $n\geq2$, write this count as $\varphi(n)$. If the distinct prime divisors are $p$, then $\varphi(n)=n\prod_{p\mid n}(1-1/p)$: each prime enters the product once, regardless of its exponent in $n$.
- Since $36=2^2\cdot3^2$, we get $\varphi(36)=36\cdot\dfrac12\cdot\dfrac23=12$. For a prime power, $\varphi(p^k)=p^k-p^{k-1}$, because exactly the multiples of $p$ fail to be coprime to $p^k$.
$\varphi(36)$ equals
Difficulty 1/5 · 100 coins + a small bonus on first completion today
$36 \cdot \tfrac12 \cdot \tfrac23$.
Euler and Fermat require the right conditions
- If $\gcd(a,n)=1$, Euler's theorem gives $a^{\varphi(n)}\equiv1\pmod n$. Multiplication by $a$ permutes the invertible residues; comparing their products and cancelling the invertible product proves the result.
- For a prime $p$ and $p\nmid a$, this becomes Fermat's theorem $a^{p-1}\equiv1\pmod p$. The form $a^p\equiv a\pmod p$ holds for every integer $a$, including multiples of $p$. For example, $\varphi(10)=4$ and $3^{100}=(3^4)^{25}\equiv1\pmod{10}$.
What is $7^{222} \bmod 10$?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
φ(10) = 4, 222 ≡ 2 mod 4, 7² = 49.
For integers $a$ and $n\geq2$, $a^{\varphi(n)}\equiv1\pmod n$ holds whenever $\gcd(a,n)=1$.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
True. Euler’s theorem requires coprimality. For example, 2 and 8 are not coprime, and $2^4\equiv0\pmod8$ rather than 1.
Reduce exponents only for units
- For a nonnegative exponent $e$ and $\gcd(a,n)=1$, reducing $e$ modulo $\varphi(n)$ preserves $a^e$ modulo $n$. Without coprimality this can fail: reducing $10$ modulo $\varphi(8)=4$ would wrongly replace $2^{10}$ by $2^2\equiv4\pmod8$.
- Repeated squaring works without a coprimality assumption. Here $2^2\equiv4$, $2^4\equiv0$ and $2^8\equiv0\pmod8$. Since $10=8+2$, the actual residue is $2^{10}\equiv0\pmod8$. Reduce intermediate products, rather than invoking Euler for a nonunit.
Since $\varphi(8)=4$, reducing the exponent proves $2^{10}\equiv2^2\pmod8$.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Euler exponent reduction requires an invertible base. The actual residues are 2¹⁰ ≡ 0 (mod 8) and 2² ≡ 4 (mod 8), so they differ.
Compute $5^{123}\bmod12$ and $6^{18}\bmod9$. Explain why the same exponent-reduction shortcut does not apply to both.
For the first power, $\gcd(5,12)=1$ and $\varphi(12)=4$. Since $123\equiv3\pmod4$, Euler gives $5^{123}\equiv5^3\equiv5\pmod{12}$. For the second, $\gcd(6,9)=3$, so Euler reduction is not justified. Instead $6^2=36\equiv0\pmod9$, hence $6^{18}=(6^2)^9\equiv0\pmod9$. Reducing 18 modulo $\varphi(9)=6$ would wrongly replace the power by $6^0=1$.
Divisibility becomes prime-exponent inequalities
- For a positive integer $M$, let $v_p(M)$ be the exponent of the prime $p$ in its factorisation. A positive integer $D$ divides $M$ exactly when $v_p(D)\leq v_p(M)$ for every prime $p$.
- If $N^k$ must be divisible by $D$, with positive integer $k$, require $k\,v_p(N)\geq v_p(D)$. Choose $v_p(N)=\lceil v_p(D)/k\rceil$ for primes dividing $D$, and zero for other primes. Every admissible $N$ is a multiple of this choice, so it is the least positive one.
The least integer whose square contains 360
- Factor $360=2^3\cdot3^2\cdot5$. For $N^2$ to be divisible by $360$, the exponents of $2,3,5$ in $N$ must be at least $2,1,1$. Thus the least choice is $N=2^2\cdot3\cdot5=60$.
- Check $60^2=3600=10\cdot360$. The exponent of $2$ in $N$ rounds up from $3/2$ to $2$; it must not round down. Extra primes or larger exponents increase $N$ and cannot improve the minimum.
What is the least positive integer $N$ such that $108$ divides $N^2$?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Since 108 = 2²·3³, N needs at least one factor of 2 and two factors of 3. The least N is 2·3² = 18, and 18² = 324 = 3·108.
Pad a product to make a perfect power
- To make $24N$ a perfect cube, start with $24=2^3\cdot3$. Every prime exponent in the product must be a multiple of $3$. The exponent of $2$ is already suitable, but the exponent of $3$ needs two more copies, so the least multiplier is $N=3^2=9$.
- Check $24\cdot9=216=6^3$. This uses exponent congruences: $v_p(24)+v_p(N)\equiv0\pmod3$. The previous square-divisibility problem used inequalities instead. Choose the condition that matches the wording of the question.
Does the proposed step work?
Check the assumptions behind exponent reduction, CRT periods and minimum exponents.
What is the least positive integer $N$ such that $18N$ is a perfect cube?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Factor 18 = 2·3². To make all product exponents multiples of 3, add two factors of 2 and one factor of 3. Thus N = 2²·3 = 12 and 18·12 = 216 = 6³.
Find the least positive integer $N$ such that $540$ divides $N^2$ and $40N$ is a perfect cube. Prove minimality using prime exponents.
Write $540=2^2\cdot3^3\cdot5$ and $40=2^3\cdot5$. Let the exponents of 2, 3 and 5 in N be a, b and c. Divisibility of N² requires $a\geq1$, $b\geq2$ and $c\geq1$. The cube condition requires $a+3$, b and $c+1$ to be multiples of 3. The least possible exponents are therefore $a=3$, $b=3$ and $c=2$, giving $N=2^3\cdot3^3\cdot5^2=5400$. No extra prime is needed. Every admissible N has at least these exponents, so none can be smaller. Check that $5400^2/540=54000$ is an integer and $40\cdot5400=216000=60^3$.
Check existence, period and minimality
- For a linear congruence, test the gcd, reduce all three numbers and lift every residue. For a system, test compatibility and use the lcm as its period; a least positive answer may differ from the least nonnegative representative.
- Use Euler only for invertible residues. For least-integer divisibility problems, factor first and translate each requirement into an inequality or a congruence for each prime exponent.