Calcul modulo (a mod n, congruences et puissance modulo n)

Choisissez un mode et saisissez des entiers. Le mode « Reste » accepte aussi les nombres négatifs et montre la différence entre le reste mathématique (positif ou nul) et l’opérateur % des langages de programmation.

Que calculer ?

Entier a

Entier b (à comparer)

Exposant k (puissance)

Modulo n (diviseur)

Saisissez uniquement des nombres entiers (pas de nombres décimaux ni de fractions). a, b et n peuvent compter jusqu’à 30 chiffres, l’exposant k est positif ou nul avec 9 chiffres au maximum, et le modulo n vaut au moins 1.

Résultat et figure

Choisissez un mode à gauche, saisissez des entiers et appuyez sur « Calculer ». Le résultat s’affiche ici (quand le modulo n vaut de 2 à 24, un cadran d’horloge montre aussi où tombe le reste).

Table des matières

[ Fermer X ]

Ce que vous pouvez faire sur cette page
À quoi sert ce calcul ?
Mode d'emploi
Formules et figures
Symboles et termes
- Symboles
- Termes
Ce qu’il est utile de savoir avant de commencer
Calculer avec Excel
Calculer avec Google Sheets
Calculer avec Python
Écrire la formule en LaTeX et autres langages mathématiques (à copier-coller)
Faire faire le calcul par ChatGPT
Les atouts de DataChef
Fonctions connexes
Liste des calculatrices NumberChef

Ce que vous pouvez faire sur cette page

Trouvez le reste de la division d’un entier $a$ par $n$. Les nombres négatifs sont acceptés (par exemple $-7$ divisé par $3$) : la page affiche côte à côte le reste mathématique ($0 \leqslant r < n$) et le résultat de l’opérateur % en C, Java, JavaScript et autres langages (qui peut être négatif)
Vérifiez si la congruence $a \equiv b \pmod{n}$ est vraie, avec la raison : la différence $a - b$ est-elle un multiple de $n$ ?
Obtenez le reste exact d’une énorme puissance, comme $7^{100}$ divisé par $13$, avec les étapes de l’exponentiation rapide (même les nombres trop grands pour une calculatrice ordinaire)
Visualisez le reste sur un cadran d’horloge (le cercle des restes modulo $n$) et voyez comment les restes tournent en boucle sur les mêmes positions (le cadran s’affiche quand le modulo $n$ vaut de 2 à 24)
Une explication simple des formules et des formules à copier-coller pour Excel, Google Sheets et Python sont réunies sur cette page

Le modulo $n$ est un entier supérieur ou égal à 1. Saisissez $a$, $b$ et $n$ avec 30 chiffres au maximum, et l’exposant $k$ comme un entier positif ou nul de 9 chiffres au maximum.

À quoi sert ce calcul ?

Horloge et calendrier (quel jour serons-nous dans N jours ?)

Sur un cadran de 12 heures, 14 h s’affiche sur le 2 : c’est exactement le calcul de reste 14 mod 12 = 2. Les jours de la semaine fonctionnent de la même façon, sur une horloge qui fait un tour tous les 7 jours. Par exemple, si nous sommes lundi, comme 100 mod 7 = 2, dans 100 jours nous serons « 2 jours après lundi », c’est-à-dire mercredi.
Agendas papier comme applications de calendrier font correspondre les dates et les jours de la semaine avec ce calcul de reste.

Les clés de contrôle qui repèrent les numéros erronés (codes-barres, ISBN, IBAN)

Le dernier chiffre d’un code-barres de produit (EAN-13) ou d’un ISBN de livre est une clé de contrôle calculée à partir des autres chiffres avec un reste. Pour un code EAN-13, par exemple, on multiplie les chiffres alternativement par 1 et par 3, on additionne, et le dernier chiffre est choisi à partir du reste de ce total divisé par 10.
Si un chiffre est mal saisi, le reste ne correspond plus, et la caisse ou le site marchand repère l’erreur aussitôt. La clé à deux chiffres du numéro de sécurité sociale (97 moins le reste de la division du numéro par 97) et le contrôle d’un IBAN (le reste de la division par 97 doit valoir 1) reposent sur la même idée.

Le chiffrement qui protège Internet (RSA)

RSA, le chiffrement à clé publique le plus connu, qui sert par exemple à transmettre des numéros de carte bancaire en toute sécurité, utilise directement « le reste d’une énorme puissance » dans ses calculs. Une puissance modulo n se calcule vite, mais remonter du résultat au nombre de départ est extrêmement difficile. C’est cette propriété à sens unique qui assure la sécurité.
L’exponentiation rapide, dont le mode « Puissance modulo » de cette page affiche les étapes, est le calcul que les logiciels de chiffrement effectuent tous les jours.

Programmation au quotidien (pair ou impair, chacun son tour)

En programmation, l’opérateur % sert tout le temps : i % 2 distingue les nombres pairs des impairs, et i % n crée un ordre qui recommence tous les n éléments (choisir le joueur suivant dans un jeu au tour par tour, revenir à la première diapositive après la dernière, etc.).
Avec des nombres négatifs, % donne des résultats différents selon les langages : connaître la différence entre « le reste mathématique et le % de C ou Java » aide à traquer les bugs.

Partager équitablement et compter ce qui reste (distribuer, ranger)

Partagez 63 crayons équitablement entre 12 personnes : chacune en reçoit 5 et il en reste 3 (63 = 12 × 5 + 3). Ranger un stock dans des cartons (combien de cartons pleins de n, et combien d’articles en trop), répartir des invités en groupes pour une fête : chaque situation « partager équitablement et voir ce qui reste » est ce calcul.
La division euclidienne a = n × q + r réunit toutes ces situations du quotidien en une seule formule.

Formules et figures

La division euclidienne (ce qu’est un reste)

Cadran d’horloge (modulo 12)

Notation mathématique (l’écriture habituelle)

$a$ $=$ $n$ $\times$ $q$ $+$ $r$

En mots (les symboles remplacés par des mots)

④ $a$ : dividende $=$ ① $n$ : diviseur (modulo) $\times$ ② $q$ : quotient $+$ ③ $r$ : reste

La formule en mots

① On prend le $n$ : diviseur (modulo)

② on le multiplie par le $q$ : quotient

③ et on ajoute le $r$ : reste (choisi pour que $0 \leqslant r < n$)

④ pour retrouver le $a$ : dividende . Il n’y a qu’une seule façon de l’écrire sous cette forme, et $r$ est « le reste de la division de $a$ par $n$ » ($a \bmod n$)

Exemple simple

On divise 38 par 12 (le même calcul qui fait que « 38 h » tombe sur le 2 d’un cadran de 12 heures)

dividende 38 $=$ diviseur 12 $\times$ quotient 3 $+$ reste 2

$38 = 12 \times 3 + 2$

$38 \bmod 12 = 2$

L’idée clé

En mathématiques, le reste $r$ est toujours choisi tel que $0 \leqslant r < n$. C’est vrai aussi pour les nombres négatifs. Pour diviser $-7$ par $3$, on écrit $-7 = 3 \times (-3) + 2$ : le quotient est arrondi à l’entier inférieur ($-3$) pour que le reste soit $2$ (division euclidienne). L’opérateur % des langages de programmation, en revanche, ne fonctionne pas pareil partout. En C, Java et JavaScript, -7 % 3 arrondit le quotient vers 0 (à $-2$), donc le résultat est $-1$ (le reste prend le signe du dividende). L’opérateur % de Python et Ruby et la fonction MOD d’Excel donnent au reste le signe du diviseur : ils renvoient $2$, comme en maths. Dans les programmes qui manipulent des restes de nombres négatifs, cette différence est une source de bugs fréquente : attention.

Définition de la congruence (ce que signifie a ≡ b (mod n))

Notation mathématique (l’écriture habituelle)

$a - b$ $=$ $n$ $\times$ $m$

En mots (les symboles remplacés par des mots)

③ $a - b$ : différence des deux entiers $=$ ① $n$ : modulo $\times$ ② $m$ : un entier

La formule en mots

① Quand le $n$ : modulo

② fois $m$ : un entier

③ est exactement égal à la $a - b$ : différence des deux entiers (c’est-à-dire quand la différence est un multiple de $n$), on écrit $a \equiv b \pmod{n}$ et on dit que « $a$ et $b$ sont congrus modulo $n$ »

Exemple simple

38 et 14 sont congrus modulo 12 ($38 \equiv 14 \pmod{12}$)

différence (38 − 14 = 24) $=$ modulo 12 $\times$ entier 2

$38 - 14 = 24 = 12 \times 2$

$38 \equiv 14 \pmod{12}$

L’idée clé

« La différence est un multiple de $n$ » et « les restes de la division par $n$ sont égaux » disent la même chose de deux façons (en effet, $38 \bmod 12 = 2$ et $14 \bmod 12 = 2$ : les restes sont égaux). C’est pourquoi on peut lire une congruence comme « une égalité qui ne regarde que les restes ». Pensez à une horloge : 38 h, 14 h et 2 h tombent toutes au même endroit du cadran de 12 heures. Le monde modulo $n$ est un cadran qui fait un tour tous les $n$, et des nombres congrus sont des nombres qui tombent au même endroit de ce cadran.

Multiplication et restes (la base du calcul d’une puissance modulo n)

Notation mathématique (l’écriture habituelle)

$(a \times b) \bmod n$ $=$ $\{(a \bmod n) \times (b \bmod n)\} \bmod n$

En mots (les symboles remplacés par des mots)

② reste du produit $=$ ① reste du produit des deux restes

La formule en mots

① Le reste du produit des deux restes

② est égal au reste du produit (on peut d’abord remplacer chaque nombre par son reste, puis multiplier)

Exemple simple

Le reste de 38 × 15 divisé par 12 se trouve à partir des seuls restes 2 et 3

reste du produit (38 × 15 = 570) $=$ reste 2 × reste 3 = 6

$38 \bmod 12 = 2,\quad 15 \bmod 12 = 3$

$2 \times 3 = 6$

$(38 \times 15) \bmod 12 = 570 \bmod 12 = 6$

L’idée clé

Grâce à cette propriété, inutile de mener une grande multiplication jusqu’au bout : on peut d’abord remplacer les nombres par leurs restes, puis multiplier. Une puissance étant une multiplication répétée, on peut trouver le reste de $7^{100}$ en ne suivant que les restes, sans jamais construire le nombre géant. C’est la base de l’exponentiation rapide (on élève au carré plusieurs fois en prenant le reste à chaque fois, on écrit l’exposant comme une somme de puissances de 2 et on multiplie les morceaux). Le mode « Puissance modulo » de cette calculatrice affiche ses étapes de cette façon. De plus, une puissance n’a que $n$ restes possibles : elle finit forcément par retomber sur un reste déjà obtenu, puis se répète en cycle (périodicité). Par exemple, le dernier chiffre de $7^{k}$ (son reste modulo $10$) prend tour à tour les valeurs 7, 9, 3, 1. Repérer un tel cycle est une technique classique des olympiades de mathématiques.

Propriétés des congruences (additionner, soustraire et multiplier membre à membre)

Notation mathématique (l’écriture habituelle)

$a + c$ $\equiv$ $b + d$ $\pmod{n}$

$a - c$ $\equiv$ $b - d$ $\pmod{n}$

$a \times c$ $\equiv$ $b \times d$ $\pmod{n}$

En mots (les symboles remplacés par des mots)

① $a + c$ : somme des membres de gauche $\equiv$ ② $b + d$ : somme des membres de droite $\pmod{n}$

$a - c$ : différence des membres de gauche $\equiv$ $b - d$ : différence des membres de droite $\pmod{n}$

$a \times c$ : produit des membres de gauche $\equiv$ $b \times d$ : produit des membres de droite $\pmod{n}$

La formule en mots

① Si $a \equiv b$ et $c \equiv d \pmod{n}$, alors la somme, différence ou produit des membres de gauche

② reste congru(e) à la somme, différence ou produit des membres de droite (on peut additionner, soustraire et multiplier des congruences comme des égalités ordinaires)

Exemple simple

Avec $38 \equiv 2$ et $15 \equiv 3 \pmod{12}$ :

38 + 15 = 53 $\equiv$ 2 + 3 = 5 $\pmod{12}$

$38 + 15 = 53 \equiv 5,\quad 2 + 3 = 5 \pmod{12}$

$38 \times 15 = 570 \equiv 6,\quad 2 \times 3 = 6 \pmod{12}$

L’idée clé

Ce qui rend cette propriété pratique, c’est que même avec de grands nombres, on peut d’abord les remplacer par leurs restes, puis additionner, soustraire ou multiplier. La seule opération qu’on ne peut pas faire librement, c’est la division. Par exemple, $6 \equiv 12 \pmod{6}$ est vraie, mais en divisant les deux membres par 2, on obtient $3 \equiv 6 \pmod{6}$, qui est fausse (la différence 3 n’est pas un multiple de 6). On ne peut diviser les deux membres que si le diviseur et le modulo sont premiers entre eux (leur PGCD vaut 1).

Le reste de la division d’un entier $a$ par $n$ est le $r$ de l’unique écriture $a = n \times q + r$ avec $0 \leqslant r < n$. La congruence $a \equiv b \pmod{n}$ signifie que la différence de $a$ et $b$ est un multiple de $n$ (autrement dit, ils ont le même reste dans la division par $n$), et on peut additionner, soustraire et multiplier des congruences comme des égalités. Grâce à cela, même le reste d’une énorme puissance se calcule vite par exponentiation rapide, en ne suivant que les restes.

Symboles et termes

Symboles

$\equiv$	est congru à	Le symbole de la congruence. C’est un signe égal à trois traits au lieu de deux : il signifie « égal dans le monde des restes », ce qui est moins fort que « exactement égal ».
$\bmod$ (mod)	modulo	L’abréviation de « modulo », du latin modulus (petite mesure). « $a \bmod n$ » désigne « le reste de la division de $a$ par $n$ », et « $\pmod{n}$ » écrit après une égalité annonce « on travaille modulo $n$ ». Dans les manuels français, on écrit aussi $a \equiv b\ [n]$.
$a,\ b$	a, b	Les entiers dont on étudie le reste. Dans une congruence, ce sont les deux entiers à gauche et à droite. Par tradition, on désigne les nombres fixés par les premières lettres de l’alphabet.
$n$	n	Le modulo (le nombre par lequel on divise). On utilise souvent la lettre $n$, comme « nombre ». Sur cette page, c’est un entier supérieur ou égal à 1.
$q$	q	Le quotient, d’après son initiale. Quand on divise un nombre négatif, le quotient est arrondi à l’entier inférieur pour que le reste soit positif ou nul (division euclidienne).
$r$	r	Le reste, d’après son initiale. En mathématiques, on le choisit toujours tel que $0 \leqslant r < n$.
$m$	m	L’entier de la définition de la congruence qui indique combien de fois le modulo est contenu dans la différence. Il peut être négatif ou nul.
$a^{k}$	a puissance k	Le produit de $k$ facteurs égaux à $a$ (une puissance). Le petit nombre $k$ en haut à droite est l’exposant, qui indique le nombre de facteurs.
%	pour cent (comme opérateur, modulo)	L’opérateur modulo, qui donne un reste dans de nombreux langages de programmation. C’est le même signe que le pourcentage, mais avec un autre rôle. En C, Java et JavaScript, son résultat pour les nombres négatifs peut différer du reste mathématique (voir l’idée clé de la formule 1).

Termes

reste	Ce qui reste quand une division ne tombe pas juste. En mathématiques, on le choisit toujours positif ou nul et strictement inférieur au diviseur.
quotient	L’entier qui indique combien de fois on peut retirer le diviseur. C’est le $q$ de la division euclidienne $a = n \times q + r$.
modulo	Le nombre $n$ par lequel on divise pour obtenir les restes avec lesquels on travaille. Sur un cadran d’horloge, c’est le nombre de graduations d’un tour complet. « Modulo 12 » veut dire « en regardant les restes de la division par 12 ».
congru	Deux entiers sont congrus modulo $n$ quand ils ont le même reste dans la division par $n$. C’est un terme d’arithmétique, différent des figures superposables en géométrie.
congruence	Une relation de la forme $a \equiv b \pmod{n}$. On peut additionner, soustraire et multiplier des congruences comme des égalités : les problèmes de restes se résolvent donc par des transformations. C’est un outil de base de l’arithmétique, utilisé en maths expertes (Terminale), aux olympiades et en informatique.
multiple	Un nombre obtenu en multipliant un entier par un autre entier. « La différence est un multiple du modulo » est la définition de la congruence.
division euclidienne	La division qui arrondit le quotient à l’entier inférieur quand le diviseur est positif : le reste est alors positif ou nul, même pour un dividende négatif. L’opérateur // de Python et la fonction ENT d’Excel fonctionnent ainsi.
opérateur modulo	L’opérateur % qui donne un reste en programmation. C, Java et JavaScript arrondissent le quotient vers 0 (le reste prend le signe du dividende). Python et Ruby utilisent la division euclidienne (le reste prend le signe du diviseur, donc il est positif ou nul quand le modulo est positif).
exponentiation rapide	Une méthode pour trouver le reste d’une énorme puissance avec peu de multiplications : on élève au carré plusieurs fois de suite en prenant le reste, on écrit l’exposant comme une somme de puissances de 2 et on multiplie les morceaux. On l’appelle aussi exponentiation par carrés successifs ; elle sert notamment dans le chiffrement RSA.
classe de congruence	L’idée de regrouper les entiers selon leur reste dans la division par $n$. Dans le monde modulo $n$, tout entier tombe dans l’un des $n$ groupes, de reste $0$ à $n-1$. Les nombres pairs et impairs sont le regroupement selon le reste de la division par 2.
périodicité	Le fait que les restes des puissances répètent le même motif. Il n’y a que $n$ restes possibles, donc ils finissent par revenir sur une valeur déjà vue. Repérer le cycle dans les problèmes de dernier chiffre (modulo 10) est un classique des olympiades.
premiers entre eux	Deux entiers sont premiers entre eux quand leur PGCD vaut 1. Cette notion apparaît dans la condition pour diviser les deux membres d’une congruence par un même nombre.

Ce qu’il est utile de savoir avant de commencer

Voici ce qu’il est utile de savoir pour utiliser le calcul de cette page en le comprenant, et pas seulement en appuyant sur le bouton.
Si vous bloquez, revoir ces notions est le chemin le plus court.

Division avec reste (CE2-CM1, 8-10 ans)	Savoir calculer que $17$ divisé par $5$ donne $3$, reste $2$ Savoir vérifier avec « diviseur × quotient + reste = dividende »
Multiples et diviseurs (CM1-6e, 9-12 ans)	Savoir que $24$ est un multiple de $12$ Savoir ce qu’est le PGCD (il sert dans la condition « premiers entre eux » pour diviser une congruence)
Nombres relatifs (5e-4e, 12-14 ans)	Savoir additionner, soustraire et multiplier des nombres négatifs (par exemple $3 \times (-3) = -9$) Savoir que $-3$ est plus petit que $-2$ (à sa gauche) sur une droite graduée
Puissances (4e-3e, 13-15 ans)	Savoir que l’exposant en haut à droite indique le nombre de facteurs, comme dans $3^{4} = 3 \times 3 \times 3 \times 3 = 81$ Savoir utiliser les règles de calcul sur les puissances $a^{m} \times a^{n} = a^{m+n}$ et $(a^{m})^{n} = a^{mn}$ (c’est grâce à elles que l’exponentiation rapide fonctionne)
Division euclidienne dans les entiers relatifs (Terminale maths expertes, 17-18 ans)	Savoir que la division d’un entier $a$ par un entier positif $n$ s’écrit d’une seule façon $a = nq + r$ (avec $0 \leqslant r < n$) Avoir déjà rencontré l’idée de regrouper les entiers en classes de congruence selon leur reste (pairs et impairs, c’est le regroupement selon le reste de la division par 2)

Calculer avec Excel

Copiez tout le tableau ci-dessous et collez-le dans la cellule A1 d’Excel. Il fonctionne tel quel.

Tableau pour calculer a mod n (le reste)

Dividende a	-7
Modulo (diviseur) n	3
Reste mathématique (positif ou nul)	=MOD(B1;B2)
Quotient (division euclidienne)	=ENT(B1/B2)
Vérification n × quotient + reste	=B2*B4+B3
Reste façon C/Java (arrondi vers 0)	=B1-B2*TRONQUE(B1/B2)

Tableau pour vérifier a ≡ b (mod n)

Entier a	38
Entier b	14
Modulo n	12
Différence a − b	=B1-B2
Reste de la différence ÷ n	=MOD(B4;B3)
Résultat (VRAI = congrus)	=MOD(B4;B3)=0

Tableau pour calculer une puissance modulo n (exponentiation rapide)

Base a	7
Exposant k	100
Modulo n	13
Reste de a^1	=MOD(B1;B3)
Reste de a^2 (carré de la ligne du dessus, puis reste)	=MOD(B4^2;$B$3)
Reste de a^4	=MOD(B5^2;$B$3)
Reste de a^8	=MOD(B6^2;$B$3)
Reste de a^16	=MOD(B7^2;$B$3)
Reste de a^32	=MOD(B8^2;$B$3)
Reste de a^64	=MOD(B9^2;$B$3)
Reste combiné pour 100 = 64 + 32 + 4	=MOD(MOD(B10B9;$B$3)B6;$B$3)

Une fois le tableau collé, il suffit de modifier les lignes du haut (les données) : les lignes du bas se calculent automatiquement.
La fonction MOD d’Excel renvoie le même « reste mathématique » (positif ou nul) que cette calculatrice. Même pour les nombres négatifs, =MOD(-7;3) vaut 2. S’il vous faut le reste façon C/Java, utilisez la dernière ligne du premier tableau, qui arrondit le quotient vers 0 avec TRONQUE.
Le premier tableau divise −7 par 3 : le reste est 2 et le quotient −3.
Le deuxième tableau vérifie 38 ≡ 14 (mod 12). Le reste de la différence 24 est 0 : il affiche VRAI (congrus).
Le troisième tableau calcule par exponentiation rapide le reste de 7 puissance 100 divisé par 13. La réponse est 9. « ^ » est le signe de la puissance. Excel ne calcule exactement qu’avec environ 15 chiffres : quand le modulo n dépasse 7 chiffres, les carrés perdent en précision. Dans ce cas, utilisez la calculatrice de cette page ou Python.

Calculer avec Google Sheets

Copiez tout le tableau ci-dessous et collez-le dans la cellule A1 de Google Sheets. Il fonctionne tel quel.

Tableau pour calculer a mod n (le reste)

Dividende a	-7
Modulo (diviseur) n	3
Reste mathématique (positif ou nul)	=MOD(B1;B2)
Quotient (division euclidienne)	=ENT(B1/B2)
Vérification n × quotient + reste	=B2*B4+B3
Reste façon C/Java (arrondi vers 0)	=B1-B2*TRONQUE(B1/B2)

Tableau pour vérifier a ≡ b (mod n)

Entier a	38
Entier b	14
Modulo n	12
Différence a − b	=B1-B2
Reste de la différence ÷ n	=MOD(B4;B3)
Résultat (VRAI = congrus)	=MOD(B4;B3)=0

Tableau pour calculer une puissance modulo n (exponentiation rapide)

Base a	7
Exposant k	100
Modulo n	13
Reste de a^1	=MOD(B1;B3)
Reste de a^2 (carré de la ligne du dessus, puis reste)	=MOD(B4^2;$B$3)
Reste de a^4	=MOD(B5^2;$B$3)
Reste de a^8	=MOD(B6^2;$B$3)
Reste de a^16	=MOD(B7^2;$B$3)
Reste de a^32	=MOD(B8^2;$B$3)
Reste de a^64	=MOD(B9^2;$B$3)
Reste combiné pour 100 = 64 + 32 + 4	=MOD(MOD(B10B9;$B$3)B6;$B$3)

Les formules d’Excel (MOD, ENT, TRONQUE) fonctionnent telles quelles dans Google Sheets en français. Copiez tout le tableau, collez-le dans la cellule A1 et remplacez les données par vos propres nombres.

Calculer avec Python

a = -7
n = 3

# le % de Python renvoie le même « reste mathématique » que cette calculatrice (positif ou nul quand le modulo est positif)
print(a % n)                 # 2

# divmod renvoie ensemble le quotient de la division euclidienne et le reste (a = n × quotient + reste)
quotient, remainder = divmod(a, n)
print(quotient, remainder)   # -3 2

# congruence : 38 ≡ 14 (mod 12) ? (on vérifie si la différence est un multiple de 12)
print((38 - 14) % 12 == 0)   # True

# puissance modulo n : reste de 7 puissance 100 divisé par 13
# pow à 3 arguments utilise l'exponentiation rapide, donc le calcul est instantané même pour d'énormes exposants
print(pow(7, 100, 13))       # 9

def c_style_mod(x, m):
    # même résultat que % en C, Java et JavaScript (quotient arrondi vers 0)
    r = x % m
    if r != 0 and x < 0:
        r -= m
    return r

print(c_style_mod(-7, 3))    # -1

L’opérateur % de Python correspond au reste mathématique. Quand le diviseur est positif, il renvoie une valeur positive ou nulle, même pour les nombres négatifs (-7 % 3 vaut 2). Pour une puissance modulo n, la forme à 3 arguments pow(base, exposant, modulo) applique l’exponentiation rapide en interne et trouve vite le seul reste, même pour des puissances de dizaines de milliers de chiffres. S’il vous faut le même résultat que % en C, Java et JavaScript, ajoutez une correction qui arrondit le quotient vers 0, comme dans la dernière fonction.

Écrire la formule en LaTeX et autres langages mathématiques (à copier-coller)

La division euclidienne (ce qu’est un reste)

a = n × q + r (0 ⩽ r < n)

a = nq + r \quad (0 \leqslant r < n)

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>a</mi><mo>=</mo><mi>n</mi><mi>q</mi><mo>+</mo><mi>r</mi>
    <mo>,</mo>
    <mn>0</mn><mo>&#x2A7D;</mo><mi>r</mi><mo>&lt;</mo><mi>n</mi>
  </mrow>
</math>

a = n q + r, \ 0 <= r < n

{Quotient[a, n], Mod[a, n]}

q := floor(a/n); r := a mod n;

q = floor(a/n); r = mod(a, n);

a = nq + r (0 ⩽ r < n)

Définition de la congruence (ce que signifie a ≡ b (mod n))

a ≡ b (mod n)  ⇔  a − b = n × m

a \equiv b \pmod{n} \iff a - b = nm

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>a</mi><mo>&#x2261;</mo><mi>b</mi>
    <mspace width="0,3em"/>
    <mo>(</mo><mi>mod</mi><mspace width="0,3em"/><mi>n</mi><mo>)</mo>
    <mo>&#x21D4;</mo>
    <mi>a</mi><mo>&#x2212;</mo><mi>b</mi><mo>=</mo><mi>n</mi><mi>m</mi>
  </mrow>
</math>

a -= b (mod n) iff a - b = n m

Mod[a - b, n] == 0

(a - b) mod n = 0;

mod(a - b, n) == 0

a ≡ b (mod n)

Multiplication et restes (la base du calcul d’une puissance modulo n)

(a × b) mod n = {(a mod n) × (b mod n)} mod n

(a \times b) \bmod n = \{(a \bmod n)(b \bmod n)\} \bmod n

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mo>(</mo><mi>a</mi><mo>&#xD7;</mo><mi>b</mi><mo>)</mo>
    <mspace width="0,3em"/><mi>mod</mi><mspace width="0,3em"/><mi>n</mi>
    <mo>=</mo>
    <mo>{</mo>
    <mo>(</mo><mi>a</mi><mspace width="0,3em"/><mi>mod</mi><mspace width="0,3em"/><mi>n</mi><mo>)</mo>
    <mo>&#xD7;</mo>
    <mo>(</mo><mi>b</mi><mspace width="0,3em"/><mi>mod</mi><mspace width="0,3em"/><mi>n</mi><mo>)</mo>
    <mo>}</mo>
    <mspace width="0,3em"/><mi>mod</mi><mspace width="0,3em"/><mi>n</mi>
  </mrow>
</math>

(a * b) mod n = ((a mod n) * (b mod n)) mod n

Mod[a b, n] == Mod[Mod[a, n] Mod[b, n], n]

(a * b) mod n = ((a mod n) * (b mod n)) mod n;

mod(a*b, n) == mod(mod(a, n)*mod(b, n), n)

(a×b) mod n = ((a mod n)×(b mod n)) mod n

Propriétés des congruences (additionner, soustraire et multiplier membre à membre)

a ≡ b, c ≡ d (mod n) ⇒ a+c ≡ b+d, a−c ≡ b−d, a×c ≡ b×d (mod n)

a \equiv b,\ c \equiv d \pmod{n} \Rightarrow a + c \equiv b + d,\ a - c \equiv b - d,\ ac \equiv bd \pmod{n}

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>a</mi><mo>+</mo><mi>c</mi><mo>&#x2261;</mo><mi>b</mi><mo>+</mo><mi>d</mi>
    <mo>,</mo>
    <mi>a</mi><mo>&#x2212;</mo><mi>c</mi><mo>&#x2261;</mo><mi>b</mi><mo>&#x2212;</mo><mi>d</mi>
    <mo>,</mo>
    <mi>a</mi><mi>c</mi><mo>&#x2261;</mo><mi>b</mi><mi>d</mi>
    <mspace width="0,3em"/>
    <mo>(</mo><mi>mod</mi><mspace width="0,3em"/><mi>n</mi><mo>)</mo>
  </mrow>
</math>

a + c -= b + d, \ a - c -= b - d, \ a c -= b d (mod n)

Mod[a + c, n] == Mod[b + d, n] && Mod[a - c, n] == Mod[b - d, n] && Mod[a c, n] == Mod[b d, n]

(a + c) mod n = (b + d) mod n;

mod(a + c, n) == mod(b + d, n)

a + c ≡ b + d (mod n)

Faire faire le calcul par ChatGPT

Tu es un assistant de calcul en arithmétique (propriétés des nombres entiers). Effectue le calcul suivant en exécutant réellement du code Python, et fonde ta réponse uniquement sur les nombres obtenus à l’exécution (ne réponds pas de tête ni par estimation).

Traite les 3 problèmes suivants.
1. Le reste mathématique de −7 divisé par 3 (choisi positif ou nul) et le quotient
2. Si 38 ≡ 14 (mod 12) est vraie (indique aussi si la différence est un multiple de 12)
3. Le reste de 7 puissance 100 divisé par 13 (utilise pow(7, 100, 13))

Utilise %, divmod et pow(base, exposant, modulo) de Python, et indique les formules utilisées et les nombres obtenus à l’exécution.

Mode d'emploi

1

Saisissez vos nombres

Tapez les nombres à calculer dans les champs de saisie
2

Calculez

Appuyez sur le bouton « Calculer »
3

Lisez le résultat

Le résultat s’affiche aussitôt. La même page explique aussi le raisonnement et la formule

Les atouts de DataChef

Simple et gratuit

Conversions gratuites et illimitées
Aucune compétence requise – simple et intuitif

Aucune inscription requise

Utilisable dès l'ouverture de la page
Aucune donnée personnelle nécessaire

Sûr et fiable

Connexion fortement chiffrée (SSL)
Le fichier est supprimé automatiquement après le téléchargement

Rapide

Affichage et conversion rapides, sans attente

Sans filigrane

Aucun filigrane
Aucune mention de crédit nécessaire

Usage commercial autorisé

Usage commercial gratuit
Aucune autorisation préalable nécessaire

\(\equiv\)	est congru à	Le symbole de la congruence. C’est un signe égal à trois traits au lieu de deux : il signifie « égal dans le monde des restes », ce qui est moins fort que « exactement égal ».
\(\bmod\) (mod)	modulo	L’abréviation de « modulo », du latin modulus (petite mesure). « \(a \bmod n\) » désigne « le reste de la division de \(a\) par \(n\) », et « \(\pmod{n}\) » écrit après une égalité annonce « on travaille modulo \(n\) ». Dans les manuels français, on écrit aussi \(a \equiv b\ [n]\).
\(a,\ b\)	a, b	Les entiers dont on étudie le reste. Dans une congruence, ce sont les deux entiers à gauche et à droite. Par tradition, on désigne les nombres fixés par les premières lettres de l’alphabet.
\(n\)	n	Le modulo (le nombre par lequel on divise). On utilise souvent la lettre \(n\), comme « nombre ». Sur cette page, c’est un entier supérieur ou égal à 1.
\(q\)	q	Le quotient, d’après son initiale. Quand on divise un nombre négatif, le quotient est arrondi à l’entier inférieur pour que le reste soit positif ou nul (division euclidienne).
\(r\)	r	Le reste, d’après son initiale. En mathématiques, on le choisit toujours tel que \(0 \leqslant r < n\).
\(m\)	m	L’entier de la définition de la congruence qui indique combien de fois le modulo est contenu dans la différence. Il peut être négatif ou nul.
\(a^{k}\)	a puissance k	Le produit de \(k\) facteurs égaux à \(a\) (une puissance). Le petit nombre \(k\) en haut à droite est l’exposant, qui indique le nombre de facteurs.
%	pour cent (comme opérateur, modulo)	L’opérateur modulo, qui donne un reste dans de nombreux langages de programmation. C’est le même signe que le pourcentage, mais avec un autre rôle. En C, Java et JavaScript, son résultat pour les nombres négatifs peut différer du reste mathématique (voir l’idée clé de la formule 1).

Division avec reste (CE2-CM1, 8-10 ans)	Savoir calculer que \(17\) divisé par \(5\) donne \(3\), reste \(2\) Savoir vérifier avec « diviseur × quotient + reste = dividende »
Multiples et diviseurs (CM1-6e, 9-12 ans)	Savoir que \(24\) est un multiple de \(12\) Savoir ce qu’est le PGCD (il sert dans la condition « premiers entre eux » pour diviser une congruence)
Nombres relatifs (5e-4e, 12-14 ans)	Savoir additionner, soustraire et multiplier des nombres négatifs (par exemple \(3 \times (-3) = -9\)) Savoir que \(-3\) est plus petit que \(-2\) (à sa gauche) sur une droite graduée
Puissances (4e-3e, 13-15 ans)	Savoir que l’exposant en haut à droite indique le nombre de facteurs, comme dans \(3^{4} = 3 \times 3 \times 3 \times 3 = 81\) Savoir utiliser les règles de calcul sur les puissances \(a^{m} \times a^{n} = a^{m+n}\) et \((a^{m})^{n} = a^{mn}\) (c’est grâce à elles que l’exponentiation rapide fonctionne)
Division euclidienne dans les entiers relatifs (Terminale maths expertes, 17-18 ans)	Savoir que la division d’un entier \(a\) par un entier positif \(n\) s’écrit d’une seule façon \(a = nq + r\) (avec \(0 \leqslant r < n\)) Avoir déjà rencontré l’idée de regrouper les entiers en classes de congruence selon leur reste (pairs et impairs, c’est le regroupement selon le reste de la division par 2)

Calcul modulo (a mod n, congruences et puissance modulo n)

Table des matières

Ce que vous pouvez faire sur cette page

À quoi sert ce calcul ?

Formules et figures

Symboles et termes

Symboles

Termes

Ce qu’il est utile de savoir avant de commencer

Calculer avec Excel

Calculer avec Google Sheets

Calculer avec Python

Écrire la formule en LaTeX et autres langages mathématiques (à copier-coller)

Faire faire le calcul par ChatGPT

Mode d'emploi

Les atouts de DataChef

Fonctions connexes

Résoudre une équation diophantienne ax + by = c (avec l’algorithme d’Euclide)

Résout ax + by = c en nombres entiers, avec les étapes de l’algorithme d’Euclide, la solution générale et les solutions positives seulement

Calcul du PGCD (plus grand commun diviseur)

Calcule le PGCD de deux nombres entiers ou plus, avec la décomposition en facteurs premiers et l’algorithme d’Euclide expliqués

Division posée en ligne (quotient et reste, étape par étape)

Pose la division des nombres entiers et décimaux, avec chaque étape expliquée (diviser, multiplier, soustraire, abaisser)

Recommandé

Probabilités et nombres aléatoires

Moyennes et statistiques

Pourcentages et proportions

Vitesse

Masse volumique et concentration

Physique et électricité

Conversion d’unités

Nombres entiers et relatifs

Fractions, décimaux et arrondis

Équations et inéquations

Polynômes

Racines carrées et racines n-ièmes

Puissances et logarithmes

Nombres complexes

Fonctions et courbes

Suites

Vecteurs

Matrices

Géométrie plane

Géométrie dans l’espace

Dates et heures

Finance et économie

Marketing web et indicateurs publicitaires

Santé et forme

Sport

Météo

Informatique

Énergie et budget du foyer

Voiture

Solaire et batteries

Maison et bricolage

À quoi sert ce calcul ?