Théorie des nombres · laboratoire
De l’horloge aux congruences, des cycles de puissances au théorème chinois des restes.
Une horloge de 12 heures ne s’arrête pas à 12 : cinq heures après 10 heures, elle indique 3 heures. Ce laboratoire part de cette idée pour étudier les restes, la divisibilité et des problèmes de plus en plus riches. Ouvrez « Pourquoi ? » à chaque étape, puis essayez les outils.
Étape 1 / 15
Après un tour complet, on revient au même point. Seul compte ce qui dépasse les tours entiers.
10+5=15 ≡ 3 (mod 12)
Exemple: 17, 29 et 41 laissent tous le reste 5 dans la division par 12.
Les écarts entre ces nombres sont des multiples de 12 : le nombre de tours change, pas la position.
Étape 2 / 15
Deux entiers sont congrus s’ils appartiennent à la même classe de restes.
a ≡ b (mod n) ⇔ n divise a−b
Exemple: 23 ≡ 3 (mod 10), car 23−3=20.
Si a−b=kn, alors a et b diffèrent de k tours complets de longueur n.
Étape 3 / 15
Utilisez la division euclidienne et choisissez toujours un reste non négatif.
a=nq+r, 0≤r<n
Exemple: −17=5×(−4)+3, donc −17 mod 5=3.
Le quotient peut être négatif ; la condition 0≤r<n rend le reste unique. Modulo 1, il vaut toujours 0.
Étape 4 / 15
On peut réduire chaque terme avant d’additionner ou de soustraire.
a≡b, c≡d ⇒ a±c≡b±d (mod n)
Exemple: 17+29 ≡ 5+5 ≡ 10 (mod 12).
La somme ou la différence de multiples de n est encore un multiple de n.
Étape 5 / 15
La multiplication conserve aussi les congruences.
a≡b, c≡d ⇒ ac≡bd (mod n)
Exemple: 123×456 mod 7 = 4×1 mod 7 = 4.
Si a=b+kn et c=d+hn, la différence ac−bd contient n comme facteur.
Étape 6 / 15
Les puissances parcourent un nombre fini de restes : tôt ou tard, un reste revient.
7¹,7²,7³,7⁴ ≡ 7,9,3,1 (mod 10)
Exemple: 2026 mod 4=2 : le dernier chiffre de 7^2026 est 9.
Quand un état revient, multiplier par la même base reproduit le parcours. Certains cycles commencent après une pré-période.
Étape 7 / 15
Le dernier chiffre décimal est simplement le reste modulo 10.
dernier chiffre de a^b = a^b mod 10
Exemple: 3^25 : cycle 3,9,7,1 ; 25 mod 4=1, donc le chiffre est 3.
Deux entiers ont le même dernier chiffre si et seulement s’ils sont congrus modulo 10.
Étape 8 / 15
Passez au module 100 et écrivez toujours deux chiffres.
deux derniers chiffres de a^b = a^b mod 100
Exemple: 3^100 mod 100=1 : les deux derniers chiffres sont 01.
Les carrés successifs évitent de construire une puissance gigantesque.
Étape 9 / 15
Chaque position décimale est une puissance de 10 : remplacez 10 par son reste.
10≡1 (mod 9); 10≡−1 (mod 11)
Exemple: Pour 5724, la somme des chiffres vaut 18 : il est divisible par 9. Pour 11, 2728 donne 2−7+2−8=−11 : il est divisible par 11.
Modulo 9, toute puissance de 10 vaut 1 ; modulo 11, elles alternent entre 1 et −1.
Étape 10 / 15
Les heures tournent modulo 12 ou 24 ; les jours de la semaine modulo 7.
22+17≡15 (mod 24); 100≡2 (mod 7)
Exemple: Cent jours après lundi, ce sera mercredi.
Chaque cycle complet ramène l’indicateur à sa position de départ.
Étape 11 / 15
L’équation ax≡b (mod n) peut avoir zéro, une ou plusieurs solutions.
d=PGCD(a,n); solutions ⇔ d divise b
Exemple: 6x≡4 (mod 8) : d=2 et les solutions sont 2 et 6.
Divisez par d pour obtenir une solution modulo n/d ; elle produit d classes modulo n.
Étape 12 / 15
L’inverse de a est un nombre dont le produit avec a laisse le reste 1.
a⁻¹ existe (mod n) ⇔ PGCD(a,n)=1, n>1
Exemple: 7×3=21≡1 (mod 10), donc 7⁻¹≡3.
L’identité de Bézout exprime 1 comme combinaison de a et n exactement lorsque leur PGCD est 1.
Étape 13 / 15
Cherchez un entier qui satisfait plusieurs conditions de reste en même temps.
x≡2 (mod 3); x≡3 (mod 5)
Exemple: La plus petite solution positive est x=8.
La première condition donne x=2+3t ; en remplaçant dans la seconde, t≡2 (mod 5).
Étape 14 / 15
Avec des modules premiers entre eux deux à deux, il existe une classe solution modulo leur produit.
x≡2 (mod 3), x≡3 (mod 5), x≡2 (mod 7) ⇒ x≡23 (mod 105)
Exemple: 23 divisé par 3, 5 et 7 laisse respectivement 2, 3 et 2.
Chaque nouvelle congruence fixe le paramètre de la solution précédente ; la coprimalité garantit que ce choix existe et est unique.
Étape 15 / 15
Les restes servent à trouver des chiffres finaux, des carrés impossibles et des solutions de systèmes.
7^(7^7) mod 10 : réduire d’abord l’exposant modulo 4
Exemple: 7^7≡3 (mod 4) : le dernier chiffre de 7^(7^7) est 3.
Une question énorme se décompose en petits modules emboîtés. Entraînez-vous avec les 25 défis ci-dessous.
Saisissez des entiers. Le module doit être positif ; le module 1 convient pour les restes, mais il ne possède pas d’inverse modulaire.
Comparez tous les carrés ou cubes modulo n (jusqu’à 60) et observez les résidus distincts.
Répondez avant d’ouvrir l’indice ou la solution. Les essais et les problèmes résolus restent seulement dans ce navigateur, même si vous changez de langue.
1 / 25 · Facile
Calculez 37 mod 5.
Combien de fois 5 entre-t-il dans 37 ?
2 / 25 · Facile
47≡5 (mod 7) est-il vrai ? Répondez oui ou non.
Soustrayez 5 de 47.
3 / 25 · Facile
Il est 9 heures. Quelle heure sera-t-il dans 17 heures sur une horloge de 12 heures ?
Additionnez puis retirez les tours complets de 12.
4 / 25 · Facile
Aujourd’hui est lundi. Quel jour sera-t-on dans 100 jours ?
Réduisez 100 modulo 7.
5 / 25 · Facile
Quel est le dernier chiffre de 3^25 ?
Le cycle modulo 10 est 3,9,7,1.
6 / 25 · Facile
Quel est le dernier chiffre de 7^2026 ?
Le cycle est 7,9,3,1.
7 / 25 · Facile
123456789 est-il divisible par 9 ? Répondez oui ou non.
Additionnez les chiffres.
8 / 25 · Moyen
2728 est-il divisible par 11 ? Répondez oui ou non.
Alternez les signes des chiffres.
9 / 25 · Moyen
Calculez (1234567+9876543) mod 9.
Réduisez les deux termes séparément.
10 / 25 · Moyen
Calculez 123×456 mod 7.
Réduisez les facteurs avant de les multiplier.
11 / 25 · Moyen
Calculez 2^100 mod 7.
Le cycle est 2,4,1.
12 / 25 · Moyen
Calculez 5^2025 mod 13.
Calculez les quatre premières puissances de 5 modulo 13.
13 / 25 · Moyen
Résolvez 3x≡1 (mod 7) : indiquez x modulo 7.
Quel nombre multiplié par 3 laisse le reste 1 ?
14 / 25 · Moyen
Résolvez 7x≡3 (mod 10) : indiquez x modulo 10.
L’inverse de 7 modulo 10 est 3.
15 / 25 · Difficile
Résolvez 6x≡5 (mod 8). Écrivez « aucune » si nécessaire.
Calculez PGCD(6,8).
16 / 25 · Difficile
Résolvez 6x≡4 (mod 8). Séparez les deux solutions par une virgule.
Divisez par PGCD(6,8)=2.
17 / 25 · Difficile
Trouvez le plus petit x positif avec x≡2 (mod 3) et x≡3 (mod 5).
Écrivez x=2+3t.
18 / 25 · Difficile
Trouvez le plus petit x positif laissant 2 mod 3, 3 mod 5 et 2 mod 7.
Partez de x=8 pour les deux premières conditions.
19 / 25 · Difficile
Trouvez le plus petit entier positif laissant 1,2,3,4 lorsqu’on le divise par 2,3,4,5.
Il est congru à −1 pour chacun des quatre modules.
20 / 25 · Difficile
Quels sont les deux derniers chiffres de 3^100 ? Écrivez deux chiffres.
3^20≡1 (mod 100).
21 / 25 · Défi
Calculez (10^1000+3) mod 7.
10≡3 (mod 7) et 3^6≡1 (mod 7).
22 / 25 · Défi
Existe-t-il un entier x tel que x²≡3 (mod 4) ? Répondez oui ou non.
Essayez les restes 0,1,2,3.
23 / 25 · Défi
Quels sont les résidus distincts de x³ modulo 9 ? Séparez-les par des virgules.
Essayez x=0,1,…,8.
24 / 25 · Défi
Expliquez pourquoi n³−n est divisible par 6 pour tout entier n.
Factorisez n³−n=n(n−1)(n+1).
25 / 25 · Défi
Trouvez le dernier chiffre de 7^(7^7).
Le cycle de 7 modulo 10 a une période de 4 : réduisez d’abord 7^7 modulo 4.
Des pièces et des soldats aux calendriers : résous des systèmes de congruences, vérifie les bornes et découvre quand aucune réponse n’existe. Les solutions sont placées sous chaque problème, mais restent fermées tant que tu veux chercher.
Lire l’article : Sunzi et le théorème chinois des restes →
Le problème classique du Sunzi Suanjing demande un nombre laissant les restes 2, 3 et 2 lorsqu’on le divise par 3, 5 et 7. Les blocs 70, 21 et 15 donnent 2×70 + 3×21 + 2×15 = 233 ; en retirant deux fois 105, on obtient 23.
1 / 30 · Débutant
Trouve le plus petit entier positif satisfaisant toutes les conditions.
x ≡ 1 (mod 3) · x ≡ 2 (mod 5) · x ≡ 3 (mod 7)
Combine les congruences une à une : écris x comme le premier reste plus un multiple du premier module.
2 / 30 · Débutant
Trouve le plus petit entier positif satisfaisant toutes les conditions.
x ≡ 2 (mod 3) · x ≡ 2 (mod 5) · x ≡ 2 (mod 7)
Si tous les restes sont égaux, soustrais ce reste et cherche un multiple du PPCM.
3 / 30 · Débutant
Trouve le plus petit entier positif satisfaisant toutes les conditions.
x ≡ 2 (mod 3) · x ≡ 4 (mod 5) · x ≡ 6 (mod 7)
Chaque reste vaut un de moins que son module : raisonne sur x+1.
4 / 30 · Débutant
Trouve le plus petit entier positif satisfaisant toutes les conditions.
x ≡ 2 (mod 5) · x ≡ 3 (mod 7)
Combine les congruences une à une : écris x comme le premier reste plus un multiple du premier module.
5 / 30 · Débutant
Trouve le plus petit entier positif satisfaisant toutes les conditions.
x ≡ 1 (mod 4) · x ≡ 2 (mod 5) · x ≡ 3 (mod 7)
Combine les congruences une à une : écris x comme le premier reste plus un multiple du premier module.
7 / 30 · Débutant
Un marchand regroupe ses pièces par 3, 5 ou 7 : il en reste 2, 4 ou 6. Quel est le plus petit total ?
x ≡ 2 (mod 3) · x ≡ 4 (mod 5) · x ≡ 6 (mod 7)
Chaque reste vaut un de moins que son module : raisonne sur x+1.
16 / 30 · Débutant
Un marchand forme des groupes de 4, 5 ou 6 sacs de riz : il en reste chaque fois un de moins que la taille du groupe.
x ≡ 3 (mod 4) · x ≡ 4 (mod 5) · x ≡ 5 (mod 6)
Chaque reste vaut un de moins que son module : raisonne sur x+1.
6 / 30 · Intermédiaire
Trouve le plus petit entier positif satisfaisant toutes les conditions.
x ≡ 1 (mod 5) · x ≡ 2 (mod 7) · x ≡ 3 (mod 8)
Combine les congruences une à une : écris x comme le premier reste plus un multiple du premier module.
8 / 30 · Intermédiaire
Un général range ses soldats en rangs de 4, 5 ou 7 : il en reste respectivement 1, 2 ou 4.
x ≡ 1 (mod 4) · x ≡ 2 (mod 5) · x ≡ 4 (mod 7)
Combine les congruences une à une : écris x comme le premier reste plus un multiple du premier module.
10 / 30 · Intermédiaire
Trouve le plus petit entier positif satisfaisant toutes les conditions.
x ≡ 3 (mod 5) · x ≡ 4 (mod 7) · x ≡ 5 (mod 9)
Combine les congruences une à une : écris x comme le premier reste plus un multiple du premier module.
11 / 30 · Intermédiaire
Trouve le plus petit entier positif satisfaisant toutes les conditions.
x ≡ 1 (mod 2) · x ≡ 2 (mod 3) · x ≡ 3 (mod 5) · x ≡ 4 (mod 7)
Combine les congruences une à une : écris x comme le premier reste plus un multiple du premier module.
13 / 30 · Intermédiaire
Quels restes obtient-on en divisant 47 par 3, 5 et 7 ? Saisis les trois restes dans cet ordre, séparés par des virgules.
47 mod 3, 5, 7
Divise 47 par chaque module et note les trois restes dans l’ordre.
17 / 30 · Intermédiaire
Des rangs de 5, 7 ou 8 soldats laissent respectivement 1, 3 ou 4 soldats de côté.
x ≡ 1 (mod 5) · x ≡ 3 (mod 7) · x ≡ 4 (mod 8)
Combine les congruences une à une : écris x comme le premier reste plus un multiple du premier module.
19 / 30 · Intermédiaire
Trouve le plus petit entier positif satisfaisant toutes les conditions.
x ≡ 1 (mod 6) · x ≡ 2 (mod 7) · x ≡ 3 (mod 8)
Combine les congruences une à une : écris x comme le premier reste plus un multiple du premier module.
20 / 30 · Intermédiaire
Trois événements périodiques reviennent tous les 5, 7 et 9 jours. Leurs prochaines occurrences auront lieu dans 1, 3 et 4 jours. Quand coïncideront-ils ?
x ≡ 1 (mod 5) · x ≡ 3 (mod 7) · x ≡ 4 (mod 9)
Combine les congruences une à une : écris x comme le premier reste plus un multiple du premier module.
21 / 30 · Intermédiaire
Verser un nombre entier de litres dans des récipients de 8, 9 ou 13 litres laisse 3, 5 ou 7 litres.
x ≡ 3 (mod 8) · x ≡ 5 (mod 9) · x ≡ 7 (mod 13)
Combine les congruences une à une : écris x comme le premier reste plus un multiple du premier module.
22 / 30 · Intermédiaire
Trouve le plus petit entier positif satisfaisant toutes les conditions.
x ≡ 2 (mod 6) · x ≡ 5 (mod 9)
Pour des modules non premiers entre eux, les restes doivent coïncider modulo leur PGCD.
25 / 30 · Intermédiaire
Trouve le plus petit entier positif satisfaisant toutes les conditions.
x ≡ 1 (mod 5) · x ≡ 2 (mod 6) · x ≡ 3 (mod 7)
Combine les congruences une à une : écris x comme le premier reste plus un multiple du premier module.
9 / 30 · Difficile
Trouve le plus petit entier positif satisfaisant toutes les conditions.
x ≡ 3 (mod 8) · x ≡ 5 (mod 9) · x ≡ 7 (mod 11)
Combine les congruences une à une : écris x comme le premier reste plus un multiple du premier module.
12 / 30 · Difficile
Trouve le plus petit entier positif satisfaisant toutes les conditions.
x ≡ 5 (mod 8) · x ≡ 7 (mod 9) · x ≡ 9 (mod 11)
Combine les congruences une à une : écris x comme le premier reste plus un multiple du premier module.
15 / 30 · Difficile
Trouve le plus petit entier positif satisfaisant toutes les conditions.
x ≡ 2 (mod 7) · x ≡ 4 (mod 9) · x ≡ 6 (mod 11)
Combine les congruences une à une : écris x comme le premier reste plus un multiple du premier module.
26 / 30 · Difficile
Le nombre recherché se trouve entre 100 et 500 inclus.
x ≡ 2 (mod 7) · x ≡ 3 (mod 8) · x ≡ 4 (mod 9)
Cherche une réponse dans les bornes indiquées ; si elle n’existe pas, écris « aucune ». De 100 · Jusqu’à 500
Résous d’abord sans bornes, puis compare le plus petit candidat positif à l’intervalle demandé.
28 / 30 · Difficile
Trouve le plus petit entier positif satisfaisant toutes les conditions.
x ≡ 1 (mod 3) · x ≡ 2 (mod 4) · x ≡ 3 (mod 5) · x ≡ 4 (mod 7)
Combine les congruences une à une : écris x comme le premier reste plus un multiple du premier module.
30 / 30 · Difficile
Trouve le plus petit entier positif satisfaisant toutes les conditions.
x ≡ 4 (mod 7) · x ≡ 5 (mod 8) · x ≡ 6 (mod 9) · x ≡ 7 (mod 11)
Combine les congruences une à une : écris x comme le premier reste plus un multiple du premier module.
14 / 30 · Pièges sans réponse dans les conditions données
Trouve le plus petit entier positif satisfaisant toutes les conditions.
x ≡ 1 (mod 4) · x ≡ 2 (mod 6)
Pour des modules non premiers entre eux, les restes doivent coïncider modulo leur PGCD.
18 / 30 · Pièges sans réponse dans les conditions données
Un trésor contient moins de 500 pièces ; la division par 7, 9 et 11 laisse 2, 4 et 6.
x ≡ 2 (mod 7) · x ≡ 4 (mod 9) · x ≡ 6 (mod 11)
Cherche une réponse dans les bornes indiquées ; si elle n’existe pas, écris « aucune ». Moins de 500
Résous d’abord sans bornes, puis compare le plus petit candidat positif à l’intervalle demandé.
23 / 30 · Pièges sans réponse dans les conditions données
Trouve le plus petit entier positif satisfaisant toutes les conditions.
x ≡ 2 (mod 6) · x ≡ 4 (mod 9)
Pour des modules non premiers entre eux, les restes doivent coïncider modulo leur PGCD.
24 / 30 · Pièges sans réponse dans les conditions données
Un entrepôt contient moins de 1 000 boîtes ; des groupes de 11, 13 et 17 laissent 4, 6 et 10 boîtes.
x ≡ 4 (mod 11) · x ≡ 6 (mod 13) · x ≡ 10 (mod 17)
Cherche une réponse dans les bornes indiquées ; si elle n’existe pas, écris « aucune ». Moins de 1000
Résous d’abord sans bornes, puis compare le plus petit candidat positif à l’intervalle demandé.
27 / 30 · Pièges sans réponse dans les conditions données
Le nombre recherché se trouve entre 200 et 400 inclus.
x ≡ 1 (mod 7) · x ≡ 1 (mod 9) · x ≡ 1 (mod 11)
Cherche une réponse dans les bornes indiquées ; si elle n’existe pas, écris « aucune ». De 200 · Jusqu’à 400
Résous d’abord sans bornes, puis compare le plus petit candidat positif à l’intervalle demandé.
29 / 30 · Pièges sans réponse dans les conditions données
Trouve le plus petit entier positif satisfaisant toutes les conditions.
x ≡ 2 (mod 4) · x ≡ 3 (mod 6) · x ≡ 4 (mod 8)
Pour des modules non premiers entre eux, les restes doivent coïncider modulo leur PGCD.
Chaque défi est généré à la demande : la réponse est calculée et non lue dans une liste fixe.