Congruences, divisibilité et fonctions arithmétiques
Introduit| English | Sens |
|---|---|
| congruence/ˈkɒŋɡruːəns/ | congruence |
| Chinese remainder theorem/tʃaɪˈniːz rɪˈmeɪndə ˈθɪərəm/ | théorème des restes chinois |
| totient/ˈtəʊʃənt/ | fonction entotiente |
Quand les cycles s'alignent
- Un engrenage se répète tous les $4$ minutes, un autre tous les $7$. Se trouver en position $2$ sur le premier cycle et $3$ sur le second revient à chercher un temps $x$ vérifiant $x\equiv2\pmod4$ et $x\equiv3\pmod7$.
- Les congruences décrivent des positions répétées. Le théorème chinois combine ces congruences ; les tests du pgcd, les inverses modulaires et les exposants premiers indiquent quels pas algébriques sont valables.
La congruence signifie divisibilité
- Une congruence est une affirmation selon laquelle deux entiers ont le même reste modulo un entier positif spécifié. Ici, toutes les variables sont des entiers et les modules satisfont $n\geq2$ ; $a\equiv b\pmod n$ signifie exactement que $n$ divise $a-b$.
- Pour $ax\equiv b\pmod n$, posons $d=\gcd(a,n)$. Toute solution donne $ax-b=kn$ pour un certain entier $k$. Puisque $d$ divise à la fois $a$ et $n$, il doit diviser $b$ ; si $d\nmid b$, il n'y a pas de solution.
Pourquoi le pgcd compte aussi les solutions
- La condition $d\mid b$ est suffisante aussi. Bézout fournit des entiers $u,v$ avec $ua+vn=d$ ; multiplier par $b/d$ montre que $x=u(b/d)$ est une solution de la congruence originale.
- Si $d<n$, divisez le coefficient, la cible et le module par $d$. Le coefficient réduit est inversible modulo $n/d$, donnant une classe $x\equiv x_0\pmod{n/d}$. Ses relèvements sont $x_0+k(n/d)$ pour $k=0,\ldots,d-1$ : exactement $d$ résidus distincts modulo $n$. Le cas $d=n$ est traité séparément ci-dessous.
How many solutions modulo 20 does $8x \equiv 12 \pmod{20}$ have?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Réduire, résoudre et relever
- Pour $6x\equiv9\pmod{15}$, le pgcd est $3$ et divise $9$. Divisez les trois nombres par $3$ pour obtenir $2x\equiv3\pmod5$. Puisque $2^{-1}\equiv3\pmod5$, la solution réduite est $x\equiv4\pmod5$.
- Relevez vers le module original en ajoutant $5$ : les résidus sont $4,9,14$ modulo $15$. En les substituant, on obtient $24,54,84$, chacun congruent à $9$ modulo $15$ ; le nombre de solutions est $3$, et non $1$.
Which congruence is equivalent to $6x\equiv9\pmod{15}$ after dividing by the gcd?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Annulation et coefficient nul
- Diviser uniquement le coefficient et la cible modifie le problème : remplacer $6x\equiv9\pmod{15}$ par $2x\equiv3\pmod{15}$ ne donnerait que $x\equiv9\pmod{15}$ et ferait perdre les deux autres solutions. Le module doit diminuer lors de l'étape de division.
- Si $n\mid a$, alors $ax\equiv0\pmod n$ pour tout $x$. Il y a toutes les $n$ solutions résiduelles lorsque $n\mid b$, et aucune sinon. Ainsi $0x\equiv0\pmod6$ a six solutions, tandis que $0x\equiv1\pmod6$ n'en a aucune ; aucune inverse modulo $1$ n'est nécessaire.
Combien de solutions ?
Utilisez pgcd(a, n) pour compter les solutions de ax ≡ b (mod n).
How many residue classes modulo $6$ satisfy $0x\equiv0\pmod6$?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Le pgcd est $\gcd(18,42)=6$, qui divise 30. Diviser le coefficient, la cible et le module par 6 pour obtenir $3x\equiv5\pmod7$. Puisque l'inverse de 3 modulo 7 est 5, cela donne $x\equiv25\equiv4\pmod7$. Les six relèvements modulo 42 sont $4,11,18,25,32,39$. Chaque relèvement satisfait la congruence originale. Il y a exactement six relèvements distincts car la période réduite est 7 et le module original est 42.
Trouver des inverses par Euclide étendu
- L'inverse de $a$ modulo $n$ existe exactement quand $\gcd(a,n)=1$. Pour $7$ et $26$, Euclid donne $26=3\cdot7+5$, puis $7=5+2$, puis $5=2\cdot2+1$ ; le dernier reste non nul est $1$.
- Puisque $2=7-5$, la substitution arrière donne $1=3\cdot5-2\cdot7$. Ensuite, utilisez $5=26-3\cdot7$ pour obtenir $1=3\cdot26-11\cdot7$. Donc $7^{-1}\equiv-11\equiv15\pmod{26}$ ; vérifiez que $7\cdot15=105\equiv1\pmod{26}$.
Find the inverse of 5 modulo 13 (between 1 and 12).
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
We need 5x ≡ 1 (mod 13). 5 · 8 = 40 = 3 · 13 + 1, so the inverse is 8. (The Euclidean algorithm finds it systematically.)
Combiner des cycles copremiers
- Le théorème chinois des restes est le résultat selon lequel les congruences avec des modules mutuellement premiers ont exactement une classe de résidu commune modulo le produit de leurs modules. Pour deux modules, substituez $x=r+mk$ dans $x\equiv s\pmod n$ ; le coefficient $m$ est inversible modulo $n$.
- Dans l'exemple des engrenages, écrivons $x=2+4k$. La deuxième condition devient $4k\equiv1\pmod7$, donc $k\equiv2\pmod7$ et $x\equiv10\pmod{28}$. Le premier temps positif est $10$ ; l'ensemble des solutions est $10+28t$ pour un entier $t$.
Find the least positive $x$ with $x \equiv 1 \pmod 3$ et $x \equiv 4 \pmod 5$.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Modules non copremiers : tester la compatibilité
- Pour $x\equiv r\pmod m$ et $x\equiv s\pmod n$, une solution existe exactement lorsque $\gcd(m,n)$ divise $s-r$. En substituant $x=r+mk$, on obtient $mk\equiv s-r\pmod n$ ; le test de gcd linéaire s'applique alors. Un système compatible donne une classe modulo $\operatorname{lcm}(m,n)$.
- Pour $x\equiv1\pmod4$ et $x\equiv3\pmod6$, en substituant $x=1+4k$, on obtient $4k\equiv2\pmod6$. En réduisant à $2k\equiv1\pmod3$, on trouve $k\equiv2\pmod3$ et $x\equiv9\pmod{12}$. Cependant, les résidus $0$ modulo $4$ et $3$ modulo $6$ sont incompatibles : l'un exige un nombre pair, l'autre un nombre impair.
Find the least positive integer $x$ with $x\equiv3\pmod8$ et $x\equiv7\pmod{12}$.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Période et plus petite solution positive
- Deux solutions d'un même système diffèrent par un multiple commun des deux modules, donc par leur PPCM. Inversement, ajouter le PPCM à une solution préserve les deux conditions. Cela prouve la période annoncée et l'unicité de la classe de résidus.
- Un représentant minimal non négatif n'est pas nécessairement positif. Pour $x\equiv0\pmod4$ et $x\equiv0\pmod6$, la classe est $0$ modulo $12$ ; son plus petit membre positif est $12$, et non $0$. Lisez la plage demandée avant de choisir le représentant final.
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$.
Le pgcd est 2 et divise $8-2=6$, donc le premier système est compatible. Écrire $x=2+6k$ ; puis $6k\equiv6\pmod{10}$, donc $3k\equiv3\pmod5$ et $k\equiv1\pmod5$. Ainsi $x\equiv8\pmod{30}$, où $30=\operatorname{lcm}(6,10)$. Sa plus petite solution positive est 8. Si le premier résidu devient 1, la différence requise est $8-1=7$, qui n'est pas divisible par le pgcd 2. De manière équivalente, les deux congruences exigent une parité impaire et paire, donc aucune solution n'existe.
Fonction indicatrice : compter les résidus inversibles
- La fonction indicatrice correspond au nombre de classes de résidus premieres avec le module. Pour $n\geq2$, notons ce nombre $\varphi(n)$. Si les diviseurs premiers distincts sont $p$, alors $\varphi(n)=n\prod_{p\mid n}(1-1/p)$ : chaque premier intervient une seule fois dans le produit, indépendamment de son exposant dans $n$.
- Puisque $36=2^2\cdot3^2$, nous obtenons $\varphi(36)=36\cdot\dfrac12\cdot\dfrac23=12$. Pour une puissance de premier, $\varphi(p^k)=p^k-p^{k-1}$, car seuls les multiples de $p$ ne sont pas premieres avec $p^k$.
$\varphi(36)$ equals
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
$36 \cdot \tfrac12 \cdot \tfrac23$.
Euler et Fermat nécessitent les bonnes conditions
- Si $\gcd(a,n)=1$, le théorème d'Euler donne $a^{\varphi(n)}\equiv1\pmod n$. La multiplication par $a$ permute les résidus inversibles ; en comparant leurs produits et en simplifiant par le produit des inversibles, on démontre le résultat.
- Pour un premier $p$ et $p\nmid a$, cela devient le théorème de Fermat $a^{p-1}\equiv1\pmod p$. La forme $a^p\equiv a\pmod p$ est valide pour tout entier $a$, y compris les multiples de $p$. Par exemple, $\varphi(10)=4$ et $3^{100}=(3^4)^{25}\equiv1\pmod{10}$.
What is $7^{222} \bmod 10$?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
φ(10) = 4, 222 ≡ 2 mod 4, 7² = 49.
For integers $a$ et $n\geq2$, $a^{\varphi(n)}\equiv1\pmod n$ holds whenever $\gcd(a,n)=1$.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
True. Euler’s theorem requires coprimality. For example, 2 and 8 are not coprime, and $2^4\equiv0\pmod8$ rather than 1.
Réduire les exposants uniquement pour les unités
- Pour un exposant non négatif $e$ et $\gcd(a,n)=1$, réduire $e$ modulo $\varphi(n)$ conserve $a^e$ modulo $n$. Sans condition de primarité, cela peut échouer : réduire $10$ modulo $\varphi(8)=4$ remplacerait faussement $2^{10}$ par $2^2\equiv4\pmod8$.
- Le carré successif fonctionne sans hypothèse de primarité. Ici $2^2\equiv4$, $2^4\equiv0$ et $2^8\equiv0\pmod8$. Puisque $10=8+2$, le résidu réel est $2^{10}\equiv0\pmod8$. Réduisez les produits intermédiaires plutôt que d'invoquer Euler pour un non-unité.
Since $\varphi(8)=4$, reducing the exponent proves $2^{10}\equiv2^2\pmod8$.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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$ et $6^{18}\bmod9$. Explain why the same exponent-reduction shortcut does not apply to both.
Pour la première puissance, $\gcd(5,12)=1$ et $\varphi(12)=4$. Puisque $123\equiv3\pmod4$, Euler donne $5^{123}\equiv5^3\equiv5\pmod{12}$. Pour la seconde, $\gcd(6,9)=3$, donc la réduction d'Euler n'est pas justifiée. À la place, $6^2=36\equiv0\pmod9$, donc $6^{18}=(6^2)^9\equiv0\pmod9$. Réduire 18 modulo $\varphi(9)=6$ remplacerait faussement la puissance par $6^0=1$.
La divisibilité se traduit par des inégalités d'exposants premiers
- Pour un entier positif $M$, soit $v_p(M)$ l'exposant du premier $p$ dans sa factorisation. Un entier positif $D$ divise exactement $M$ si et seulement si $v_p(D)\leq v_p(M)$ pour tout premier $p$.
- Si $N^k$ doit être divisible par $D$, avec entier positif $k$, il faut exiger $k\,v_p(N)\geq v_p(D)$. Choisissez $v_p(N)=\lceil v_p(D)/k\rceil$ pour les premiers divisant $D$, et zéro pour les autres. Tout admissible $N$ est un multiple de ce choix, c'est donc le plus petit positif.
Le plus petit entier dont le carré contient 360
- Factorisez $360=2^3\cdot3^2\cdot5$. Pour que $N^2$ soit divisible par $360$, les exposants de $2,3,5$ dans $N$ doivent être au moins $2,1,1$. Le choix minimal est donc $N=2^2\cdot3\cdot5=60$.
- Vérifiez $60^2=3600=10\cdot360$. L'exposant de $2$ dans $N$ s'arrondit de $3/2$ vers le haut jusqu'à $2$ ; il ne doit jamais s'arrondir vers le bas. Des premiers supplémentaires ou des exposants plus grands augmentent $N$ et ne peuvent améliorer le minimum.
What is the least positive integer $N$ such that $108$ divides $N^2$?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Ajuster un produit pour obtenir une puissance parfaite
- Pour que $24N$ soit un cube parfait, commencer avec $24=2^3\cdot3$. Chaque exposant premier dans le produit doit être un multiple de $3$. L'exposant de $2$ est déjà adéquat, mais celui de $3$ nécessite deux copies supplémentaires, donc le plus petit multiplicateur est $N=3^2=9$.
- Vérifiez $24\cdot9=216=6^3$. Cela utilise des congruences d'exposants : $v_p(24)+v_p(N)\equiv0\pmod3$. Le problème précédent de divisibilité par un carré utilisait des inégalités à la place. Choisissez la condition correspondant à l'énoncé de la question.
L'étape proposée fonctionne-t-elle ?
Vérifiez les hypothèses sous-jacentes à la réduction des exposants, aux périodes de CRT et aux exposants minimaux.
What is the least positive integer $N$ such that $18N$ is a perfect cube?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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$ et $40N$ is a perfect cube. Prove minimality using prime exponents.
Écrire $540=2^2\cdot3^3\cdot5$ et $40=2^3\cdot5$. Soient a, b et c les exposants de 2, 3 et 5 dans N. La divisibilité de N² nécessite $a\geq1$, $b\geq2$ et $c\geq1$. La condition de cube exige que $a+3$, b et $c+1$ soient des multiples de 3. Les exposants minimaux possibles sont donc $a=3$, $b=3$ et $c=2$, donnant $N=2^3\cdot3^3\cdot5^2=5400$. Aucun autre nombre premier n'est nécessaire. Tout N admissible possède au moins ces exposants, donc aucun ne peut être plus petit. Vérifier que $5400^2/540=54000$ est un entier et $40\cdot5400=216000=60^3$.
Vérifier l'existence, la période et la minimalité
- Pour une congruence linéaire, testez le pgcd, réduisez les trois nombres et relevez chaque résidu. Pour un système, vérifiez la compatibilité et utilisez le ppcm comme période ; la plus petite réponse positive peut différer du représentant non négatif minimal.
- N'utilisez Euler que pour les résidus inversibles. Pour les problèmes de divisibilité impliquant le plus petit entier, factorisez d'abord et traduisez chaque exigence en une inégalité ou une congruence pour chaque exposant premier.