Définition : Diviseur, multiple et témoin entier

Soient \(d,a\in\mathbb{Z}\). On dit que \(d\) divise \(a\), et on écrit \(d\mid a\), s’il existe un entier \(k\in\mathbb{Z}\) tel que \(a=dk\). On dit aussi que \(d\) est un diviseur de \(a\), ou que \(a\) est un multiple de \(d\). L’entier \(k\) justifie la divisibilité.

Ainsi \(-35=7\times(-5)\) prouve que \(7\mid-35\). En revanche, \(12=5\times2{,}4\) ne prouve pas que \(5\mid12\) : \(2{,}4\notin\mathbb{Z}\).

Propriétés : Zéro, signes et quotient

Pour tout entier \(a\), \(1\mid a\), \(-1\mid a\) et \(a\mid0\). De plus, \(0\mid a\) si et seulement si \(a=0\) : en particulier, \(0\mid0\).

Changer le signe du diviseur ou du dividende ne change pas la divisibilité. Si \(d\ne0\), on dispose du critère

Lemme : Borner les diviseurs et les rechercher par paires

Si \(a\ne0\) et \(d\mid a\), alors \(d\ne0\) et \(1\leqslant |d|\leqslant |a|\). Pour \(N\geqslant1\), si \(N=de\) avec \(d,e\) positifs, au moins l’un des deux facteurs vérifie \(d\leqslant\sqrt N\) ou \(e\leqslant\sqrt N\).

Méthode : Lister tous les diviseurs d’un entier non nul

On travaille d’abord avec \(N=|a|\). Pour chaque entier \(d\geqslant1\) tel que \(d^2\leqslant N\), on teste si \(N/d\) est entier. Dans ce cas, on inscrit les deux partenaires \(d\) et \(N/d\), sans doublon s’ils sont égaux. On range les diviseurs positifs puis on ajoute leurs opposés pour une liste dans \(\mathbb{Z}\). Le lemme garantit qu’aucune paire n’est oubliée.

Exemple : Tous les diviseurs de \(-84\)

Comme \(9^2\leqslant84<10^2\), on teste \(d=1,\ldots,9\). Les paires retenues pour \(84\) sont

Contrôle. Chaque paire a pour produit \(84\) ; les signes se vérifient en changeant celui du partenaire. Il y a \(24\) diviseurs entiers, aucun n’est nul.

Propriétés : Transitivité et produit

Pour des entiers \(a,b,c,d,d_1,d_2,a_1,a_2\) :

• si \(d\mid a\) et \(a\mid b\), alors \(d\mid b\) ;

• si \(d\mid a\), alors \(d\mid ca\) ;

• si \(d_1\mid a_1\) et \(d_2\mid a_2\), alors \(d_1d_2\mid a_1a_2\).

Théorème : Stabilité par combinaison linéaire entière

Si \(d\mid a\) et \(d\mid b\), alors, pour tous \(u,v\in\mathbb{Z}\),

Corollaire : Enlever un multiple du diviseur

Pour \(a,d,k\in\mathbb{Z}\),

Piège : Ne pas inverser une implication

\(d\mid(a+b)\) n’impose pas \(d\mid a\) ni \(d\mid b\) : \(3\mid(1+2)\). De même \(6\mid2\times3\), mais \(6\nmid2\) et \(6\nmid3\). Les coefficients de la combinaison doivent être entiers : la moitié d’un multiple de \(2\) n’est pas nécessairement un multiple de \(2\).

Méthode : Une divisibilité contenant l’inconnue

Lorsqu’un diviseur et le nombre à diviser dépendent du même entier \(n\), chercher une combinaison qui supprime \(n\). Transformer par équivalence, puis exploiter une liste finie de diviseurs. Vérifier les valeurs interdites et la réciproque.

Exemple : Résoudre \(n-2\mid3n+4\) dans \(\mathbb{Z}\)

On écrit \(3n+4=3(n-2)+10\). Le corollaire donne

Contrôle. Pour chacune de ces valeurs, \(10=(n-2)k\) avec \(k\in\mathbb{Z}\), donc \(3n+4=(n-2)(3+k)\) : toutes conviennent. La valeur \(n=2\) ne convient pas, car \(0\nmid10\).

Méthode : Factoriser une équation à inconnues entières

Une équation diophantienne cherche des solutions entières. Si elle se ramène à \(uv=N\ne0\), les couples ordonnés possibles sont \((u,v)=(d,N/d)\), où \(d\) parcourt tous les diviseurs entiers de \(N\). En effet, \(uv=N\) impose \(u\mid N\) et \(v=N/u\) ; la réciproque est immédiate.

Revenir ensuite aux inconnues initiales et contrôler leur intégralité. Si \(N=0\), il faut traiter séparément \(u=0\) ou \(v=0\) : la liste finie ne s’applique plus.

Exemple : Compléter un produit

Résolvons \(xy-2x+3y=11\) dans \(\mathbb{Z}^2\). Comme

Ce sont les quatre solutions \((-2,7),(2,3),(-4,-3),(-8,1)\).

Contrôle. Toute ligne a un produit égal à \(5\) ; en développant et en ajoutant \(6\), on retrouve \(xy-2x+3y=11\). L’énumération des diviseurs de \(5\) garantit l’exhaustivité.

Exemple : Un retour aux inconnues qui impose la parité

Pour \(x^2-y^2=32\), poser \(u=x-y\) et \(v=x+y\) donne \(uv=32\) et

Contrôle. \(9^2-7^2=81-49=32\) et \(6^2-2^2=36-4=32\) ; les signes ne changent pas les carrés. La restriction à \(\mathbb{N}^2\) ne garderait que \((9,7)\) et \((6,2)\).

Théorème : Existence et unicité

Pour tout \(a\in\mathbb{Z}\) et tout entier \(b\geqslant1\), il existe un unique couple \((q,r)\in\mathbb{Z}^2\) tel que

Lemme : Un petit multiple est nul

Si \(b\geqslant1\), \(b\mid t\) et \(-b<t<b\), alors \(t=0\).

Corollaire : Divisibilité et reste nul

Pour \(b\geqslant1\), \(b\mid a\) si et seulement si le reste de la division de \(a\) par \(b\) vaut \(0\).

Méthode : Effectuer puis vérifier une division

Trouver deux multiples consécutifs tels que \(bq\leqslant a<b(q+1)\). Calculer \(r=a-bq\), puis contrôler à la fois l’identité \(a=bq+r\) et les bornes \(0\leqslant r<b\). Pour un dividende négatif, ne pas seulement changer le signe du quotient et du reste.

Exemple : Diviser \(173\), \(-173\) et \(-180\) par \(12\)

Exemple : Exploiter une contrainte sur quotient et reste

Un entier \(a\) est divisé par \(6\) ; on impose \(q=2r+1\). Écrivons toutes les conditions :

Réciproquement, chaque colonne satisfait \(a=6q+r\) et \(0\leqslant r<6\) ; elle fournit donc une division valable. Sans la borne sur \(r\), on obtiendrait des candidats qui ne répondent pas au problème.

Définition : Congruence modulo un entier

On fixe un entier \(n\geqslant2\). Pour \(a,b\in\mathbb{Z}\),

Théorème : Caractérisation par les restes

Deux entiers sont congrus modulo \(n\) si et seulement si leurs divisions euclidiennes par \(n\) ont le même reste.

Propriétés : Trois règles de raisonnement

Pour un même module \(n\), \(a\equiv a\) ; si \(a\equiv b\), alors \(b\equiv a\) ; si \(a\equiv b\) et \(b\equiv c\), alors \(a\equiv c\). Ces trois propriétés sont la réflexivité, la symétrie et la transitivité.

Corollaire : Décrire tous les entiers d’un même reste

Si \(r\) est le reste de \(a\) modulo \(n\), alors

Méthode : Prouver une congruence ou borner ses solutions

Pour comparer deux entiers : tester leur différence ou comparer leurs restes. Pour chercher tous les entiers d’un même reste : écrire \(x=r+nk\). S’il existe des bornes sur \(x\), les traduire en bornes sur l’entier \(k\).

Exemple : \(-58\) et \(23\) modulo \(9\)

La différence vaut \(-81=9(-9)\), donc \(-58\equiv23\pmod9\). On retrouve ce fait par \(-58=9(-7)+5\) et \(23=9\times2+5\).

Pour résoudre \(x\equiv23\pmod9\) avec \(-20\leqslant x\leqslant20\), on écrit

Contrôle. Elles appartiennent à l’intervalle demandé et chacune a pour reste \(5\).

Théorème : Compatibilité avec les opérations

Pour un même module \(n\geqslant2\), si \(a\equiv a'\pmod n\) et \(b\equiv b'\pmod n\), alors

Théorème : Puissances naturelles

Si \(a\equiv b\pmod n\), alors \(a^p\equiv b^p\pmod n\) pour tout entier \(p\geqslant1\). Pour \(p=0\), l’égalité \(a^0=b^0=1\) convient lorsque \(a\) et \(b\) sont non nuls. On ne donne pas ici de sens à \(0^0\).

Méthode : Réduire avant de calculer

Remplacer chaque entier par un représentant plus simple pour le même module. Appliquer les règles précédentes et réduire de nouveau les résultats intermédiaires. Si l’on demande le reste, terminer par le représentant compris entre \(0\) et \(n-1\).

Exemple : Reste de \(47\times83-19^2\) modulo \(12\)

On a \(47\equiv-1\), \(83\equiv-1\) et \(19\equiv7\pmod{12}\). Donc

Contrôle. Le calcul direct donne \(47\times83-19^2=3901-361=3540=12\times295\).

Propriété : Passer à un module diviseur

Si \(a\equiv b\pmod n\) et si \(d\geqslant2\) divise \(n\), alors \(a\equiv b\pmod d\).

Théorème : Une simplification qui change aussi le module

Pour \(c\geqslant1\), \(m\geqslant2\) entiers et \(a,b\in\mathbb{Z}\),

Piège : On ne divise pas librement une congruence

\(3\equiv9\pmod6\) est vraie, mais \(1\equiv3\pmod6\) est fausse. La simplification correcte est \(1\equiv3\pmod2\). De même,

On ne peut pas non plus extraire arbitrairement des racines : \(2^2\equiv3^2\pmod5\), alors que \(2\not\equiv3\pmod5\). Enfin un produit nul modulo \(6\) n’impose pas un facteur nul modulo \(6\) : \(2\times3\equiv0\).

Méthode : Chercher d’abord \(0\), \(1\) ou \(-1\)

Réduire la base avant toute autre recherche. Pour un exposant entier \(p\geqslant1\), une base congrue à \(0\) donne un reste nul ; une base congrue à \(1\) donne un reste \(1\) ; une base congrue à \(-1\) donne \((-1)^p\), donc dépend de la parité de \(p\). Ces règles découlent du théorème sur les puissances.

Théorème : Réduire l’exposant grâce à un retour à \(1\)

Soient \(a\in\mathbb{Z}\setminus\{0\}\), \(m\geqslant2\) et \(T\geqslant1\) entiers. Si \(a^T\equiv1\pmod m\) et si \(p=Tq+r\) est la division euclidienne de \(p\in\mathbb{N}\) par \(T\), alors

Exemple : Reste de \(36^{2027}\) modulo \(11\)

Comme \(36\equiv3\pmod{11}\), on étudie les puissances de \(3\).

Les étapes se calculent en multipliant le reste précédent par \(3\), puis en réduisant : \(27\equiv5\), \(15\equiv4\), \(12\equiv1\pmod{11}\). En particulier \(3^5=243=11\times22+1\).

Contrôle. L’exposant se divise par \(5\), longueur du retour à \(1\), et non par \(11\). Si son reste avait été \(0\), on aurait obtenu \(3^0=1\), pas \(0\).

Piège : Le retour à \(1\) n’est pas garanti

Modulo \(8\), les restes de \(2^p\) pour \(p=0,1,2,3,\ldots\) sont \(1,2,4,0,0,\ldots\). Pour \(p\geqslant3\), \(2^p=8\times2^{p-3}\), donc le reste vaut \(0\). Il n’y a pas de retour à \(1\) après l’exposant \(0\) : le théorème précédent ne s’applique pas.

Méthode : Variante : les carrés successifs

Si aucun cycle court n’est commode, calculer les restes de \(a,a^2,a^4,a^8,\ldots\) en élevant au carré le représentant précédent. Décomposer ensuite l’exposant en somme de puissances de \(2\) et multiplier les termes utiles. La règle \((a^u)^2=a^{2u}\) et la compatibilité avec le produit justifient la méthode.

Exemple : \(7^{117}\) modulo \(13\)

Les carrés successifs donnent :

En effet \(49\equiv10\), \(100\equiv9\), \(81\equiv3\), puis \(9\equiv9\pmod{13}\) ; les carrés suivants redonnent alternativement \(3\) et \(9\). Comme \(117=64+32+16+4+1\),

Théorème : Une recherche exhaustive par les restes

Pour résoudre \(ax\equiv b\pmod m\) dans \(\mathbb{Z}\), il suffit de tester \(r=0,1,\ldots,m-1\). Chaque reste \(r\) qui vérifie \(ar\equiv b\pmod m\) fournit toutes les solutions \(x=r+mk\), \(k\in\mathbb{Z}\).

Exemple : Plusieurs restes solutions : \(4x\equiv6\pmod{10}\)

Les restes solutions sont \(4\) et \(9\). Par conséquent

Contrôle. \(4(4+10k)-6=10(1+4k)\) et \(4(9+10k)-6=10(3+4k)\) sont bien des multiples de \(10\).

Définition : Inverse modulo \(m\)

Un entier \(c\) est un inverse de \(a\) modulo \(m\) si \(ac\equiv1\pmod m\). Il ne s’agit pas de la fraction réelle \(1/a\). Pour le déterminer avec un petit module, tester les restes \(0,\ldots,m-1\) et chercher un produit de reste \(1\).

Exemple : Un inverse trouvé et un cas sans inverse

Modulo \(7\), les produits \(3\times1,3\times2,\ldots,3\times5\) ont pour restes \(3,6,2,5,1\). Ainsi \(5\) est un inverse de \(3\) : \(3\times5=15=7\times2+1\).

En revanche, \(4\) n’a pas d’inverse modulo \(10\) : \(4c=1+10k\) serait une égalité entre un entier pair et un entier impair. Cela n’empêche pas \(4x\equiv6\pmod{10}\) d’avoir des solutions, comme on vient de le voir.

Propriété : Unicité du reste de l’inverse

Si \(c\) et \(d\) sont des inverses de \(a\) modulo \(m\), alors \(c\equiv d\pmod m\). Il y a donc au plus un inverse dans \(\{0,\ldots,m-1\}\).

Théorème : Résoudre grâce à un inverse vérifié

Si \(ac\equiv1\pmod m\), alors

Méthode : Tableau ou inverse ?

Pour un petit module, le tableau des restes est toujours possible et exhaustif. Si l’on repère un inverse, le vérifier d’abord ; multiplier ensuite les deux membres, réduire le résultat, puis écrire toutes les solutions entières. Ne jamais déduire « aucune solution » de la seule absence d’inverse.

Exemple : Une famille ou aucune solution

Pour \(3x\equiv4\pmod7\), l’inverse \(5\) donne \(x\equiv5\times4=20\equiv6\pmod7\). Les solutions sont \(x=6+7k\), \(k\in\mathbb{Z}\).

Contrôle. \(3(6+7k)-4=18+21k-4=14+21k=7(2+3k)\).

En revanche, \(6y\equiv5\pmod9\) n’a aucune solution entière. En effet, \(6y-5=9k\) imposerait \(5=6y-9k=3(2y-3k)\), donc \(3\mid5\), ce qui est faux.

Notation : Écriture décimale et valeur des chiffres

Un entier naturel \(N=\overline{a_sa_{s-1}\ldots a_1a_0}\) s’écrit

Théorème : Un critère fondé sur les derniers chiffres

Soient \(s\geqslant1\) et \(d\geqslant2\) des entiers. Si \(d\) divise \(10^s\) et si \(N=10^s A+B\), avec \(A,B\in\mathbb{N}\) et \(0\leqslant B<10^s\), alors

Théorème : Somme des chiffres : critères de \(3\) et de \(9\)

Si \(S=a_0+a_1+\cdots+a_s\), alors \(N\equiv S\pmod3\) et \(N\equiv S\pmod9\). Ainsi \(N\) est divisible par \(3\) (respectivement par \(9\)) si et seulement si \(S\) est divisible par \(3\) (respectivement par \(9\)).

Exemple : \(583\,146\)

La somme des chiffres est \(5+8+3+1+4+6=27\). Comme \(27\) est divisible par \(9\), \(583\,146\) l’est aussi, et donc il est également divisible par \(3\).

Contrôle. \(583\,146=9\times64\,794\). Le critère donne une divisibilité, pas le quotient \(64\,794\).

Théorème : Somme alternée : critère de \(11\)

Soit \(A=a_0-a_1+a_2-a_3+\cdots+(-1)^s a_s\), la somme alternée en commençant par le chiffre des unités. Alors \(N\equiv A\pmod{11}\), donc

Exemple : \(604\,879\)

En partant des unités, \(A=9-7+8-4+0-6=0\). Le nombre est donc divisible par \(11\) : \(604\,879=11\times54\,989\). Sa somme de chiffres vaut \(6+0+4+8+7+9=34\) ; il n’est divisible ni par \(3\) ni par \(9\).

Commencer la somme alternée par la gauche peut changer son signe, mais pas sa divisibilité par \(11\). Il faut obtenir un multiple de \(11\), pas nécessairement \(0\). La somme alternée, éventuellement négative, n’est pas toujours le reste euclidien.

Méthode : Choisir le raisonnement

Une assertion portant sur tous les entiers ne se prouve pas par quelques essais. On peut factoriser, construire un témoin entier ou examiner tous les restes pour un module pertinent. Pour réfuter une assertion universelle, un seul contre-exemple suffit.

Pour prouver une impossibilité, chercher un module pour lequel les deux membres ne peuvent pas avoir le même reste. L’absence de contradiction pour un module ne suffit pas, à elle seule, à établir l’existence d’une solution.

Lemme : De \(2\) et \(3\) à \(6\)

Un entier divisible à la fois par \(2\) et par \(3\) est divisible par \(6\).

Propriété : Un produit de trois entiers consécutifs

Pour tout \(n\in\mathbb{Z}\), \(6\mid n^3-n\).

Propriété : Restes d’un carré modulo \(4\)

Le carré d’un entier a pour reste \(0\) ou \(1\) modulo \(4\).

Corollaire : Une famille d’équations sans solution entière

Pour tout entier \(k\), l’équation \(x^2+y^2=4k+3\) n’a aucune solution dans \(\mathbb{Z}^2\).

Définition : Coder les lettres par des entiers

On associe aux lettres \(A,B,\ldots,Z\) les rangs \(0,1,\ldots,25\). On travaille sans accents ni espaces dans les exemples. Le chiffrement étudié transforme le rang \(x\) en l’unique rang \(y\) tel que

Propriété : Déchiffrer grâce à l’inverse de \(5\)

Le rang de départ est l’unique entier \(x\) entre \(0\) et \(25\) vérifiant

Exemple : Chiffrer puis déchiffrer MATH

Le message chiffré est PHYQ. Les réductions sont \(67=26\times2+15\), \(102=26\times3+24\) et \(42=26+16\).

Pour déchiffrer, soustraire \(7\) avant de multiplier par \(21\) :

Contrôle. \(168=26\times6+12\), \(357=26\times13+19\) et \(189=26\times7+7\). Le message initial est retrouvé.

Piège : Reste négatif apparent et coefficient non inversible

Pour déchiffrer F, de rang \(y=5\), on obtient \(21(5-7)=-42\). Il faut prendre \(-42=26(-2)+10\) : le rang \(10\) correspond à K.

Remplacer \(5\) par \(2\) dans la règle de chiffrement détruirait l’unicité : les rangs \(0\) et \(13\) donneraient tous deux le reste \(7\), donc la lettre H. Le nombre \(2\) n’a pas d’inverse modulo \(26\), car \(2c=1+26k\) opposerait un nombre pair à un impair.

Vocabulaire : Lire un programme entier

Les arguments ci-dessous sont des entiers. Pour \(b>0\), Python donne le quotient euclidien avec a // b et le reste avec a % b. Ainsi \(-47=6(-8)+1\) donne -47 // 6 = -8 et -47 % 6 = 1 : le quotient est arrondi vers le bas, pas vers zéro.

Dans un programme, = est une affectation : on calcule le membre droit avec l’ancienne valeur, puis on remplace la valeur à gauche. == teste une égalité ; ** calcule une puissance ; l’indentation délimite les blocs d’instructions. Une congruence est une relation ; % est une opération qui calcule un reste.

Méthode : Distinguer tests et preuve

Préciser les entrées autorisées, suivre les états dans l’ordre des instructions, puis établir un invariant : une affirmation vraie au départ et après chaque passage complet. Justifier aussi la terminaison et relier le test d’arrêt au résultat attendu. Quelques tests numériques réussis ne remplacent pas cette preuve.

Algorithme : Division par soustractions successives

Entrées : \(a\geqslant0\) et \(b\geqslant1\), entiers. Sortie : quotient \(q\) et reste \(r\). \(q\) compte les groupes de \(b\) retirés ; \(r\) est ce qui reste à répartir.

def division_soustractions(a, b):
    if a < 0 or b <= 0:
        raise ValueError("il faut a >= 0 et b > 0")
    q, r = 0, a
    while r >= b:
        q = q + 1
        r = r - b
    return q, r

Exemple : Trace de la division de \(29\) par \(6\)

Le test \(5\geqslant6\) est faux : la fonction renvoie \((4,5)\). Une soustraction supplémentaire produirait \((5,-1)\), qui n’est pas une division euclidienne. Cette version refuse les dividendes négatifs, contrairement aux opérations // et % avec un diviseur positif. Elle peut être lente si le quotient est grand.

Algorithme : Puissance modulaire par multiplications successives

Entrées : \(a\in\mathbb{Z}\), \(e\in\mathbb{N}\) et \(m\geqslant1\) entiers. Le programme prend le reste après chaque produit ; il ne construit pas d’abord l’entier \(a^e\) tout entier.

def puissance_modulaire(a, exposant, module):
    if exposant < 0 or module < 1:
        raise ValueError("exposant >= 0 et module >= 1 requis")
    produit = 1 % module
    base = a % module
    for _ in range(exposant):
        produit = (produit * base) % module
    return produit

Exemple : Trace pour \(5^4\) modulo \(17\)

Les valeurs successives de produit sont

Contrôle. \(5^4=625=17\times36+13\). Avec un exposant nul et un module \(17\), aucun passage n’est exécuté et le résultat est \(1\) ; avec un module \(1\), il est \(0\).

À retenir : Les relations fondamentales et leurs conditions

• \(d\mid a\Longleftrightarrow a=dk\) pour un \(k\in\mathbb{Z}\). Le critère \(a/d\in\mathbb{Z}\) exige \(d\ne0\).

• \(d\mid a\) et \(d\mid b\) entraînent \(d\mid ua+vb\) pour \(u,v\in\mathbb{Z}\).

• Si \(a\in\mathbb{Z}\) et \(b\geqslant1\) entier, il existe un unique couple \((q,r)\in\mathbb{Z}^2\) tel que \(a=bq+r\) et \(0\leqslant r<b\).

• Pour \(n\geqslant2\), \(a\equiv b\pmod n\Longleftrightarrow n\mid(a-b)\) \(\Longleftrightarrow\) les deux restes euclidiens sont égaux.

• On peut additionner, soustraire, multiplier et élever à une puissance naturelle positive des congruences de même module. Pas de division arbitraire ni d’extraction de racine.

• \(ca\equiv cb\pmod{cm}\Longleftrightarrow a\equiv b\pmod m\) pour \(c\geqslant1\), \(m\geqslant2\). Si \(ac\equiv1\pmod m\), alors \(ax\equiv b\pmod m\Longleftrightarrow x\equiv cb\pmod m\).

• \(x\equiv r\pmod m\) décrit tous les entiers \(x=r+mk\), \(k\in\mathbb{Z}\). Le reste est le représentant vérifiant \(0\leqslant r<m\).