Raisonner sur les entiers : divisibilité, division euclidienne et congruences ; calculer un PGCD avec l'algorithme d'Euclide ; démontrer et utiliser les théorèmes de Bézout et de Gauss ; résoudre une congruence et une équation en nombres entiers ; étudier les nombres premiers (décomposition, petit théorème de Fermat) et des problèmes de chiffrement. Programme de Maths expertes.
Prérequis
Calcul sur les entiers relatifs, puissances, raisonnement par récurrence.
IDivisibilité dans
DéfinitionDiviseur, multiple
Soient et deux entiers relatifs. On dit que divise s'il existe un entier relatif tel que .
On note ; on dit aussi que est un diviseur de , ou que est un multiple de .
Exemple
car .
est un multiple de tout entier (), mais ne divise que .
Les diviseurs de dans sont ,,,, et .
PropriétéRègles de calcul
Soient ,, des entiers relatifs.
Si et , alors (transitivité).
Si et , alors divise toute combinaison avec ; en particulier et .
Si et , alors : un entier non nul n'a qu'un nombre fini de diviseurs.
DémonstrationPoint 2
Si et avec , alors , où est un entier : donc .
ExempleÉliminer par une combinaison
Cherchons les entiers naturels tels que divise .
Si , comme , alors divise la différence .
Réciproquement, si , alors .
Donc . Comme , on a , soit .
MéthodeDéterminer les diviseurs d'un entier
Tester les entiers de à .
Chaque diviseur trouvé en donne un second, : les diviseurs vont par paires.
Dans , ajouter les opposés.
ExempleDiviseurs de
: on teste les entiers de à . Les paires ,,,, et donnent les diviseurs positifs de :.
AttentionLes diviseurs négatifs
Dans , un diviseur peut être négatif : pour trouver les entiers tels que , il faut envisager .
IIDivision euclidienne
ThéorèmeDivision euclidienne
Soient et . Il existe un unique couple d'entiers tel que
est le quotient et le reste de la division euclidienne de par .
Exemple
: quotient , reste .
: quotient , reste . Sur la droite des entiers, est situé unités après le multiple .
AttentionLe reste n'est jamais négatif
n'est pas l'écriture euclidienne : le reste doit vérifier .
PropriétéConséquences
si et seulement si le reste de la division euclidienne de par est nul.
Les restes possibles dans la division par sont : tout entier s'écrit ,, …, ou . C'est la base des raisonnements par disjonction des cas.
DémonstrationUnicité (pour aller plus loin)
Si avec et , alors . Or , et le seul multiple de strictement compris entre et est . Donc , puis .
En Python, pour ,a // b et a % b donnent le quotient et le reste euclidiens, y compris pour négatif :
Python
a, b = -17, 4
q, r = a // b, a % b
print(q, r) # -5 3
IIICongruences dans
DéfinitionCongruence modulo
Soit un entier naturel, . Deux entiers et sont congrus modulo lorsque divise . On note
PropriétéCongruence et reste
si et seulement si et ont le même reste dans la division euclidienne par .
Tout entier est congru modulo à son reste , avec .
signifie que divise .
Exemple
car .
: et ont le même reste .
ThéorèmeCompatibilité avec les opérations
Soient et des entiers tels que et . Alors :
et ;
;
pour tout entier naturel .
DémonstrationProduit et puissances
L'égalité montre que est une combinaison de et , tous deux multiples de : donc . Pour les puissances, la règle du produit donne, par récurrence sur :.
AttentionOn ne divise pas une congruence
, mais . Simplifier par un facteur n'est permis que sous condition (théorème de Gauss, partie V).
Reste d'une grande puissance
MéthodeRestes de modulo
Remplacer par un entier plus simple qui lui est congru (son reste, ou un entier négatif comme ).
Calculer les restes de jusqu'à obtenir le reste : si , les restes se répètent avec la période .
Diviser l'exposant par : si , alors .
ExempleReste de dans la division par
Restes successifs : ,,,, et . Comme :
Le reste de la division euclidienne de par est (en Python : pow(3, 100, 7) renvoie 4).
Raisonner par disjonction des cas
ExempleLes carrés modulo
Tout entier est congru à ,, ou modulo :
Reste de modulo
Reste de modulo
Un carré est donc congru à ou à modulo , et une somme de deux carrés à , ou , jamais à . Par exemple, n'est pas une somme de deux carrés.
Critères de divisibilité
PropriétéDivisibilité par et par
Soit un entier naturel de chiffres .
: est divisible par si et seulement si la somme de ses chiffres l'est (de même pour ).
: est divisible par si et seulement si la somme alternée de ses chiffres, à partir des unités, l'est.
Démonstration
, donc pour tout entier naturel ; en remplaçant chaque puissance de dans , on obtient . De même, donne .
Exemple
est divisible par , donc aussi : .
est divisible par , donc aussi : .
IVPGCD et algorithme d'Euclide
DéfinitionPGCD
Soient et deux entiers relatifs non tous deux nuls. Leurs diviseurs communs sont en nombre fini ; le plus grand d'entre eux est le plus grand commun diviseur de et , noté . C'est un entier naturel non nul.
Propriété
.
Si , ; si et ,.
PropriétéPropriété clé
Soient ,,, des entiers avec et . Les diviseurs communs de et sont exactement les diviseurs communs de et . En particulier, .
Démonstration
Si et , alors divise la combinaison . Réciproquement, si et , alors . Les deux couples ont les mêmes diviseurs communs, donc le même plus grand.
ThéorèmeAlgorithme d'Euclide
Soient et deux entiers naturels avec . On effectue les divisions euclidiennes successives
et ainsi de suite. Les restes forment une suite strictement décroissante d'entiers naturels : un reste nul apparaît après un nombre fini d'étapes. Le dernier reste non nul est (si , le PGCD est ).
RemarquePourquoi ça marche
D'après la propriété clé, , où est le dernier reste non nul.
ExempleCalcul de
Division euclidienne
Reste
Le dernier reste non nul est :.
Lecture géométrique : on découpe le rectangle de côtés et en carrés aussi grands que possible, à chaque étape. Le côté des derniers carrés, , est le PGCD : c'est le plus grand côté de carré qui pave exactement le rectangle.
PropriétéDiviseurs communs
Les diviseurs communs de et sont exactement les diviseurs de : on l'obtient en suivant l'algorithme d'Euclide jusqu'au couple .
Exemple
Les diviseurs communs positifs de et sont les diviseurs de :.
Pour et entiers naturels, (pgcd(252, 198) renvoie 18) :
Python
def pgcd(a, b):
while b != 0:
a, b = b, a % b
return a
VThéorèmes de Bézout et de Gauss
DéfinitionEntiers premiers entre eux
Deux entiers et , non tous deux nuls, sont premiers entre eux lorsque : leurs seuls diviseurs communs sont et .
Exemple
et sont premiers entre eux, sans être des nombres premiers ; et ne le sont pas ().
Deux entiers consécutifs et sont toujours premiers entre eux : un diviseur commun divise .
ThéorèmeIdentité de Bézout
Soient et deux entiers non tous deux nuls et . Il existe des entiers relatifs et tels que
DémonstrationÉcriture du PGCD sous la forme (au programme)
Soit l'ensemble des entiers strictement positifs de la forme , avec . n'est pas vide : il contient . Toute partie non vide de admet un plus petit élément : notons le plus petit élément de .
divise . Écrivons la division euclidienne , avec . Alors est de la forme . Si était strictement positif, il appartiendrait à tout en étant strictement inférieur à : impossible. Donc et . De même, .
. est un diviseur commun positif de et , donc . Inversement, divise et , donc la combinaison ; comme , on a .
Ainsi .
ThéorèmeThéorème de Bézout
Deux entiers et sont premiers entre eux si et seulement s'il existe des entiers et tels que .
Démonstration
Si , l'identité de Bézout fournit et . Réciproquement, si , tout diviseur commun positif de et divise : il vaut .
MéthodeTrouver un couple de Bézout (algorithme d'Euclide étendu)
Écrire l'algorithme d'Euclide.
Partir de l'avant-dernière division et isoler le dernier reste non nul.
Remonter les divisions en remplaçant chaque reste par son expression, jusqu'à n'avoir plus que et .
ExempleUn couple de Bézout pour et
D'après les divisions du IV : , et . Donc
Le couple convient : .
Version itérative de l'algorithme (pour et entiers naturels, ) : à chaque étape, et ;bezout(252, 198) renvoie (18, 4, -5).
Soient ,, des entiers. Si divise et si et sont premiers entre eux, alors divise .
Démonstration(au programme)
Comme , le théorème de Bézout donne des entiers et tels que . En multipliant par :
divise ; divise , donc . Ainsi divise la somme .
PropriétéCorollaire
Si et sont premiers entre eux et divisent tous les deux , alors divise .
Démonstration
avec . Comme et , le théorème de Gauss donne :, d'où .
ExempleProduit de trois entiers consécutifs
Pour tout entier , est divisible par . En effet, parmi deux entiers consécutifs l'un est pair, donc ; les restes de , et modulo sont , et dans un certain ordre, donc l'un des trois est multiple de et . Comme et sont premiers entre eux, .
AttentionL'hypothèse « premiers entre eux » est indispensable
divise , mais ne divise ni ni : ici .
VICongruences linéaires et équations diophantiennes
PropriétéInverse modulo
Soient et un entier. Il existe un entier tel que si et seulement si et sont premiers entre eux. Un tel est un inverse de modulo .
Démonstration
équivaut à l'existence d'un entier tel que : c'est exactement le théorème de Bézout appliqué à et .
ExempleInverse de modulo
donne , soit . Comme , est un inverse de modulo : vérification, .
MéthodeRésoudre
Calculer .
Si ne divise pas :aucune solution (car serait divisible par ).
Si : multiplier les deux membres par un inverse de modulo ;.
Si et : diviser ,et par (car ), puis appliquer le point 3. On obtient solutions modulo .
ExempleTrois cas
: ; en multipliant par ,. Les solutions sont les entiers ,.
: divise ; on se ramène à , puis, étant un inverse de modulo , à . Modulo : ou .
: ne divise pas : aucune solution.
PropriétéÉquation
Soient et deux entiers non nuls et . L'équation admet des solutions entières si et seulement si divise .
Démonstration
Si , divise et , donc . Réciproquement, si , l'identité de Bézout multipliée par donne la solution .
MéthodeRésoudre dans
Vérifier que divise , puis diviser l'équation par : on se ramène au cas .
Trouver une solution particulière (couple de Bézout, ou essai).
Soustraire : . Le théorème de Gauss donne , d'où puis , avec .
Vérifier (réciproque) que ces couples sont bien solutions.
ExempleRésoudre
et : est une solution particulière.
Si , alors . divise et est premier avec , donc (Gauss) : . En reportant, , soit .
Réciproquement, .
Les solutions sont les couples avec .
Attention
Ne pas oublier la réciproque, ni de diviser , et par le PGCD avant d'appliquer Gauss : dans , on travaille sur .
VIINombres premiers
DéfinitionNombre premier
Un nombre premier est un entier naturel dont les seuls diviseurs positifs sont et . Un entier non premier est dit composé. L'entier n'est pas premier.
Propriété
Tout entier admet au moins un diviseur premier : son plus petit diviseur .
Si est composé, il admet un diviseur premier tel que .
Si est premier et ne divise pas , alors et sont premiers entre eux.
Démonstration
Si le plus petit diviseur de était composé, il aurait un diviseur avec , qui diviserait aussi : contradiction.
Si avec , alors , donc , et un diviseur premier de convient.
Les diviseurs positifs de sont et ; ne divise pas , donc le seul diviseur commun positif est .
MéthodeÉtudier la primalité d'un entier
Chercher un diviseur parmi les nombres premiers . S'il n'y en a aucun, est premier.
Exemple
. Aucun des nombres premiers ,,,,, ne divise (restes ,,,,,) : est premier.
ThéorèmeL'ensemble des nombres premiers est infini
Il existe une infinité de nombres premiers.
Démonstration(au programme)
Raisonnons par l'absurde : supposons qu'il n'existe qu'un nombre fini de nombres premiers . Posons
admet un diviseur premier , qui est l'un des . Alors divise et le produit , donc leur différence : impossible. Il existe donc une infinité de nombres premiers.
Remarque
n'est pas forcément premier : . Mais ses diviseurs premiers ne sont pas dans la liste de départ.
Crible d'Ératosthène
Pour obtenir les nombres premiers jusqu'à : on écrit les entiers de à ; le premier entier non barré est premier, on barre tous ses multiples à partir de son carré ; on recommence tant que le carré du nombre retenu est inférieur ou égal à . Jusqu'à , il suffit de barrer les multiples de ,, et (car ) : il reste les nombres premiers inférieurs à .
Python
def crible(n):
est_p = [True] * (n + 1)
est_p[0] = est_p[1] = False
p = 2while p * p <= n:
if est_p[p]:
k = p * p
while k <= n:
est_p[k] = False
k += p
p += 1return [k for k inrange(n+1)
if est_p[k]]
Décomposition en produit de facteurs premiers
PropriétéUn premier qui divise un produit
Si un nombre premier divise un produit , alors divise ou divise .
Démonstration
Si ne divise pas , alors et sont premiers entre eux ; comme , le théorème de Gauss donne .
ThéorèmeDécomposition en facteurs premiers
Tout entier s'écrit comme produit de nombres premiers :
où sont premiers et les exposants des entiers naturels non nuls. Cette écriture est unique.
DémonstrationIdée
Existence, par récurrence forte : si est premier, c'est fini ; sinon avec , et on décompose et .Unicité : si deux décompositions de existaient, un premier de la première divise le produit de la seconde, donc l'un de ses facteurs (propriété précédente) ; on simplifie par ce premier et on recommence.
Exemple
On divise successivement par les plus petits nombres premiers possibles : .
PropriétéDiviseurs d'un entier décomposé
Les diviseurs positifs de sont les entiers avec . Leur nombre est .
Exemple
a diviseurs positifs. Avec , on lit (plus petits exposants communs).
RemarquePour aller plus loin : le PPCM
Le plus petit multiple commun strictement positif de et s'obtient avec les plus grands exposants : . Pour , on a : ici .
Pour ,facteurs(360) renvoie [2, 2, 2, 3, 3, 5] :
Python
def facteurs(n):
res, d = [], 2while d * d <= n:
while n % d == 0:
res.append(d)
n //= d
d += 1if n > 1:
res.append(n)
return res
VIIIPetit théorème de Fermat
ThéorèmePetit théorème de Fermat
Soit un nombre premier.
Si est un entier non divisible par , alors .
Pour tout entier ,.
DémonstrationPour aller plus loin
Soit non divisible par . Les entiers ne sont pas divisibles par (propriété du VII), et ils ont des restes deux à deux distincts modulo : si , alors , donc (Gauss), avec , d'où . Leurs restes sont donc dans un certain ordre. En multipliant :
divise et est premier avec , donc . Enfin, s'obtient en multipliant par (et est évident si ).
ExempleReste de dans la division par
est premier et ne divise pas :. Comme ,.
AttentionLa réciproque est fausse
alors que n'est pas premier. En revanche, si pour un entier premier avec , alors est sûrement composé : c'est le principe des tests de primalité.
IXApplication : chiffrement
ExempleChiffrement affine
On numérote les lettres de à et on chiffre la lettre par le reste de modulo . Par exemple, () donne : devient .
Pour déchiffrer, on résout . Comme , est un inverse de modulo , d'où . Pour :, on retrouve .
Remarque
Le déchiffrement n'est possible que si le coefficient ( ici) est premier avec . Le système RSA repose de même sur des calculs de puissances modulo et sur le petit théorème de Fermat.
À retenir
; division euclidienne avec .
: compatible avec , et les puissances, mais on ne divise pas.
Le dernier reste non nul de l'algorithme d'Euclide est le PGCD ; en remontant les divisions, on obtient .
Bézout : . Gauss : et .
Infinité des nombres premiers, décomposition unique, Fermat : si .
OptiTAB utilise des cookies essentiels pour le fonctionnement du site et des cookies de statistiques et marketing/publicité pour mesurer l’audience et personnaliser nos campagnes. Vous pouvez accepter, refuser ou personnaliser votre choix. En savoir plus.