התאמות, חלוקה ופונקציות אריתמטיות
הוצג| English | משמעות |
|---|---|
| congruence/ˈkɒŋɡruːəns/ | התאמה מודולרית |
| totient/ˈtəʊʃənt/ | פונקציית טוטיינט |
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?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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 ____.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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.
איזו תשובה מתאימה למקרה זה?
פתור התאמות ליניאריות באמצעות תנאי GCD
x≡0 modulo 4 and x≡1 modulo 6 have a simultaneous solution.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Keep the distinctions stated in the teaching example.
Put this lesson’s reasoning or event sequence in order.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
The order follows the stated process; check each stage before the next.