Chargement du chapitre…
36 exercices de difficulté croissante, à chercher avant de regarder le corrigé.
36 exercices, difficulté croissante de ★ (application directe) à ★★★★ (défi). Les corrigés détaillés sont dans le PDF — cherchez d'abord, le corrigé ensuite : c'est là que ça progresse.
Divisibilité dans Z : diviseurs, multiples, combinaisons linéaires
Déterminer tous les diviseurs de dans . Combien y en a-t-il ?
Soient des entiers relatifs. Démontrer les deux propriétés suivantes.
a. Si et , alors pour tous entiers .
b. Si et , alors ou .
Déterminer tous les entiers relatifs tels que divise . On commencera par écrire sous la forme .
Déterminer tous les entiers naturels tels que divise . On cherchera une combinaison linéaire de et de dans laquelle disparaît.
Vrai ou faux : pour tous entiers , si , alors ou .
Division euclidienne dans Z, raisonner selon le reste
Dans tout l'exercice, la division euclidienne de par est l'écriture avec et .
Effectuer la division euclidienne :
a. de par ;
b. de par ;
c. de par ;
d. de par ;
e. de par .
Soit un entier naturel. On divise par .
a. Vérifier que . Pour quelles valeurs de cette égalité est-elle la division euclidienne de par ?
b. Effectuer la division euclidienne pour les valeurs de restantes.
Soit . On divise par .
a. Vérifier que . Pour quelles valeurs de cette égalité est-elle la division euclidienne ?
b. Pour , en déduire le quotient et le reste de la division euclidienne de par .
Un entier a pour reste dans la division euclidienne par .
a. Quel est son reste dans la division par ? dans la division par ?
b. Réciproquement, si l'on sait seulement que le reste de dans la division par vaut , quels sont les restes possibles de dans la division par ?
Démontrer l'unicité dans le théorème de la division euclidienne : si avec , et , alors et .
Division euclidienne dans Z, raisonner selon le resteDivisibilité dans Z : diviseurs, multiples, combinaisons linéaires
Dans tout l'exercice, on n'utilise pas les congruences : on raisonne en écrivant la division euclidienne de , sous la forme , et en distinguant les cas selon la valeur du reste . Les entiers sont des entiers relatifs quelconques.
Montrer que est divisible par , puis par , puis par .
Montrer que si est impair, alors divise .
a. Montrer que le carré d'un entier est de la forme ou , avec .
b. En déduire qu'aucun entier de la forme n'est la somme de deux carrés d'entiers.
c. La réciproque est-elle vraie : un entier qui n'est pas de la forme est-il toujours somme de deux carrés ?
Montrer que divise , de deux façons : par une disjonction de cas selon le reste de dans la division par , puis en se ramenant à la question 1.
Pour quels entiers l'entier est-il divisible par ?
PGCD et algorithme d'Euclide
Calculer par l'algorithme d'Euclide, en écrivant une division euclidienne par ligne et en comptant les divisions effectuées :
a. ;
b. ;
c. .
La figure du cours qui illustre l'algorithme d'Euclide pave un rectangle de sur par des carrés : on y retire d'abord le plus grand carré possible, autant de fois qu'il tient, puis on recommence dans le rectangle restant.
a. Décrire le pavage du rectangle de sur obtenu par le même procédé : combien de carrés de chaque taille ? Contrôler le résultat par un calcul d'aires.
b. Expliquer, sur la figure puis par le calcul, pourquoi le côté du dernier carré divise les deux côtés du rectangle de départ.
a. Soient et . Montrer que .
b. En déduire pour tout .
PGCD et algorithme d'EuclideDivisibilité dans Z : diviseurs, multiples, combinaisons linéaires
Dans tout l'exercice, désigne un entier naturel.
Montrer que .
Montrer que .
a. Montrer que vaut ou .
b. Montrer que si et seulement si est de la forme avec .
Montrer que vaut si est pair et si est impair.
Calculer en fonction de .
Relation de Bézout, théorème de Bézout, entiers premiers entre euxPGCD et algorithme d'Euclide
Pour chacun des couples suivants, calculer par l'algorithme d'Euclide, puis trouver des entiers et tels que , de deux façons : en remontant l'algorithme ligne par ligne, puis à l'aide du tableau des coefficients de l'algorithme d'Euclide étendu. Vérifier le résultat.
a. ;
b. ;
c. .
Déterminer tous les couples tels que .
On constate que .
a. Expliquer pourquoi cette égalité, à elle seule, ne prouve pas que . On donnera une égalité du même type qui conduirait, par le même raisonnement, à une conclusion fausse.
b. Expliquer pourquoi, dans ce cas précis, on peut tout de même conclure que .
Relation de Bézout, théorème de Bézout, entiers premiers entre eux
Dans tout l'exercice, chaque démonstration doit exhiber une combinaison linéaire à coefficients entiers égale à (ou au PGCD), avec ses coefficients écrits explicitement, puis citer le théorème de Bézout.
Montrer que, pour tout , .
Soit . Montrer que est un entier, puis que . On pourra calculer .
Soient deux entiers premiers entre eux. Montrer que . On établira d'abord et par des combinaisons explicites, puis on multipliera les deux relations obtenues.
Soient deux entiers premiers entre eux, et deux entiers. Montrer que . On pourra élever une relation à la puissance par la formule du binôme.
Soient deux entiers tels que . On écrit et , avec .
a. Montrer que .
b. Application : déterminer tous les couples d'entiers naturels tels que et .
Rédaction : citer Gauss, Bézout et le lemme d'Euclide avec leurs hypothèsesRelation de Bézout, théorème de Bézout, entiers premiers entre euxPGCD et algorithme d'Euclide
Les quatre textes ci-dessous sont des réponses rédigées, telles qu'on les lit sur une copie. Chacune est fausse ou incomplète. Pour chacune, répondre aux quatre questions suivantes.
(a) Question posée : calculer et en donner une relation de Bézout.
(b) Affirmation : pour tous entiers et , .
(c) Affirmation : pour tous entiers , si et , alors .
(d) Affirmation : pour tout , vaut ou .
Pour cette dernière copie, déterminer de plus la valeur exacte de en fonction de .
PGCD et algorithme d'EuclideRelation de Bézout, théorème de Bézout, entiers premiers entre eux
On rappelle la caractérisation du PGCD : pour tous entiers et , les diviseurs communs à et sont exactement les diviseurs de .
a. Soient . Démontrer l'homogénéité du PGCD : . On n'utilisera que la caractérisation rappelée ci-dessus.
b. Application : pour , déterminer sans aucun calcul de division.
Soient , avec . On pose
a. Montrer que possède un plus petit élément, noté , et que pour certains entiers .
b. En effectuant la division euclidienne de par , montrer que divise . Montrer de même que divise .
c. Montrer que . En déduire la relation de Bézout, sans utiliser l'algorithme d'Euclide.
d. Montrer que l'ensemble de toutes les combinaisons de et est exactement l'ensemble des multiples de .
e. Comparer cette démonstration avec celle du cours, qui remonte l'algorithme d'Euclide : que fournit chacune d'elles ?
Soient trois entiers non tous nuls. On appelle PGCD de , , , et l'on note , le plus grand entier strictement positif qui divise à la fois , et . On dit que , , sont premiers entre eux dans leur ensemble lorsque .
a. Montrer que les diviseurs communs à , , sont exactement les diviseurs de , et en déduire que . Montrer qu'il existe des entiers tels que .
b. Montrer que , et sont premiers entre eux dans leur ensemble, mais qu'aucun des trois couples qu'on peut former avec eux n'est formé d'entiers premiers entre eux.
c. Trouver des entiers tels que , d'abord par la méthode de la question 3.a, puis en cherchant une solution plus simple.
Théorème de Gauss et ses corollaires
Dans tout l'exercice, , , , désignent des entiers relatifs. Chaque fois que le théorème de Gauss ou son corollaire est utilisé, on vérifiera son hypothèse dans la phrase même qui le cite.
Montrer que si divise , alors divise .
Déterminer tous les couples tels que .
Montrer que si et , alors .
Un étudiant affirme : « si et , alors ».
a. Montrer par un contre-exemple que cette affirmation est fausse.
b. Quelle hypothèse du corollaire du théorème de Gauss n'est pas satisfaite ?
c. Par quel entier peut-on affirmer que est divisible lorsque et ? Le démontrer.
On suppose et . Que donne le théorème de Gauss lorsque ? Retrouver ce résultat sans le théorème de Gauss. Que donne-t-il lorsque ?
Théorème de Gauss et ses corollairesRédaction : citer Gauss, Bézout et le lemme d'Euclide avec leurs hypothèses
Dans tout l'exercice, est un polynôme de degré à coefficients entiers, avec et . On dit qu'un rationnel est écrit sous forme irréductible lorsque , et . Le chapitre « Polynômes et fractions rationnelles » a utilisé, en l'admettant, la règle démontrée à la question 1.
On suppose que le rationnel , écrit sous forme irréductible, est racine de .
a. Montrer que
b. En déduire que divise , puis que divise . On nommera le théorème utilisé et l'on justifiera son hypothèse.
c. Montrer de même que divise .
On considère .
a. Dresser la liste des racines rationnelles possibles de .
b. Montrer que pour tout réel , et en déduire les seuls candidats qu'il reste à essayer.
c. Déterminer les racines rationnelles de , puis écrire comme produit de trois polynômes de degré à coefficients entiers.
Montrer que n'a aucune racine rationnelle. Montrer qu'il a pourtant une racine réelle dans l'intervalle . Que peut-on dire de ce réel ?
a. Montrer que est irrationnel.
b. On pose . Montrer que , puis que est irrationnel.
PPCM et lien avec le PGCDPGCD et algorithme d'Euclide
Dans tout l'exercice, et désignent des entiers naturels non nuls, et l'on note . On rappelle le résultat du cours : il existe des entiers naturels et tels que , et .
Démontrer que . On montrera que est un multiple commun de et , puis que tout multiple commun de et est un multiple de .
Déterminer tous les couples tels que et .
Déterminer tous les couples tels que et .
Déterminer tous les couples tels que .
PPCM et lien avec le PGCDThéorème de Gauss et ses corollaires
Deux phares clignotent, le premier toutes les secondes, le second toutes les secondes. À minuit pile, ils clignotent ensemble. À quelle heure clignoteront-ils de nouveau ensemble pour la première fois ? À quels instants clignotent-ils ensemble ?
Trois roues dentées , , , de , et dents, sont engrenées en chaîne : entraîne , qui entraîne . On marque d'un trait la position de départ de chaque roue. Combien de dents doivent passer au point de contact pour que les trois roues retrouvent ensemble leur position de départ, au plus tôt ? Combien de tours chaque roue a-t-elle alors effectués ?
Soient et deux entiers non nuls. Démontrer que les multiples communs de et sont exactement les multiples de . On effectuera la division euclidienne d'un multiple commun par .
Soient tels que . Démontrer, à l'aide du corollaire du théorème de Gauss, que . Donner un exemple de deux entiers naturels non nuls tels que .
Nombres premiers : crible, infinité, lemme d'Euclide
On utilisera librement le critère de primalité du cours : si un entier n'a aucun diviseur premier tel que , alors est premier. La question 5 en demande la démonstration.
Pour chacun des entiers suivants, dire s'il est premier. On précisera les nombres premiers par lesquels il suffit d'essayer de diviser, et l'on justifiera leur nombre.
a.
b.
c.
d.
e.
Le crible d'Ératosthène jusqu'à (figure du cours) consiste à écrire les entiers de à , puis à rayer les multiples de autres que , ceux de autres que , ceux de autres que et ceux de autres que . Expliquer pourquoi les entiers restants sont exactement les nombres premiers inférieurs ou égaux à , et pourquoi il est inutile de rayer les multiples de . Expliquer aussi pourquoi, pour rayer les multiples de , on peut commencer à .
On pose pour .
a. Calculer pour , et vérifier par le critère de primalité que , et sont premiers. (Les dix valeurs sont premières.)
b. Montrer que n'est pas premier, sans calculatrice. Faire de même pour .
Montrer que pour tout entier , l'entier n'est pas premier. On établira l'identité . Que se passe-t-il pour ?
Démontrer que tout entier qui n'est pas premier possède un diviseur premier tel que , et en déduire le critère de primalité.
Nombres premiers : crible, infinité, lemme d'Euclide
On rappelle que désigne l'ensemble des nombres premiers et que tout entier possède au moins un diviseur premier.
a. Rédiger la démonstration d'Euclide de l'infinitude de : on suppose que est fini, , et l'on considère .
b. On note le produit des plus petits nombres premiers, augmenté de . Calculer , et vérifier que . Cela contredit-il la démonstration de la question a ? Qu'est-ce que cette démonstration affirme exactement à propos de ?
Une variante sans raisonnement par l'absurde. Soit . Montrer que tout diviseur premier de est strictement supérieur à . En déduire que est infini.
Les trous entre nombres premiers.
a. Soit . Montrer que les entiers consécutifs ne sont pas premiers.
b. En déduire que pour tout entier , il existe entiers consécutifs dont aucun n'est premier.
c. Donner, par cette méthode, cinq entiers consécutifs dont aucun n'est premier. En trouver cinq plus petits à l'aide de la liste des nombres premiers inférieurs à .
Les nombres de la forme .
a. Vérifier que pour tout réel et tout entier , .
b. Soit . Montrer que si est premier, alors est premier.
c. La réciproque est-elle vraie ? On pourra examiner .
Décomposition en facteurs premiers, valuations, diviseurs
Pour un entier , on note le nombre de ses diviseurs positifs et leur somme. On rappelle les formules du cours : si , où sont des nombres premiers distincts et , alors
et
Décomposer en produit de facteurs premiers les entiers suivants. Pour , on justifiera que le facteur obtenu est premier.
a.
b.
c.
d.
e.
Calculer et . Expliquer pourquoi le développement du produit donnant fait apparaître chaque diviseur de exactement une fois.
Calculer et à l'aide des décompositions, puis contrôler le résultat à l'aide de la relation .
Déterminer le plus petit entier naturel ayant exactement diviseurs positifs.
Soit . Montrer que est impair si et seulement si est le carré d'un entier.
Décomposition en facteurs premiers, valuations, diviseurs
Ce résultat figure dans certaines maquettes seulement ; voir l'encadré Selon les facs du cours.
Dans tout l'exercice, est un nombre premier. Pour non nul, la valuation -adique est l'exposant de dans la décomposition de en facteurs premiers, avec si . On admet les deux faits suivants, qui découlent du théorème fondamental de l'arithmétique :
Soient non nuls.
a. Montrer que .
b. On suppose . Montrer que , avec égalité lorsque .
c. Donner un exemple où et où l'inégalité est stricte.
La formule de Legendre. Soit .
a. Soit . Montrer que l'ensemble contient exactement multiples de .
b. Soit . Montrer que est égal au nombre d'entiers tels que .
c. En déduire la formule de Legendre :
et expliquer pourquoi cette somme ne comporte qu'un nombre fini de termes non nuls. Contrôler la formule sur .
Par combien de zéros se termine l'écriture décimale de ?
On rappelle (chapitre « Dénombrement et combinatoire ») que est un entier. Calculer .
Soit et .
a. Montrer que pour tout réel , .
b. Retrouver, par la formule de Legendre et sans dénombrement, que divise .
c. Montrer que pour tout nombre premier .
d. Montrer que est pair.
Décomposition en facteurs premiers, valuations, diviseursNombres premiers : crible, infinité, lemme d'Euclide
Pour un nombre premier et un entier , on note l'exposant de dans la décomposition de en facteurs premiers ( si ), de sorte que , le produit ne comportant qu'un nombre fini de facteurs différents de .
Soit . Montrer que est rationnel si et seulement si est le carré d'un entier. En déduire que est irrationnel.
Montrer que est irrationnel.
Montrer que est irrationnel.
Montrer que est irrationnel.
a. Soient . Montrer que si , alors .
b. Soient tels que et . Montrer qu'il existe tel que et . Déterminer ainsi tous les couples tels que .
c. Montrer, par un exemple, que la conclusion de la question b peut être fausse si .
Nombres premiers : crible, infinité, lemme d'EuclideThéorème de Gauss et ses corollairesRédaction : citer Gauss, Bézout et le lemme d'Euclide avec leurs hypothèses
Dans tout l'exercice, désigne un nombre premier, un entier naturel non nul, et des entiers relatifs.
Pour chacune des affirmations suivantes, dire si elle est vraie ou fausse. Une affirmation vraie se démontre, en citant chaque théorème employé avec son hypothèse ; une affirmation fausse se réfute par un contre-exemple explicite, et l'on propose alors une version corrigée (hypothèse renforcée ou conclusion affaiblie), que l'on démontre.
Si , alors .
Si , alors .
Si , alors ou .
Pour tout , .
Deux nombres premiers distincts sont premiers entre eux.
Si , alors .
Si , alors .
Pour tout entier tel que , le nombre premier divise . Que devient cette affirmation si l'on remplace par ?
Pour la dernière affirmation, on pourra utiliser la formule du pivot, démontrée dans le chapitre « Dénombrement et combinatoire » : pour , .
Congruences modulo n et compatibilité avec les opérations
Déterminer le reste de la division euclidienne :
a. de par ;
b. de par ;
c. de par ;
d. de par ;
e. de par .
Quel est le chiffre des unités de l'écriture décimale de ?
On pose pour . Démontrer que divise pour tout , de deux façons :
a. par récurrence sur , en exprimant à l'aide de ;
b. par congruences, en raisonnant selon le reste de dans la division euclidienne par .
Démontrer que est divisible par pour tout .
En dressant la table des restes modulo , démontrer que est divisible par pour tout .
Congruences modulo n et compatibilité avec les opérations
Ce résultat figure dans certaines maquettes seulement ; voir l'encadré Selon les facs du cours.
Tout entier naturel s'écrit en base dix sous la forme
où les chiffres sont des entiers de . Dans cet exercice, et dans lui seulement, on note l'entier qui s'écrit ainsi : la barre désigne ici l'écriture décimale, et non une classe modulo . Par exemple, désigne l'entier à six chiffres .
Démontrer que . En déduire un critère de divisibilité par , puis par .
Démontrer que , et en déduire un critère de divisibilité par .
Démontrer que est divisible par si et seulement si l'entier , formé par ses deux derniers chiffres, l'est.
a. Vérifier que et que .
b. On découpe l'écriture de en tranches de trois chiffres à partir de la droite : , avec dans . On pose . Démontrer que , et en déduire un critère de divisibilité qui teste , et en même temps.
Appliquer ces critères aux deux entiers et : lesquels des entiers , , , , , divisent-ils ?
Déterminer le chiffre pour lequel l'entier est divisible par .
Déterminer les chiffres et , avec , pour lesquels l'entier est divisible par .
Congruences modulo n et compatibilité avec les opérations
Pour , dresser la table des carrés modulo : pour chaque reste , donner le reste de dans la division par . En déduire les restes possibles du carré d'un entier modulo , , et . On pourra remarquer que et ont des carrés congrus modulo .
Démontrer que l'équation n'a aucune solution .
Démontrer que l'équation n'a aucune solution . En déduire que n'est pas la somme de deux carrés d'entiers. Le même argument s'applique-t-il à ?
Démontrer qu'aucun entier de la forme , avec , n'est la somme de trois carrés d'entiers. La réciproque est-elle vraie ? On pourra examiner l'entier .
On considère l'équation , d'inconnue .
a. Montrer que la réduction modulo , la réduction modulo et la réduction modulo ne permettent pas de conclure.
b. Démontrer que l'équation n'a aucune solution.
a. Démontrer que si , alors et .
b. En déduire que l'équation n'a pas d'autre solution dans que . On pourra raisonner par l'absurde, en considérant une solution non nulle pour laquelle l'entier est le plus petit possible.
Équations diophantiennes linéaires ax + by = cRelation de Bézout, théorème de Bézout, entiers premiers entre euxThéorème de Gauss et ses corollaires
On considère l'équation , d'inconnue .
a. Par l'algorithme d'Euclide étendu, déterminer des entiers et tels que . En déduire une solution particulière de .
b. Résoudre dans , en rédigeant l'analyse et la synthèse.
Résoudre dans l'équation . Pourquoi est-il indispensable de commencer par simplifier ?
Démontrer que l'équation n'a aucune solution dans .
Déterminer les solutions de telles que et appartiennent tous deux à .
Dans un repère du plan, on note la droite d'équation . Décrire l'ensemble des points de à coordonnées entières, et expliquer pourquoi deux d'entre eux qui se suivent sont toujours séparés du même vecteur.
Équations diophantiennes linéaires ax + by = cCongruences modulo n et compatibilité avec les opérations
Ce problème figure dans le Manuel de calcul de Zhang Qiujian (Chine, cinquième siècle) : « Un coq coûte pièces, une poule pièces, et trois poussins coûtent ensemble pièce. Avec pièces, on achète volatiles. Combien de coqs, de poules et de poussins ? »
On note , et les nombres de coqs, de poules et de poussins achetés. Dans les questions 1 à 3, on exige d'acheter au moins un volatile de chaque espèce : , et sont des entiers naturels non nuls.
Traduire l'énoncé par un système de deux équations, et montrer qu'il équivaut au système formé de l'équation et de l'égalité .
Résoudre l'équation dans , en rédigeant l'analyse et la synthèse. Retrouver ensuite, par un calcul de congruences modulo , que est nécessairement un multiple de .
Exprimer à l'aide du paramètre de la question 2. Le prix des poussins impose-t-il une condition supplémentaire sur ? Déterminer toutes les solutions du problème.
Que devient la réponse si l'on autorise qu'une espèce soit absente de l'achat ?
Variante. Avec les mêmes prix, on achète volatiles pour pièces, au moins un de chaque espèce. Combien le problème a-t-il de solutions ?
Rédaction : citer Gauss, Bézout et le lemme d'Euclide avec leurs hypothèsesCongruences modulo n et compatibilité avec les opérationsThéorème de Gauss et ses corollaires
Les quatre textes ci-dessous sont des copies d'étudiants, numérotées ligne par ligne. Chacune contient au moins une faute de raisonnement ou de justification. Pour chacune, répondre aux quatre questions suivantes.
(a) Question posée : résoudre dans la congruence .
(b) Question posée : résoudre dans l'équation .
(c) Question posée : résoudre dans la congruence .
(d) Question posée : déterminer le reste de la division euclidienne de par .
Systèmes de congruences, théorème chinois, chiffrement RSARelation de Bézout, théorème de Bézout, entiers premiers entre eux
Ce résultat figure dans certaines maquettes seulement ; voir l'encadré Selon les facs du cours.
Le problème de Sunzi (Chine, entre le troisième et le cinquième siècle) : « Il y a des objets dont on ne connaît pas le nombre. Comptés par , il en reste ; comptés par , il en reste ; comptés par , il en reste . Combien y a-t-il d'objets ? » On cherche donc les entiers tels que
a. Trouver des entiers et tels que . Vérifier que satisfait les deux premières congruences, puis démontrer que les entiers qui les satisfont toutes les deux sont exactement ceux qui sont congrus à modulo .
b. Par la même méthode, résoudre le système complet. Vérifier le résultat.
Soient et deux entiers naturels non nuls premiers entre eux, et , deux entiers. En reprenant la démarche de la question 1.a, démontrer que le système
a des solutions, et que ses solutions forment exactement une classe modulo .
Lorsque les modules ne sont pas premiers entre eux.
a. Démontrer que le système , n'a aucune solution.
b. Démontrer que le système , équivaut à . Pourquoi le module obtenu est-il et non ?
Le nombre de soldats d'une armée est compris entre et . Rangés par , il en reste ; rangés par , il en reste ; rangés par , il en reste . Combien y a-t-il de soldats ?
Nombres premiers : crible, infinité, lemme d'EuclideCongruences modulo n et compatibilité avec les opérations
Ce résultat figure dans certaines maquettes seulement ; voir l'encadré Selon les facs du cours.
Dans tout l'exercice, on dit qu'un entier naturel est de la forme s'il existe tel que , c'est-à-dire si ; de même pour les formes , et . Par exemple, les nombres premiers de la forme inférieurs à sont .
Démontrer qu'un produit d'entiers naturels de la forme est de la forme .
Soit un entier de la forme .
a. Démontrer que tous les facteurs premiers de sont impairs.
b. Démontrer que possède au moins un facteur premier de la forme .
On suppose, par l'absurde, qu'il n'existe qu'un nombre fini de nombres premiers de la forme , et on les note (on a , puisque en est un). On pose .
a. Démontrer que est de la forme et que .
b. Démontrer qu'aucun des ne divise , et conclure. Pourquoi le facteur premier fourni par la question 2 ne peut-il pas être ?
c. Calculer pour les listes , et . L'entier est-il toujours premier ?
Démontrer de même qu'il existe une infinité de nombres premiers de la forme . On établira d'abord que tout nombre premier est de la forme ou de la forme .
Expliquer en une phrase pourquoi la même méthode ne démontre pas, telle quelle, qu'il existe une infinité de nombres premiers de la forme .
L'anneau Z/nZ : classes, opérations, tables, diviseurs de zéro
Dans tout l'exercice, désigne la classe de l'entier , modulo quand on travaille dans et modulo quand on travaille dans . Dans une table de multiplication de , la case de la ligne et de la colonne contient le représentant de pris dans .
Le produit de peut se calculer avec les représentants et , ou avec les représentants et . Faire les deux calculs, puis dire en deux phrases quel résultat du cours garantit qu'ils donnent toujours la même classe. On ne redémontrera pas ce résultat.
Dresser la table de multiplication de , puis celle de , en omettant la ligne et la colonne de . Expliquer pourquoi on ne perd rien à les omettre.
Lecture des tables.
a. Quels sont les éléments inversibles de ? Donner l'inverse de chacun. Même question dans .
b. Un diviseur de zéro est une classe pour laquelle il existe une classe telle que . Déterminer les diviseurs de zéro de , en donnant pour chacun une classe qui convient. Pourquoi n'en a-t-il aucun ?
c. Déterminer l'ensemble des carrés de , c'est-à-dire des classes de la forme , puis celui de .
Résoudre l'équation dans , puis dans . Traduire le premier résultat en une phrase sur les entiers, et expliquer pourquoi les deux équations n'ont pas le même nombre de solutions.
Résoudre l'équation dans , en remarquant qu'elle équivaut à et en lisant la table. Montrer ensuite qu'elle n'a aucune solution dans .
Inversibles de Z/nZ, congruences linéaires, Z/pZ est un corpsRelation de Bézout, théorème de Bézout, entiers premiers entre eux
Un inverse par l'algorithme d'Euclide étendu.
a. Appliquer l'algorithme d'Euclide à et , puis le remonter pour trouver des entiers et tels que . En déduire que est inversible dans , et donner son inverse sous la forme avec .
b. Résoudre dans la congruence .
Le chiffrement affine. On numérote les lettres de à : , , et ainsi de suite jusqu'à . La lettre de numéro est chiffrée par la lettre de numéro , où est le reste de dans la division par ; autrement dit et .
a. Déterminer les éléments inversibles de .
b. Vérifier que , puis démontrer que équivaut à . En déduire que deux lettres distinctes ne sont jamais chiffrées par la même lettre.
c. Chiffrer le mot MOT, puis déchiffrer le résultat obtenu.
d. Pourquoi la règle ne pourrait-elle pas servir de chiffrement ? Exhiber deux lettres chiffrées de la même façon.
Le cas général. En citant le théorème du cours sur les congruences linéaires , résoudre dans les congruences et . Pour la première, donner les solutions modulo , puis la liste des classes solutions modulo .
Inversibles de Z/nZ, congruences linéaires, Z/pZ est un corpsL'anneau Z/nZ : classes, opérations, tables, diviseurs de zéroNombres premiers : crible, infinité, lemme d'Euclide
Dans tout l'exercice, est un entier supérieur ou égal à . On rappelle que est un corps lorsque tout élément non nul y est inversible, et qu'un diviseur de zéro est une classe pour laquelle il existe avec .
Le théorème.
a. On suppose premier. Soit . Montrer que , puis que est inversible. Conclure.
b. On suppose non premier. Montrer qu'on peut écrire avec et . Montrer que , , , et en déduire que n'est pas inversible. Conclure.
L'équation .
a. Soit un nombre premier. Montrer que, dans , l'équation a exactement deux solutions, et .
b. Résoudre la même équation dans . Quel argument de la question a ne s'applique plus ?
L'équation .
a. Vérifier que pour tout .
b. Soit un nombre premier. Montrer que l'équation a exactement deux solutions dans . Que deviennent-elles pour ?
c. Montrer qu'elle a quatre solutions dans .
d. Le chapitre « Polynômes et fractions rationnelles » établit qu'un polynôme non nul de degré a au plus deux racines. Expliquer pourquoi la question c ne contredit pas ce théorème : quelle propriété, utilisée dans sa démonstration, manque à ?
Inversible ou diviseur de zéro. Soit et .
a. Montrer que si , alors est inversible.
b. Montrer que si , alors est un diviseur de zéro (on écrira et ).
c. Montrer qu'un élément inversible n'est jamais un diviseur de zéro. Énoncer la conclusion, et l'illustrer dans .
Petit théorème de Fermat, indicatrice et théorème d'EulerNombres premiers : crible, infinité, lemme d'Euclide
Ce résultat figure dans certaines maquettes seulement ; voir l'encadré Selon les facs du cours.
Soit un nombre premier. Le petit théorème de Fermat affirme que pour tout , et que pour tout non divisible par . On en donne deux démonstrations indépendantes, puis on examine sa réciproque.
Par le binôme. On rappelle que et la formule du binôme de Newton, démontrées dans le chapitre « Dénombrement et combinatoire ».
a. Vérifier que pour , puis montrer que divise pour .
b. En déduire que pour tout .
c. Démontrer par récurrence que pour tout , puis étendre le résultat à tout .
d. En déduire que lorsque ne divise pas .
Par les classes. Soit un entier non divisible par . On note l'ensemble des classes non nulles de , et , .
a. Montrer que est bien à valeurs dans , qu'elle est injective, puis qu'elle est bijective.
b. Calculer de deux façons le produit , et en déduire que .
c. Écrire la liste pour et , et vérifier sur cet exemple la conclusion de b.
La réciproque est fausse.
a. Vérifier que . En déduire que , alors que n'est pas premier.
b. Calculer le reste de dans la division par , puis dans la division par . En déduire que , puis que le reste de dans la division par est .
c. Que permet de conclure sur le calcul de b, à lui seul ?
Petit théorème de Fermat, indicatrice et théorème d'EulerCongruences modulo n et compatibilité avec les opérations
Le petit théorème de Fermat et le théorème d'Euler figurent dans certaines maquettes seulement ; voir l'encadré Selon les facs du cours.
Déterminer le reste de dans la division par .
Un lemme, et .
a. Soit un nombre premier et un entier tel que divise . Montrer que pour tout .
b. En déduire que est divisible par pour tout .
Montrer que est divisible par pour tout , sachant que . Le nombre premier divise-t-il pour tout ?
Un inverse par Fermat. Montrer que la classe de est l'inverse de dans . Calculer le reste de dans la division par par carrés successifs, puis contrôler le résultat par l'algorithme d'Euclide étendu.
Les deux derniers chiffres de . Calculer , puis déterminer les deux derniers chiffres de l'écriture décimale de à l'aide du théorème d'Euler.
Petit théorème de Fermat, indicatrice et théorème d'EulerInversibles de Z/nZ, congruences linéaires, Z/pZ est un corpsSystèmes de congruences, théorème chinois, chiffrement RSA
L'indicatrice d'Euler et le théorème d'Euler figurent dans certaines maquettes seulement ; voir l'encadré Selon les facs du cours.
Pour , on note le nombre d'entiers tels que . Pour , c'est aussi le nombre d'éléments de , ensemble des inversibles de .
Soit un nombre premier et . Montrer que , en comptant les entiers de qui ne sont pas premiers avec .
Calculer en dressant la liste des entiers concernés. Calculer ensuite , et , à l'aide du résultat du cours (conséquence du théorème chinois, admis ici) : si , alors . On justifiera que est premier.
Le théorème d'Euler. Soit et un entier tel que . On note et , .
a. Montrer que est bien définie (à valeurs dans ) et bijective.
b. En calculant de deux façons le produit des éléments de , démontrer que .
c. Illustrer la démonstration pour et , puis dire ce que devient le théorème lorsque est premier.
Une identité.
a. Vérifier que pour , la somme portant sur les diviseurs positifs de .
b. Pour et diviseur positif de , on pose . Montrer que les ensembles forment une partition de , que a éléments, et en déduire l'identité pour tout .
Montrer que est pair pour tout , en considérant l'application .
Petit théorème de Fermat, indicatrice et théorème d'EulerSystèmes de congruences, théorème chinois, chiffrement RSAInversibles de Z/nZ, congruences linéaires, Z/pZ est un corps
Le chiffrement RSA, comme le petit théorème de Fermat et le théorème chinois sur lesquels il repose, figure dans certaines maquettes seulement ; voir l'encadré Selon les facs du cours.
Alice choisit les nombres premiers et , calcule et , et choisit . Elle publie la clé publique et garde secrets , , et la clé privée , définie ci-dessous. Un message est un entier ; pour l'envoyer à Alice, on calcule le reste de dans la division par . Alice déchiffre en calculant le reste de dans la division par .
Vérifier que , puis déterminer par l'algorithme d'Euclide étendu l'entier tel que .
Chiffrer le message par carrés successifs modulo .
Déchiffrer le message obtenu, en calculant modulo par carrés successifs, et vérifier qu'on retrouve .
Le calcul d'Alice. Calculer modulo et modulo à l'aide du petit théorème de Fermat, et en déduire de nouveau le reste de modulo .
Pourquoi le déchiffrement marche. Soient deux nombres premiers, , et des entiers tels que . Démontrer que pour tout , y compris lorsque ou divise . En déduire que le déchiffrement redonne toujours le message.
Pourquoi c'est sûr. Expliquer pourquoi la connaissance de ne livre pas facilement. Montrer qu'au contraire la connaissance de permet de retrouver et : exprimer en fonction de et , puis retrouver et dans l'exemple.
Congruences modulo n et compatibilité avec les opérationsNombres premiers : crible, infinité, lemme d'Euclide
Soit un polynôme à coefficients entiers, de degré (donc ). On rappelle le résultat du chapitre « Polynômes et fractions rationnelles » : un polynôme non nul de degré a au plus racines réelles.
Soit . Montrer que, pour tous , entraîne .
Soit tel que . Montrer que divise pour tout . Que donnerait le même raisonnement si valait ou ?
Le théorème.
a. Montrer qu'il existe tel que .
b. Montrer qu'il existe une infinité d'entiers tels que n'est pas un nombre premier. En déduire qu'aucun polynôme non constant à coefficients entiers ne prend que des valeurs premières sur .
Le polynôme d'Euler , dont on peut vérifier qu'il prend des valeurs premières pour .
a. Appliquer la question 2 avec pour trouver un entier tel que divise et . Factoriser .
b. Déterminer tous les entiers tels que divise .
c. En déduire une infinité d'entiers explicites pour lesquels est composé, et retrouver que est composé.
Petit théorème de Fermat, indicatrice et théorème d'EulerSystèmes de congruences, théorème chinois, chiffrement RSADécomposition en facteurs premiers, valuations, diviseurs
Le petit théorème de Fermat, sur lequel repose cet exercice, figure dans certaines maquettes seulement ; voir l'encadré Selon les facs du cours.
On dit qu'un entier est sans facteur carré si aucun carré de nombre premier ne divise , c'est-à-dire si pour tout nombre premier : est alors un produit de nombres premiers deux à deux distincts.
Le nombre .
a. Vérifier que .
b. Soit un entier tel que . Montrer que modulo , modulo et modulo , puis que .
c. Comparer avec l'exercice 31, où l'on a vu que mais , avec . Qu'est-ce qui, dans les calculs, distingue de ?
Le critère de Korselt (sens suffisant). Soit un entier composé, sans facteur carré, tel que divise pour tout nombre premier divisant .
a. Démontrer que pour tout , puis que pour tout premier avec .
b. Montrer, avec et , que l'hypothèse « sans facteur carré » ne peut pas être supprimée. À quel endroit la démonstration de a échoue-t-elle ?
Vérifier que et satisfont les hypothèses de la question 2.
Soit un entier qui satisfait les hypothèses de la question 2. Montrer que est impair et qu'il a au moins trois facteurs premiers (distincts).
On peut le travailler ensemble dès cette semaine. Une séance ciblée sur ce chapitre, et vous repartez au minimum avec une méthode.