Congruences, divisibility and arithmetic functions
| English | Français |
|---|---|
| congruence/ˈkɒŋɡruːəns/ | congruence |
| totient/ˈtəʊʃənt/ | totient |
A decision before an answer
- A machine repeats one cycle every four minutes and another every seven. A simultaneous position is a congruence problem, not a decimal approximation.
- Your goal: Solve linear congruences using gcd conditions.
Read the relationship
- The equation ax≡b modulo n has a solution exactly when d=gcd(a,n) divides b. If it does, divide a,b,n by d to obtain an equation with an invertible coefficient. It has one residue solution modulo n/d and d distinct solutions modulo n. Dividing the coefficient but leaving the original modulus generally loses solutions. Prime factorisation gives another divisibility tool: if n^k must be divisible by a product of prime powers p^a, each prime exponent in n must be at least ceil(a/k). These minimum exponents independently produce the least positive admissible n. For n⁴ divisible by 2⁷·3⁵, n must contain 2² and 3², so the least value is 36. This is a prime-exponent condition, not a congruence solved by modular division.
- Combine coprime congruences with the Chinese remainder theorem.
How many distinct solutions modulo 18 satisfy 6x≡12?
gcd(6,18)=6 divides 12, so there are six solutions; after dividing the modulus too, x≡2 modulo 3.
Use the defining rule
- The extended Euclidean algorithm expresses gcd(a,n) as ua+vn. When the gcd is 1, u is an inverse of a modulo n. Choose a representative in the required range after reduction. For 7 and 26, 1=15·7−4·26, so 15 is the inverse of 7 modulo 26; verify the product to catch a sign error.
- Apply Euler's theorem only to invertible residues.
What is the least nonnegative x with x≡1 modulo 3 and x≡2 modulo 5?
Among 1,4,7,10,13 modulo 15, only 7 has residue 2 modulo 5.
Check the conditions
- For coprime positive moduli m,n, the Chinese remainder theorem gives exactly one solution modulo mn for each pair of residue conditions. Substitute x=r+mk into the second congruence and solve for k. If the moduli are not coprime, their residue values must agree modulo gcd(m,n); when consistent, uniqueness is modulo the least common multiple, not the product.
- Use prime-exponent divisibility to find least admissible integers.
Solve 6x≡9 modulo 15. The gcd is 3 and divides 9. Divide all three quantities to get 2x≡3 modulo 5; the inverse of 2 is 3, so x≡9≡4 modulo 5. The original solutions modulo 15 are 4,9,14. For x≡2 modulo 4 and x≡3 modulo 7, write x=2+4k; then 4k≡1 modulo 7, giving k≡2. Hence x≡10 modulo 28.
phi(12) equals ____.
The coprime residues are 1,5,7,11, or use 12(1−1/2)(1−1/3)=4.
Apply the task format
- Euler's totient phi(n) counts residues coprime to n. For distinct prime divisors p, phi(n)=n times the product of (1−1/p). Euler's theorem gives a^phi(n)≡1 only when gcd(a,n)=1. The prime case is Fermat's little theorem. Reduce exponents only after checking this condition; a nonunit can become zero under repeated powers instead.
- Use prime-exponent divisibility to find least admissible integers.
The expression a^phi(n)≡1 is false for arbitrary a. For example 2 is not invertible modulo 8 and 2^4 is zero modulo 8.
Which answer fits this case?
Solve linear congruences using gcd conditions
x≡0 modulo 4 and x≡1 modulo 6 have a simultaneous solution.
The first condition makes x even, the second makes it odd; residues disagree modulo gcd(4,6)=2.
Keep the distinctions
- congruence 同余 — Equality of residues because the modulus divides their difference.
- totient 欧拉函数 — The count of residues coprime to the positive integer modulus.
- Solve linear congruences using gcd conditions.
- Combine coprime congruences with the Chinese remainder theorem.
- Apply Euler's theorem only to invertible residues.
- Use prime-exponent divisibility to find least admissible integers.
Match each term with its precise meaning in this lesson.
Keep the distinctions stated in the teaching example.
Put this lesson’s reasoning or event sequence in order.
The order follows the stated process; check each stage before the next.