Feuille 1
M1 MEEF - Arithmétique
Notre objectif n’est pas seulement de réussir à produire des solutions pour les exercices sui-
vants : nous souhaitons maı̂triser leur rédaction, et prendre du recul (quand nous le pourrons,
nous comparerons des solutions différentes).
Quand on ne précise pas, le terme entier désigne un entier relatif.
Exercice 1. Montrer que pour tout entier naturel n on a 7 qui divise 32n+1 + 2n+2 .
Exercice 2. Chercher tous les entiers n tels que n − 1 divise n + 3.
Exercice 3. Chercher tous les premiers p > 3 tels que 24 divise p2 − 1.
Exercice 4. Combien de diviseurs l’entier 18! admet-il ?
Exercice 5. Calculer le reste de 1001000 dans la division euclidienne par 13.
Exercice 6. Montrer que pour tout entier n on a n7 qui est congru à n modulo 42.
On essaiera d’être efficace.
Exercice 7. Déterminer l’ensemble des entiers relatifs n tels quel
1. n + 1 divise 13
2. n + 1 divise n2 + 1
3. n − 3 divise n2 − 3.
Exercice 8. Montrer que pour tout entier m on a
a) m(m + 1)(m + 2)(m + 3) qui est divisible par 24 et
b) m(m + 1)(m + 2)(m + 3)(m + 4) qui est divisible par 120.
Exercice 9.
1. Chercher tous les entiers m et n tels que mn = 3m + 2n.
2. Construire un exercice destiné à une classe de Terminale amenant à résoudre cette équation,
de façon guidée.
Exercice 10.
Déterminer l’ensemble des entiers a et b tels que
1. P GCD(a, b) = 37 et a + b = 296.
2. P GCD(a, b) = 11 et a + b = 111.
Exercice 11. Pour tout entier relatif n calculer le PPCM de n et n + 1.
Exercice 12. Quels sont les entiers a et b tels que 3a 7b finisse par un 1 en base 10 ?
Exercice 13. Déterminer les couples d’entiers qui ont pour pgcd 18 et pour somme 360.
INSPE Nice-Toulon 1/5 Université Côte d’Azur
Exercice 14. Equations diophantiennes.
Résoudre les équations suivantes dans Z2 . On pourra reprendre le cours de Terminale.
a) 12x − 15y = 7
b) 7x + 5y = 3
q
3 5
Exercice 15. Démontrer que 4 est irrationnel.
Exercice 16. Démontrer que deux entiers sont premiers entre eux si et seulement si leur somme
et leur produit sont premiers entre eux.
Exercice 17. Montrer que pour tout (a, b) ∈ Z2 on a 7 qui divise a2 + b2 si et seulement
si 7 divise a et b.
Exercice 18.
1. Sans utiliser les congruences, retrouver les critères de divisibilité par 2, 3, 5, 10, 9,. . .
2. Quel peut être l’intérêt de la question précédente ?
Exercice 19. Soit p un nombre premier. Résoudre l’équation x2 − y 2 = p dans Z2 .
Exercice 20. Quels sont tous les entiers a et b tels que pgcd(a, b) = a + b − 1 ?
Exercice 21. On cherche à résoudre l’équation x2 = y 2 + x ∧ y + 2 dans N2 .
1. On suppose que deux entiers naturels x et y vérifient l’équation. Montrer que leur pgcd d
vérifie d = 1 ou d = 2.
2. En déduire que (x, y) = (2, 1) ou (x, y) = (2, 0) .
3. Conclure.
4. Quels types de raisonnement ont été utilisés dans cet exercice ?
Exercice 22. Une infinité de nombres premiers.
1. Montrer que l’ensemble des nombres premiers est infini. Un argument classique consiste à
considérer p1 . . . pn + 1 où les pi désignent...
2. Dans cette question on souhaite montrer que parmi ces nombres premiers il en existe une
infinité qui soient congrus à 3 modulo 4. On note T l’ensemble des nombres premiers congrus à
3 modulo 4.
2.1. Montrer que T est non vide.
2.2. Montrer que le produit de deux entiers congrus à 1 modulo 4 reste congru à 1 modulo 4.
2.3. On suppose que T est fini et que T = {p1 , p2 , . . . , pn }. On note a = 4p1 . . . pn − 1. Montrer
que a admet un diviseur premier congru à 3 modulo 4.
2.4 Aboutir à une contradiction et conclure.
Exercice 23. Un théorème du cours très important, mais souvent malmené.
On considère trois entiers relatifs non nuls m, n et k ainsi que les deux propositions
a) mn | k et
b) m | k, n | k et m premier avec n.
1. Proposer un énoncé destiné à une classe de Terminale qui indique les implications éventuelles
entre ces deux propositions, et qui éventuellement indique quand il n’y a pas d’implication.
INSPE Nice-Toulon 2/5 Université Côte d’Azur
2. Donner une preuve de votre énoncé destinée à une classe de Terminale ayant connaissance
du cours d’arithmétique.
3. Analyser la proposition de réponse suivante :
M`o“n˚tˇr`o“n¯s `qfi˚u`e ˜b) ˚i‹m¯p˜lˇi`qfi˚u`e `affl). S̀o˘i˚t m, n `eˇt k ˚tˇr`o˘i¯s `e›n˚tˇi`eˇr¯s ”n`a˚tˇu˚r`e¨l˙s ”n`o“nffl ”n˚u˜l˙s. S˚u¯p¯p`o¸sfi`o“n¯s `qfi˚u`e
m | k, `qfi˚u`e n | k `eˇt `qfi˚u`e m ¯sfi`o˘i˚t ¯p˚r`e›m˚i`eˇrffl `a‹vfle´c n.
C`o“m‹m`e m | k `o“nffl `affl ˜l„`e›xˇi¯sfi˚t´e›n`c´e `d`e a ∈ Z ˚t´e¨l `qfi˚u`e ma = k.
D`e ”m`ê›m`e, `c´o“m‹m`e n | k `o“nffl `affl ˜l„`e›xˇi¯sfi˚t´e›n`c´e `d`e b ∈ Z ˚t´e¨l `qfi˚u`e nb = k.
O”nffl `affl `d`o“n`c ma = nb.
D`o“n`c m `d˚i‹v˘i¯sfi`e nb, `eˇt `d`o“n`c m `d˚i‹v˘i¯sfi`e n `o˘uffl b.
D`e ”m`ê›m`e, n `d˚i‹v˘i¯sfi`e ma, `eˇt `d`o“n`c n `d˚i‹v˘i¯sfi`e m `o˘uffl a.
R`a˚i¯sfi`o“n‹n`o“n¯s ¯p`a˚rffl `d˚i¯sfi¯j´o“n`cˇtˇi`o“nffl `d`e `c´a¯s : ¯sfi˚iffl m `d˚i‹v˘i¯sfi`e b, `a˜l´o˘r¯s ˚i˜l `e›xˇi¯sfi˚t´e t ∈ Z ˚t´e¨l `qfi˚u`e mt = b, `eˇt
`d`o“n`c mnt = k, `dffl’`o˘ùffl mn `d˚i‹v˘i¯sfi`e ˜b˘i`e›nffl k.
D`a‹n¯s ˜l´e `c´a¯s `o˘ùffl n `d˚i‹v˘i¯sfi`e a, `d`e ˜l´affl ”m`ê›m`e ˜f´a`ç´o“nffl ˚i˜l `e›xˇi¯sfi˚t´e t ∈ Z ˚t´e¨l `qfi˚u`e nt = a, `eˇt `d`o“n`c mnt = k
`eˇt `o“nffl `affl `e›n`c´o˘r`e mn `qfi˚u˚iffl `d˚i‹v˘i¯sfi`e k.
I˜l ”n`e ˚r`e˙sfi˚t´e `qfi˚u`e ˜l´e `c´a¯s `o˘ùffl m | n `eˇt n | m, `c´e `qfi˚u˚iffl ˚i‹m¯p˜lˇi`qfi˚u`e `qfi˚u`e m = n `o˘uffl m = −n. M`a˚i¯s m `eˇt
n ¯sfi`o“n˚t ¯p˚r`e›m˚i`eˇr¯s `e›n˚tˇr`e `eˇu‹x, `dffl’`o˘ùffl m `eˇt n ”n`e ¯p`eˇu‹vfle›n˚t ”vˆa˜l´o˘i˚rffl `qfi˚u`e 1 `o˘uffl −1, `eˇt `d`o“n`c mn ”vˆa˚u˚t
1 `o˘uffl −1 `eˇt ˚i˜l `d˚i‹v˘i¯sfi`e k.
En quel énoncé faux l’étudiant semble-t-il croire ? Prouver que cet énoncé est bien faux.
4. Démontrer le lemme d’Euclide, c’est-à-dire que pour tout nombre premier p et pour deux
entiers a et b, on a p qui divise ab si et seulement si p divise a ou p divise b. On proposera une
démonstration rapide, en deux ou trois lignes, en utilisant un théorème du cours.
5. On considère un entier naturel n ≥ 2. Montrer que pour tout (a, b, m) ∈ Z3 tel que m soit
premier avec n, l’égalité am ≡ bm(n) implique a ≡ b(n).
Exercice 24. Deux définitions de la congruence.
Dans deux cours différents, on trouve les deux définitions suivantes de la notion de congruence.
Définition 1. Soit a et b deux entiers relatifs et n un entier naturel tel que n ≥ 2. On dit que a
est congru à b modulo n si a et b ont même reste dans la division euclidienne par n. On note alors
a ≡ b (n).
Définition 2. Soit a et b deux entiers relatifs et n un entier naturel tel que n ≥ 2. On dit que a est
congru à b modulo n si a − b est un multiple de n. On note alors a ≡ b (n).
1. Donner un énoncé du théorème de division euclidienne dans Z.
2. Montrer que les deux définitions ci-dessus sont équivalentes.
3. Enoncer un résultat classique du cours sur les congruences, de votre choix, se démontrant
facilement et naturellement à l’aide de la Définition 2 puis le démontrer. On pourra par exemple
penser aux théorèmes du cours sur les opérations algébriques.
INSPE Nice-Toulon 3/5 Université Côte d’Azur
Exercice 25. Petit théorème de Fermat.
On souhaite dans cette partie proposer une démonstration du théorème suivant :
Petit théorème de Fermat. Soit a un entier naturel et p un nombre premier.
Si p ne divise pas a, alors ap−1 ≡ 1 (p).
Pour la suite on considère un nombre premier p fixé.
1. Montrer que pour tout entier k compris entre 1 et p − 1, on a p qui divise k! × kp .
2. Analyser cette proposition de réponse à la question précédente, et proposer une remédiation.
P̀a˚rffl `d`é¨fˇi‹n˚i˚tˇi`o“nffl `d`e˙s `c´ofle¨f¨fˇi`cˇi`e›n˚t˙s ˜b˘i‹n`o“m˚i`a˚u‹x `o“nffl `affl
p p! p!
k! k
= k! k!(p−k)! = (p−k)!
`dffl’`o˘ùffl p (p−k)! = k! `eˇt `d`o“n`c p `d˚i‹v˘i¯sfi`e k!
(p−1)! p p
k k
3. En déduire que pour tout entier k compris entre 1 et p − 1 on a p qui divise kp .
4. A l’aide du binôme de Newton, montrer que pour tout entier naturel a on a (a + 1)p ≡
ap + 1 (p).
5. En déduire que pour tout entier naturel a on a ap ≡ a (p).
6. Conclure.
7. Analyser la proposition de réponse suivante à la question 6.
8. Dans cette question on s’intéresse à une autre preuve de ce théorème, celle proposée dans
l’exercice suivant.
INSPE Nice-Toulon 4/5 Université Côte d’Azur
8.a. Dans cette sous-question, on souhaite prendre du recul par rapport à la question 2)b) .
Pour cela, on considère la fonction ϕa : Z/pZ → Z/pZ qui à la classe de t associe la classe de
a.t. Reformuler sans explication la question 2)b) en terme d’une propriété de cette fonction ϕa .
(On ne demande pas de corriger la question 2)b)) .
8.b. Proposer une correction de la question 4) à partir de la question 3) qui soit destinée à
une classe de Terminale.
Jusqu’à la fin de l’exercice, on souhaite prendre du recul avec nos connaissances du supérieur.
9. On considère un entier n ≥ 2. On suppose connue la structure d’anneau de Z/nZ, et
on souhaite montrer dans les questions suivantes que l’anneau Z/nZ est un corps si et seulement
si n est premier.
9.a. Montrer que si n n’est pas premier, alors Z/nZ n’est pas intègre, c’est-à-dire qu’il existe
deux éléments différents de 0 dont le produit égale 0.
9.b Montrer que si n est premier, alors Z/nZ est un corps. On pourra utiliser la relation de
Bézout.
9.c Conclure.
Exercice 26. Un petit défi. On définit quatre entiers A, B, C et D ainsi : A = 44444444 , B est
la somme des chiffres de A, C est la somme des chiffres de B et D est la somme des chiffres de
C. Calculer D.
Exercice 27. L’objectif de cet exercice est de trouver tous les couples d’entiers (a, b) tels que
ab = ba .
1. Montrer que pour tout entier n ≥ 3 on a 2n−1 > n.
2. Montrer que si deux entiers u et v sont premiers entre eux, alors pour tout entier n on a u
et v n qui sont premiers entre eux également.
3. Dans cette questions 3. on considère un couple d’entiers (a, b) solution du problème et tel
que 0 < a < b. On note d le pgcd de a et de b, et on considère des entiers a′ et b′ tels que a = da′
et b = db′ .
′
3.a Montrer que d = a et que dd(b −1) = b′d .
3.b Traiter les cas d = 1, d = 2 et d ≥ 3.
4. Conclure.
5. Proposer une autre solution de l’exercice basée sur l’étude de la fonction x 7→ ln(x)/x.
Exercice 28. L’objectif de cet exercice est prouver un point important du cours : la termi-
naison et la validité de l’algorithme d’Euclide.
1. Proposer une version simple de l’algorithme d’Euclide (on pourra décrire cet algorithme en
pseudocode).
2. Démontrer que toute suite d’entiers positifs strictement décroissante est finie.
3. En considérant la suite des restes calculés à chaque étape, montrer que l’algorithme termine.
(Remarquer qu’une des difficultés est de définir proprement cette suite des restes !)
4. On considère deux entiers naturels a et b, avec b non nul. On note r le reste dans la division
euclidienne de a par b. Montrer que pgcd(a, b) = pgcd(b, r).
5. Montrer la validité de l’algorithme d’Euclide, c’est-à-dire qu’il renvoie bien le résultat
souhaité.
INSPE Nice-Toulon 5/5 Université Côte d’Azur
