Savoir si un nombre en divise un autre, trouver un reste, calculer « à un multiple de près » : ces outils contrôlent une clé de RIB ou un code ISBN et servent à chiffrer des messages. À la fin du chapitre, tu sauras trouver les diviseurs d'un entier, poser une division euclidienne dans , calculer avec des congruences, établir un test de divisibilité et résoudre une congruence .
Divisibilité dans
Définition
Soient et deux entiers relatifs. On dit que divise , ou que est un multiple de , s'il existe un entier tel que . On note .
- , car ;
- tout entier divise , mais ne divise que ;
- si , alors : dans , les diviseurs vont par paires opposées.
Exemple résolu : les diviseurs de
On teste de à ; chaque diviseur en donne un second, :
et ne divise pas . Les diviseurs positifs de sont ; dans , ajoute leurs opposés : a diviseurs.
Propriétés
- Transitivité : si et , alors .
- Combinaison linéaire : si et , alors pour tous entiers et .
Preuve : et , donc , avec entier.
Exemple résolu : une condition de divisibilité
Cherche les entiers naturels tels que divise .
- divise et , donc leur différence : .
- Les diviseurs positifs de sont et ; comme , , soit .
- Réciproque : pour , divise . La seule solution est .
Division euclidienne
Théorème
Soient et . Il existe un unique couple d'entiers tel que
est le quotient, le reste. La condition rend le couple unique : n'est pas la division euclidienne de par . Ainsi si et seulement si , et les restes possibles vont de à .
Exemple résolu : un dividende négatif
Division euclidienne de par .
- , donc .
- Le reste est négatif : on ajoute au reste et on retire au quotient, d'où .
- Comme , le quotient est et le reste .
Congruences
Définition
Soit un entier naturel, . Deux entiers et sont congrus modulo si divise . On note .
Cela revient à dire que et ont le même reste dans la division euclidienne par . En particulier, si avec , alors est le reste de .
- , car ;
- signifie exactement ;
- les congruences s'enchaînent : si et modulo , alors .
Exemple résolu : le reste d'un entier négatif
avec , donc : le reste de par est . On a aussi , mais n'est pas un reste.
Compatibilité avec les opérations
Si et , alors :
- et ;
- ;
- pour tout entier naturel .
Preuve du produit : , somme de deux multiples de . Les puissances s'en déduisent par récurrence.
Attention, on ne divise pas : , alors que .
Exemple résolu : le reste d'une grande puissance
Reste de dans la division par .
- , et .
- On divise l'exposant par : .
- : le reste est .
Exemple résolu : un tableau de restes
Montre que n'est jamais divisible par . On étudie les trois restes possibles de modulo :
Aucune colonne ne donne : n'est jamais divisible par .
Tests de divisibilité
En base dix, , où est le chiffre des unités. On réduit chaque puissance de .
- Par et : , donc et ; de même modulo , car .
- Par : , donc et .
- Par et : est multiple de et de , donc . Par : , seuls les deux derniers chiffres comptent.
Exemple résolu : appliquer les tests
Étudie la divisibilité de par , et .
- , donc modulo comme modulo : n'est divisible ni par ni par .
- Depuis les unités : , donc : divise . Vérification : .
Inverse et équation modulo
Inverse modulo
Un entier est un inverse de modulo si .
Exemple résolu
un inverse de modulo . On teste de à : vaut successivement , , , et . Donc est un inverse de modulo .
Un inverse n'existe pas toujours : si , alors pour un entier , donc tout diviseur commun à et divise . Ainsi n'a pas d'inverse modulo : divise et , mais pas . Réciproquement, on admet ici que si et sont premiers entre eux (leur seul diviseur positif commun est ), alors a un inverse modulo ; la preuve viendra avec le théorème de Bézout.
Résoudre
Si est un inverse de modulo , alors
(on multiplie par dans un sens, par dans l'autre).
Exemple résolu
résous .
- Un inverse de modulo est .
- .
- Vérification : . Les solutions sont les entiers , .
Sans inverse, on teste les restes possibles. Pour :
Les solutions vérifient ou : diviser par aurait fait perdre . Et n'a aucune solution : manque dans la ligne.
Les pièges
- Un reste négatif ou trop grand : vérifie toujours .
- Les diviseurs négatifs oubliés quand on cherche les diviseurs dans .
- La réciproque oubliée : une condition nécessaire, comme , se vérifie sur chaque candidat.
- Une congruence divisée : n'équivaut pas à . Multiplie par un inverse s'il existe, sinon teste tous les restes.
- L'exposant réduit modulo : ne donne pas ( mais ). Comme , l'exposant se réduit modulo .
Ce qu'il faut retenir
- s'il existe tel que ; un diviseur commun à et divise .
- Division euclidienne : avec , couple unique.
- : , c'est-à-dire même reste dans la division par .
- Les congruences s'additionnent, se multiplient et s'élèvent à une même puissance ; elles ne se divisent pas.
- Grande puissance : trouve , puis divise l'exposant par .
- Modulo (et ) : somme des chiffres ; modulo : somme alternée depuis les unités.
- inverse de modulo : ; alors .
À l'épreuve
Consignes possibles en devoir :
- « Montre que, pour tout entier naturel , divise » : pars de et , cite la compatibilité utilisée, conclus.
- « Résous » : une rédaction complète donne l'inverse vérifié, puis toutes les solutions , .
- « Démontre le critère de divisibilité par » : réduis chaque puissance de .
Les erreurs à éviter : un reste négatif, une congruence divisée, une réciproque oubliée, une puissance réduite sans calcul posé.