[http://mp.cpgedupuydelome.

fr] édité le 3 novembre 2017 Enoncés 1

Arithmétique (c) Montrer

∀n ∈ N, ∀m ∈ N∗ , ϕn+m = ϕm ϕn+1 + ϕm−1 ϕn .

Divisibilité (d) En déduire

∀m, n ∈ N∗ , pgcd(ϕn , ϕm+n ) = pgcd(ϕn , ϕm )
Exercice 1 [ 01187 ] [Correction] puis pgcd(ϕm , ϕn ) = pgcd(ϕn , ϕr ) où r est le reste de la division euclidienne
Résoudre dans Z les équations suivantes : de m par n.
(a) x − 1 | x + 3 b) x + 2 | x2 + 2. (e) Conclure
pgcd(ϕm , ϕn ) = ϕpgcd(m,n) .

Exercice 2 [ 01188 ] [Correction]

Résoudre dans Z2 les équations suivantes : PGCD et PPCM

(a) xy = 3x + 2y (b) 1
x + 1
y = 1
5 (c) x2 −y 2 −4x−2y = 5 Exercice 6 [ 01195 ] [Correction]
Déterminer le pgcd et les coecients de l'égalité de Bézout (1730-1783) des entiers
a et b suivants :
Exercice 3 [ 02358 ] [Correction] (a) a = 33 et b = 24
Pour n ∈ N∗ , on désigne par N le nombre de diviseurs positifs de n et par P leur (b) a = 37 et b = 27
produit. Quelle relation existe-t-il entre n, N et P ? (c) a = 270 et b = 105.

Division euclidienne
Exercice 7 [ 01196 ] [Correction]
Soient a, b, d ∈ Z. Montrer l'équivalence :
Exercice 4 [ 01189 ] [Correction]
Soient a ∈ Z et b ∈ N∗ , on note q le quotient de la division euclidienne de a − 1 (∃u, v ∈ Z, au + bv = d) ⇐⇒ pgcd(a, b) | d.
par b.
Déterminer pour tout n ∈ N, le quotient de la division euclidienne de (abn − 1)
par bn+1 .
Exercice 8 [ 01197 ] [Correction]
Montrer que le pgcd de 2n + 4 et 3n + 3 ne peut être que 1, 2, 3 ou 6.
Exercice 5 [ 01215 ] [Correction]
On considère la suite (ϕn )n∈N dénie par Exercice 9 [ 01199 ] [Correction]
ϕ0 = 0, ϕ1 = 1 et ∀n ∈ N, ϕn+2 = ϕn+1 + ϕn . Soient d, m ∈ N. Donner une condition nécessaire et susante pour que le système

pgcd(x, y) = d
(a) Montrer
ppcm(x, y) = m
∗
∀n ∈ N , ϕn+1 ϕn−1 − ϕ2n = (−1) .
n

(b) En déduire possède un couple (x, y) ∈ N2 solution.

∀n ∈ N∗ , ϕn ∧ ϕn+1 = 1.

Diusion autorisée à titre entièrement gratuit uniquement - dD

[http://mp.cpgedupuydelome.fr] édité le 3 novembre 2017 Enoncés 2

Exercice 10 [ 01200 ] [Correction] (a) Justier l'existence d'au moins un couple solution (u0 , v0 ).
Résoudre dans N2 l'équation : (b) Montrer que tout autre couple solution est de la forme (u0 + kb, v0 − ka) avec
k ∈ Z.
pgcd(x, y) + ppcm(x, y) = x + y .
(c) Conclure.

Exercice 11 [ 01201 ] [Correction]

Résoudre dans N2 les systèmes : Exercice 17 [ 01208 ] [Correction]

pgcd(x, y) = 5

x + y = 100 (a) Pour n ∈ N, montrer qu'il existe un couple unique (an , bn ) ∈ N2 tel que
(a) (b) √ √
ppcm(x, y) = 60 pgcd(x, y) = 10
(1 + 2)n = an + bn 2.

Nombres premiers entre eux (b) Calculer a2n − 2b2n .

(c) En déduire que an et bn sont premiers entre eux.
Exercice 12 [ 01203 ] [Correction]
Soient a, b ∈ Z.
(a) On suppose a ∧ b = 1. Montrer que (a + b) ∧ ab = 1. Exercice 18 [ 01209 ] [Correction]
Soient a et b deux entiers relatifs premiers entre eux et d ∈ N un diviseur de ab.
(b) On revient au cas général. Calculer pgcd(a + b, ppcm(a, b)). Montrer
∃!(d1 , d2 ) ∈ N2 , d = d1 d2 , d1 | a et d2 | b.
Exercice 13 [ 01204 ] [Correction]
Montrer que pour tout n ∈ N∗ on a :
Exercice 19 [ 03624 ] [Correction]
(a) (n + n) ∧ (2n + 1) = 1
2
(b) (3n + 2n) ∧ (n + 1) = 1
2 Soit n ∈ N. Montrer que les entiers
ai = i.n! + 1
Exercice 14 [ 01205 ] [Correction] pour i ∈ {1, . . . , n + 1} sont deux à deux premiers entre eux.
Montrer que pour tout entier n ∈ N∗ , n + 1 et 2n + 1 sont premiers entre eux.
En déduire  
n+1|
2n
. Nombres premiers
n
Exercice 20 [ 03209 ] [Correction]
Soient n ≥ 2 et N la somme de n entiers impairs consécutifs. Montrer que N n'est
Exercice 15 [ 01206 ] [Correction] pas un nombre premier.
Soient a et b premiers entre eux et c ∈ Z.
Montrer que pgcd(a, bc) = pgcd(a, c).
Exercice 21 [ 01219 ] [Correction]
Exercice 16 [ 01207 ] [Correction] Montrer que les nombres suivants sont composés :
Soient a et b deux entiers premiers entre eux non nuls.
Notre but est de déterminer tous les couples (u, v) ∈ Z2 tels que au + bv = 1.

Diusion autorisée à titre entièrement gratuit uniquement - dD

[http://mp.cpgedupuydelome.fr] édité le 3 novembre 2017 Enoncés 3

(a) 4n3 + 6n2 + 4n + 1 avec n ∈ N∗ (b) n4 − n2 + 16 avec n ∈ Z. Exercice 29 [ 01212 ] [Correction]

Soit x ∈ Q. On suppose qu'il existe n ∈ N∗ tel que xn ∈ Z. Montrer que x ∈ Z.

Exercice 22 [ 03623 ] [Correction] Exercice 30 [ 01213 ] [Correction]

Soit n un naturel non nul. Montrer qu'il existe toujours un nombre premier Soient a, b ∈ N∗ . On suppose qu'il existe m, n premiers entre eux tels que am = bn .
strictement compris entre n et n! + 2. Montrer qu'il existe c ∈ N∗ tel que a = cn et b = cm .

Exercice 23 [ 01224 ] [Correction] Exercice 31 [ 01214 ] [Correction]

Justier l'existence de 1 000 entiers consécutifs sans nombres premiers. On divise un cercle en n arcs égaux et on joint les points de division de p en p
jusqu'à ce qu'on revienne au point de départ. Quel est le nombre de côtés du
polygone construit ?
Exercice 24 [ 02369 ] [Correction]
On suppose que n est un entier ≥ 2 tel que 2n − 1 est premier.
Montrer que n est nombre premier. Exercice 32 [ 03669 ] [Correction]
On étudie l'équation algébrique
(E) : xn + an−1 xn−1 + · · · + a1 x + a0 = 0
Exercice 25 [ 02656 ] [Correction]
Soient des entiers a > 1 et n > 0. d'inconnue x et où les coecients a0 , a1 , . . . , an−1 sont supposés entiers.
Montrer que si an + 1 est premier alors n est une puissance de 2. Montrer que les solutions réelles de (E) sont entières ou irrationnelles.

Exercice 33 [ 01228 ] [Correction]

Exercice 26 [ 03351 ] [Correction] Soient p ∈ P et α ∈ N∗ . Déterminer les diviseurs positifs de pα .
Soient a, b ∈ N \ {0, 1} et n ∈ N∗ .
On suppose que an + bn est un nombre premier. Montrer que n est une puissance
de 2. Exercice 34 [ 01229 ] [Correction]
Soit n ∈ N \ {0, 1} et n = Nk=1 pk sa décomposition primaire.
αk
Q
Quel est le nombre de diviseurs positifs de n ?
 ] [Correction]
Exercice27 [ 01223
Soit E = 4k − 1  k ∈ N∗ .

Exercice 35 [ 01230 ] [Correction]
(a) Montrer que pour tout n ∈ E , il existe p ∈ P ∩ E tel que p | n. Soit n ∈ N \ {0, 1} dont la décomposition primaire est
(b) En déduire qu'il y a une innité de nombre premier p tel que p = −1 [4]. N

i .
Y
n= pαi

Études arithmétiques i=1

On note d(n) le nombre de diviseurs supérieurs ou égaux à 1 de n et σ(n) la

Exercice 28 [ 01225 ] [Correction] somme de ceux-ci.
Soit n ∈ N, montrer Montrer
√ N N
n ∈ Q ⇐⇒ ∃m ∈ N, n = m2 . pαi +1 − 1
(αi + 1) et σ(n) = .
Y Y
i
√ √ d(n) =
pi − 1
En déduire que 2 ∈/ Q et 3 ∈/ Q i=1 i=1

Diusion autorisée à titre entièrement gratuit uniquement - dD

[http://mp.cpgedupuydelome.fr] édité le 3 novembre 2017 Enoncés 4

Exercice 36 [ 01231 ] [Correction] Petit théorème de Fermat

Soit σ : Z → N qui à n ∈ Z associe la somme de diviseurs positifs de n.
(a) Soit p ∈ P et α ∈ N∗ . Calculer σ(pα ). Exercice 39 [ 01222 ] [Correction]
Soit p un nombre premier.
(b) Soient a, b ∈ Z premiers entre eux.
Montrer que tout diviseur positif d du produit ab s'écrit de manière unique (a) Montrer  
p
d = d1 d2 avec d1 et d2 diviseurs positifs de a et b. ∀k ∈ {1, 2, . . . , p − 1}, p | .
k
(c) En déduire que si a et b sont premiers entre eux alors σ(ab) = σ(a)σ(b).
(b) En déduire que
(d) Exprimer σ(n) en fonction de la décomposition primaire de n. ∀n ∈ Z, np ≡ n [p] .

Valuation p-adique Exercice 40 [ 03636 ] [Correction]

Soit n ≥ 2 un entier. On suppose
Exercice 37 [ 01226 ] [Correction]
∀a ∈ {1, . . . , n − 1}, an−1 ≡ 1 [n] .
Pour p ∈ P et n ∈ Z, on note vp (n) l'exposant de la plus grande puissance de p
divisant n. Montrer que n est un nombre premier
(a) Montrer que v2 (1 000!) = 994.
(b) Plus généralement, calculer vp (n!). On rappelle que
Exercice 41 [ 00204 ] [Correction]
  (Nombres de Carmichael) Soit n un entier supérieur à 2.
bpxc
∀x ∈ R, = bxc. On suppose que n pour tout facteur premier p de n, p2 ne divise pas n mais p − 1
p divise n − 1.
Établir
∀a ∈ Z, an ≡ a [n] .
Exercice 38 [ 02370 ] [Correction]
On note P l'ensemble des nombres premiers. Pour tout entier n > 0, on note vp (n)
l'exposant de p dans la décomposition de n en facteurs premiers. On note bxc la
partie entière de x. On note π(x) le nombre de nombres premiers au plus égaux à
x.
(a) Montrer
+∞  
n
.
X
vp (n!) =
pk
k=1

ln(2n)
(b) Montrer que 2n
divise pb ln p c .

Q
n p∈P;p≤2n

(c) Montrer que 2n

≤ (2n)π(2n) .


n

(d) Montrer que x

= O π(x) quand x → +∞


ln x

Diusion autorisée à titre entièrement gratuit uniquement - dD

[http://mp.cpgedupuydelome.fr] édité le 3 novembre 2017 Corrections 5

Corrections Exercice 3 : [énoncé]

En associant dans P 2 = P × P chaque diviseur d avec celui qui lui est conjugué
Exercice 1 : [énoncé] n/d, on obtient un produit de N termes égaux à n. Ainsi

(a) x = 1 n'est pas solution. Pour x 6= 1 : P 2 = nN .

x+3 4
x−1 | x+3 ⇐⇒ x−1 = 1+ x−1 ∈ Z ⇐⇒ x−1 ∈ D(4) = {1, 2, 4, −1, −2, −4}
Ainsi S = {2, 3, 5, 0, −1, −3}.
(b) x = −2 n'est pas solution. Pour x 6= −2 : Exercice 4 : [énoncé]
2 a − 1 = bq + r avec 0 ≤ r < b.
x + 2 | x2 + 2 ⇐⇒ xx+2 +2 6
= x − 2 + x+2 ∈ Z ⇐⇒ x + 2 ∈ D(6) =
abn − 1 = (bq + r + 1)bn − 1 = qbn+1 + bn (r + 1) − 1.
{1, 2, 3, 6, −1, −2, −3, −6}.
Or 0 ≤ bn (r + 1) − 1 < bn+1 donc la relation ci-dessus est la division euclidienne
Ainsi S = {−1, 0, 1, 4, −3, −4, −5, −8}. de abn − 1 par bn+1 .
Le quotient de celle-ci est donc q .
Exercice 2 : [énoncé]
(a) On a Exercice 5 : [énoncé]
xy = 3x + 2y ⇐⇒ (x − 2)(y − 3) = 6. (a) Par récurrence sur n ∈ N∗ :
En détaillant les diviseurs de 6 possibles, on obtient Pour n = 1 : ϕ2 ϕ0 − ϕ21 = 0 − 1 = −1 : ok.
Supposons la propriété établie au rang n ≥ 1.
S = (3, 9), (4, 6), (5, 5), (8, 4), (1, −3), (0, 0), (−1, 1), (−4, 2) .

ϕn+2 ϕn −ϕ2n+1 = (ϕn +ϕn+1 )ϕn −ϕn+1 (ϕn +ϕn−1 ) = ϕ2n −ϕn+1 ϕn−1 = −(−1)n = (−1
HR
(b) Pour x, y ∈ Z∗ ,
Récurrence établie.
1 1 1 (b) Par l'égalité de Bézout on obtient que ϕn ∧ ϕn+1 = 1 puisque la relation
+ = ⇐⇒ 5x + 5y = xy ⇐⇒ (x − 5)(y − 5) = 25.
x y 5 précédente permet d'écrire uϕn + vϕn+1 = 1 avec u, v ∈ Z.
En détaillant les diviseurs de 25 possibles, on obtient (c) Par récurrence sur m ∈ N∗
Pour m = 1 : ϕn+1 = ϕ1 ϕn+1 + ϕ0 ϕn car ϕ1 = 1 et ϕ0 = 0.
S = (6, 30), (10, 10), (30, 6), (4, −20), (−20, 4) . Supposons la propriété établie au rang n ≥ 1


(c) On a ϕn+m+1 = ϕ(n+1)+m = ϕm ϕn+2 +ϕm−1 ϕn+1 = ϕm ϕn+1 +ϕm ϕn +ϕm−1 ϕn+1 = ϕm+1 ϕ
HR
2 2 2 2
x − y − 4x − 2y = 5 ⇐⇒ (x − 2) − (y + 1) = 8
Récurrence établie.
et donc
(d)
x − y − 4x − 2y = 5 ⇐⇒ (x − y − 3)(x + y − 1) = 8.
2 2
pgcd(ϕm+n , ϕn ) = pgcd(ϕm ϕn−1 +ϕm−1 ϕn , ϕn ) = pgcd(ϕm ϕn−1 , ϕn ) = pgcd(ϕm , ϕn )
En détaillant les diviseurs de 8 possibles et sachant car ϕn ∧ ϕn−1 = 1.

x−y−3=a

x= a+b
+2 Par récurrence on obtient que
⇐⇒ 2
b−a
x+y−1=b y= 2 −1 ∀q ∈ Nϕm ∧ ϕn = ϕm+qn ∧ ϕn .
on obtient On en déduit alors pgcd(ϕm , ϕn ) = pgcd(ϕn , ϕr ) car on peut écrire
S = (5, 0), (5, −2), (−1, 0), (−1, −2) .

m = nq + r avec q ∈ N.

Diusion autorisée à titre entièrement gratuit uniquement - dD

[http://mp.cpgedupuydelome.fr] édité le 3 novembre 2017 Corrections 6

(e) Suivons l'algorithme d'Euclide calculant pgcd(m, n) : Exercice 10 : [énoncé]

a0 = m, a1 = n, a0 = a1 q1 + a2 , a1 = a2 q2 + a3 ,. . . , ap−1 = ap qp + 0 avec Soit (x, y) ∈ N2 un couple solution. Posons δ = pgcd(x, y).
ap = pgcd(m, n) On peut écrire
Or x = δx0 et y = δy 0 avec x0 ∧ y 0 = 1.
pgcd(ϕn , ϕm ) = pgcd(ϕa0 , ϕa1 ) = pgcd(ϕa1 , ϕa2 ) = . . . = pgcd(ϕap , ϕ0 ) = ϕap
L'équation devient :
car ϕ0 = 0.
Ainsi pgcd(ϕm , ϕn ) = ϕpgcd(m,n) . 1 + x0 y 0 = x0 + y 0 ⇐⇒ (x0 − 1)(y 0 − 1) = 0 ⇐⇒ x0 = 1 ou y 0 = 1.

Ainsi (x, y) est de la forme (δ, δk) ou (δk, δ) avec k ∈ N.

Inversement ces couples sont solutions.
Exercice 6 : [énoncé]
(a) pgcd(a, b) = 3 et 3a − 4b = 3.
Exercice 11 : [énoncé]
(b) pgcd(a, b) = 1 et 11b − 8a = 1
(a) Soit (x, y) solution. pgcd(x, y) = 5 donc x = 5x0 et y = 5y 0 avec x0 , y 0 ∈ N
(c) pgcd(a, b) = 15 et 2a − 5b = 15 premiers entre eux.
ppcm(x, y) = 5x0 y 0 = 60 donc x0 y 0 = 12 d'où

(x0 , y 0 ) ∈ (1, 12), (2, 6), (3, 4), (4, 3), (6, 2), (12, 1) .

Exercice 7 : [énoncé]
( =⇒ ) Supposons d = au + bv avec u, v ∈ Z. Les couples (2, 6) et (6, 2) sont à éliminer car 2 et 6 ne sont pas premiers
pgcd(a, b) | a et pgcd(a, b) | b donc pgcd(a, b) | au + bv = d. entre eux.
( ⇐= ) Supposons pgcd(a, b) | d. On peut écrire d = k pgcd(a, b) avec k ∈ Z. Finalement,
Par l'égalité de Bézout, il existe u0 , v0 ∈ Z tels que (x, y) ∈ (5, 60), (15, 20), (20, 15), (60, 5) .


Inversement : ok. Finalement S = (5, 60), (15, 20), (20, 15), (60, 5) .

au0 + bv0 = pgcd(a, b)
(b) Soit (x, y) solution. pgcd(x, y) = 10 donc x = 10x0 et y = 10y 0 avec x0 , y 0 ∈ N
et on a alors premiers entre eux.
d = au + bv x + y = 10(x0 + y 0 ) = 100 donc x0 + y0 = 10.
Sachant x0 ∧ y 0 = 1, il reste (x0 , y 0 ) ∈ (1, 9),
(3, 7), (7, 3), (9, 1) puis

avec u = ku0 et v = kv0 ∈ Z (x, y) ∈ (10, 90), (30, 70), (70, 30),  (90, 10) .
Inversement : ok. Finalement S = (10, 90), (30, 70), (70, 30), (90, 10) .

Exercice 8 : [énoncé]
3 × (2n + 4) − 2 × (3n + 3) = 6 donc pgcd(2n + 4, 3n + 3) | 6. Exercice 12 : [énoncé]
(a) pgcd(a, a + b) = pgcd(a, b) et pgcd(b, a + b) = pgcd(a, b) = 1.
Ainsi (a + b) ∧ a = 1 et (a + b) ∧ b = 1 donc (a + b) ∧ ab = 1.
Exercice 9 : [énoncé] (b) Posons δ = pgcd(a, b). On peut écrire a = δa0 et b = δb0 avec a0 ∧ b0 = 1.
Si le système possède une solution alors d | m est une condition nécessaire. pgcd(a + b, ppcm(a, b)) = δ pgcd(a0 + b0 , ppcm(a0 , b0 )) = δ
Inversement si d | m alors x = d et y = m donne un couple (x, y) ∈ N2 solution.
Exercice 13 : [énoncé]

Diusion autorisée à titre entièrement gratuit uniquement - dD

[http://mp.cpgedupuydelome.fr] édité le 3 novembre 2017 Corrections 7

(a) n2 + n = n(n + 1). (b) Soit (u, v) ∈ Z2 un couple solution. On a au + bv = 1 = au0 + bv0 donc
1 × (2n + 1) − 2 × n = 1 donc (2n + 1) ∧ n = 1. a(u − u0 ) = b(v0 − v)
2 × (n + 1) − 1 × (2n + 1) = 1 donc (2n + 1) ∧ (n + 1) = 1 On a a | b(v0 − v) or a ∧ b = 1 donc a | v0 − v . Ainsi ∃k ∈ Z tel que
Par produit (2n + 1) ∧ (n2 + n) = 1. v = v0 − ka et alors a(u − u0 ) = b(v0 − v) donne a(u − u0 ) = abk puis
(b) 3n2 + 2n = n(3n + 2). u = u0 + kb (sachant a 6= 0).
1 × (n + 1) − 1 × n = 1 donc n ∧ (n + 1) = 1. (c) Inversement les couples de la forme ci-dessus sont solutions.
3 × (n + 1) − 1 × (3n + 2) = 1 donc (3n + 2) ∧ (n + 1) = 1.
Par produit (3n2 + 2n) ∧ (n + 1) = 1.
Exercice 17 : [énoncé]
(a) Unicité : Si (an , bn ) et (αn , βn ) sont solutions alors
Exercice 14 : [énoncé] √ √
2 × (n + 1) − 1 × (2n + 1) = 1 donc (n + 1) ∧ (2n + 1) = 1. an + bn 2 = αn + βn 2
On a 
2n + 1
  
2n + 1 2n donc √
n+1
=
n+1 n (bn − βn ) 2 = (αn − an ).

donc Si bn 6= βn alors
   √ αn − a
2n + 1 2n 2= ∈Q
(n + 1) = (2n + 1) . bn − βn
n+1 n
ce qui est absurde.
Puisque 2n+1
∈ Z, on a


n+1 On en déduit bn = βn puis an = αn
  Existence : Par la formule du binôme
2n
(n + 1) | (2n + 1) √ n  
n √ k
n (1 + 2) =n
X
2 .
k
or (n + 1) ∧ (2n + 1) = 1 donc k=0

  En séparant les termes d'indices pairs de ceux d'indices impairs, on a

2n
(n + 1) | . (1 +
√ √
2)n = an + bn 2
n

avec
bn/2c   b(n−1)/2c  
n p n
Exercice 15 : [énoncé] 2 et bn = 2p .
X X
an =
Posons d = pgcd(a, bc) et δ = pgcd(a, c). p=0
2p p=0
2p + 1
On δ | a et δ | c donc δ | bc puis δ | d.
Inversement d | a et d | bc. (b) On a √ √

Or d ∧ b = 1 car d | a et a ∧ b = 1. Donc d | c puis d | δ . a2n − 2b2n = (an + bn 2) an − bn 2 .
Par double divisibilité d = δ . Or en reprenant les calculs qui précèdent
√ √
(1 − 2)n = an − bn 2
Exercice 16 : [énoncé] donc √ √
(a) Théorème de Bézout. a2n − 2b2n = (1 + 2)n (1 − 2)n = (−1)n .

Diusion autorisée à titre entièrement gratuit uniquement - dD

[http://mp.cpgedupuydelome.fr] édité le 3 novembre 2017 Corrections 8

(c) La relation qui précède permet d'écrire (b) n4 − n2 + 16 = (n2 + 4)2 − 9n2 = (n2 − 3n + 4)(n2 + 3n + 4).
De plus les équations n2 − 3n + 4 = 0, 1 ou − 1 et n2 + 3n + 4 = 0, 1 ou − 1
an u + bn v = 1 avec u, v ∈ Z. n'ont pas de solutions car toutes de discriminant négatif. Par conséquent
On en déduit que an et bn sont premiers entre eux. n4 − n2 + 16 est composée.

Exercice 18 : [énoncé] Exercice 22 : [énoncé]

Unicité : Si (d1 , d2 ) est solution alors pgcd(d, a) = pgcd(d1 d2 , a) Considérons l'entier n! + 1. Celui-ci est divisible par un nombre premier p
Or d2 ∧ a = 1 car d2 | b et a ∧ b = 1, donc pgcd(d1 d2 , a) = pgcd(d1 , a) = d1 car inférieur à n! + 1.
d1 | a. Si ce nombre premier p est aussi inférieur à n alors il divise n! (car apparaît
De même d2 = pgcd(d, b) d'où l'unicité. comme l'un des facteurs de ce produit) et donc il divise aussi 1 = (n! + 1) − n!.
Existence : Posons d1 = pgcd(d, a) et d2 = pgcd(d, b). On a d1 | a et d2 | b. Ceci est absurde et donc le nombre premier en question est au moins égal à n + 1.
d1 | a et d2 | b donc d1 ∧ d2 = 1 car a ∧ b = 1. Finalement, il est strictement compris entre n et n! + 2.
d1 | d, d2 | d et d1 ∧ d2 = 1 donc d1 d2 | d.
Inversement : Par l'égalité de Bézout on peut écrire d1 = u1 d + v1 a et
d2 = u2 d + v2 b donc d | d1 d2 = U d + v1 v2 ab car d | ab. Exercice 23 : [énoncé]
Considérons les xk = 1001! + k avec 2 ≤ k ≤ 1001. Ce sont 1 000 entiers
consécutifs.
Exercice 19 : [énoncé] Pour tout 2 ≤ k ≤ 1001, on a k | (1001)! donc k | xk avec 2 ≤ k < xk donc xk ∈/ P .
Par l'absurde, supposons que ai et aj (avec i, j ∈ {1, . . . , n + 1}) ne soient pas
premiers entre eux.
Considérons d un diviseur premier commun à ai et aj . L'entier d est diviseur de Exercice 24 : [énoncé]
ai − aj donc de (i − j).n!. Si n = ab avec a, b ∈ N∗ alors
Puisque d est premier et diviseur de i − j ou de n!, il est nécessairement inférieur
à n et donc assurément diviseur de n!. Or d divise aussi ai = i.n! + 1 et donc d 2n − 1 = (2a − 1)(1 + 2a + · · · + 2a(b−1) )
divise 1. donc 2a − 1 | 2n − 1 d'où 2a − 1 = 1 ou 2a − 1 = 2n − 1 ce qui implique a = 1 ou
C'est absurde. a = n.
Ainsi n ne possède que des diviseurs triviaux, il est premier.
Exercice 20 : [énoncé]
Notons 2p + 1 le premier nombre impair sommé. On a Exercice 25 : [énoncé]
n−1 On peut écrire
n = 2k (2p + 1).
X
N= (2k + 2p + 1) = n(n + 2p)
k=0
On a alors
avec n ≥ 2 et n + 2p ≥ 2. Ainsi N est composé. 2p

X
an + 1 = b2p+1 − (−1)2p+1 = b − (−1) bk (−1)2p−k = (b + 1)c
Exercice 21 : [énoncé] k=0

(a) 4n3 + 6n2 + 4n + 1 = (n + 1)4 − n4 = ((n + 1)2 − n2 )((n + 1)2 + n2 ) = avec b = a2 .

k

(2n + 1)(2n2 + 2n + 1). On en déduit que b + 1 | an + 1, or an + 1 est supposé premier et b + 1 > 1 donc
Cet entier est composé pour n ∈ N∗ car 2n + 1 ≥ 2 et 2n2 + 2n + 1 ≥ 2. b + 1 = an + 1 puis n = 2k .

Diusion autorisée à titre entièrement gratuit uniquement - dD

[http://mp.cpgedupuydelome.fr] édité le 3 novembre 2017 Corrections 9

Exercice 26 : [énoncé] Exercice 30 : [énoncé]

On peut écrire n = 2k (2p + 1) avec k, p ∈ N et l'enjeu est d'établir p = 0. Il existe u, v ∈ Z tel que mu + nv = 1.
Posons α = a2 et β = b2 . On a
k k
Analyse : Si c convient alors c = cmu+nv = bu av . A priori c ∈ Q.
Synthèse : Soit c = bu av . On a cn = bnu anv = amu anv = a et de même cm = b.
an + bn = α2p+1 + β 2p+1 = α2p+1 − (−β 2p+1 ). Puisque le nombre rationnel c possède une puissance entière, c ∈ Z.
On peut alors factoriser par α − (−β) = α + β et puisque an + bn est un nombre
premier, on en déduit que α + β = 1 ou α + β = an + bn . Puisque α, β ≥ 1, le cas
α + β = 1 est à exclure et puisque α ≤ an et β ≤ bn , le cas α + β = an + bn Exercice 31 : [énoncé]
entraîne Le nombre de côté du polygone construit est le plus petit entier k ∈ N∗ tel que
α = an et β = bn . n | kp.
Posons δ = pgcd(n, p). On peut écrire n = δn0 et p = δp0 avec n0 ∧ p0 = 1.
Puisque a ≥ 2, l'égalité α = an = α2p+1 entraîne p = 0 et nalement n est une n | kp ⇐⇒ n0 | kp0 i.e. n0 | k . Ainsi k = n0 = n/δ .
puissance de 2.

Exercice 27 : [énoncé] Exercice 32 : [énoncé]

Supposons x = p/q une racine rationnelle de l'équation (E) avec p et q premiers
(a) n est impair, il n'est donc pas divisible par 2. Si tous les nombres premiers p entre eux.
divisant n sont tels que p = 1 [4] alors n = 1 [4] et donc n ∈/ E En réduisant au même dénominateur, on obtient
(b) Supposons qu'il n'y ait qu'un nombre ni de nombres premiers p1 p2 . . . pn .
Considérons pn + an−1 qpn−1 + · · · + a1 pq n−1 + a0 q n = 0.
n = 4p1 p2 . . . pn − 1 ∈ E .
Puisque q divise an−1 qpn−1 + · · · + a1 pq n−1 + a0 q n , on obtient que q divise pn .
Il existe p ∈ P ∩ E tel que p | n mais p | p1 p2 . . . pn donc p | 1. Absurde. Or p et q sont premiers entre eux donc nécessairement q = 1 et donc x = p ∈ Z.
Ainsi les racines rationnelles de (E) sont entières.

Exercice 28 : [énoncé]
( ⇐= ) ok √ √
( =⇒ ) Si n ∈ Q alors on peut écrire n = pq avec p ∧ q = 1.
Exercice 33 : [énoncé]
Soit d ∈ Div(pα ) ∩ N. Notons β la plus grande puissance de p telle que pβ | d.
On a alors q 2 n = p2 donc n | p2 On peut écrire d = pβ k avec p 6 |k.
De plus q 2 n = p2 et p2 ∧ q 2 = 1 donne p2 | n. Puisque p 6 |k et p ∈ P on a p ∧ k = 1. Or k | pα × 1 donc, par Gauss : k | 1.
Par double divisibilité n = p2 . √ √ Par suite d = pβ avec β ∈ N. De plus d | pα donc pβ ≤ pα puis β ≤ α.
ni 2, ni 3 ne sont des carrés d'un entier, donc 2 ∈/ Q et 3 ∈/ Q. Inversement : ok.

Exercice 29 : [énoncé]
On peut écrire x = pq avec p ∈ Z, q ∈ N∗ et p ∧ q = 1. Exercice 34 : [énoncé]
xn = k ∈ Z donne q n k = pn . p ∧ q = 1 donc pn ∧ q n = 1. Puisque q n | pn × 1 on a Les diviseurs positifs sont les d = Nk=1 pk avec ∀1 ≤ k ≤ N, 0 ≤ βk ≤ αk .
βk
Q

q n | 1 (par Gauss). Le
QNchoix des βk conduisant à des diviseurs distincts, il y a exactement
Par suite q n = 1 et donc q = 1 et x = p ∈ Z. k=1 (αk + 1) diviseurs positifs de n.

Diusion autorisée à titre entièrement gratuit uniquement - dD

[http://mp.cpgedupuydelome.fr] édité le 3 novembre 2017 Corrections 10

Exercice 35 : [énoncé] (a) v2 (1 000!) = 500 + v2 (500!) car 1000! = 2500 × 500! × k avec k produit de
Soit d ∈ N diviseur de n. nombres impairs.
Tout diviseur premier de d estQaussi diviseur de n et c'est donc l'un des p1 , . . . , pN . v2 (1 000!) = 500 + 250 + 125 + 62 + 31 + 15 + 7 + 3 + 1 = 994.
Par suite, on peut écrire d = N i=1 pi avec βi ∈ N.
βi
(b) En isolant les multiples de p dans le produit décrivant p!, on obtient
pβi i | d donc pβi i | n d'où βi ≤ αi .     
Ainsi d est de la forme d = N n n
i=1 pi avec pour tout i ∈ {1, . . . , N }, 0 ≤ βi ≤ αi .
Q βi
vp (n!) = + vp !
Inversement de tels nombres sont bien diviseurs de n. p p
Il y a autant de nombres de cette forme distincts que de choix pour QNles puis
β1 , . . . , βN .Pour βi , il y a αi + 1 choix possibles, au total d(n) = i=1 (αi + 1).
     
n bn/pc bn/pc
De plus vp (n!) =
p
+
p
+ vp
p
!
α1 X
α2 αN or  
bpxc
X X
σ(n) = ... pβ1 1 pβ2 2 . . . pβNN = bxc
β1 =0 β2 =0 βN =0 p
avec x = n/p2 donne
α1
! α2
! αN
!
.
X X X
= pβ1 1 pβ2 2 ... pβNN 
bn/pc
  
n
β1 =0 β2 =0 βN =0 = 2
p p
Par sommation géométrique puis nalement      
n n n
N vp (n!) = + 2 + ··· + k
pα i +1
−1 p p p
.
Y
i
σ(n) =
i=1
pi − 1 avec  
ln n
k= .
ln p
Exercice 36 : [énoncé]
(a) Div(pα ) ∩ N = 1, p, p2 , . . . , pα donc σ(pα ) = p p−1−1 . Exercice 38 : [énoncé]
 α+1

(b) Soit d ∈ Div(ab) ∩ N. Posons d1 = pgcd(d, a) et d2 = pgcd(d, b). (a) Pour k susamment grand n/pk = 0, la somme évoquée existe donc car
 

On a d1 ∈ Div(a) ∩ N et d2 ∈ Div(b) ∩ N. elle ne comporte qu'un nombre ni de termes non nuls. n! = 1 × 2 × . . . × n,
Puisque a ∧ b = 1 on a d1 ∧ d2 = 1. Or d1 | d et d2 | d donc d1 d2 | d. parmi les entiers allant de 1 à n, il y en a exactement bn/pc divisibles par p,
d1 = du1 + av1 et d2 = du2 + bv2 donc d1 d2 = dk + abv1 v2 d'où d | d1 d2 . n/p2 divisibles par p2 , etc. . . donc


Finalement d = d1 d2 .
Supposons d = δ1 δ2 avec δ1 ∈ Div(a) ∩ N et δ2 ∈ Div(b) ∩ N.
+∞  
n
.
X
vp (n!) =
On a d1 | δ1 δ2 et d1 ∧ δ2 = 1 donc d1 | δ1 et de même δ1 | d1 puis d1 = δ1 . De pk
même d2 = δ2 . k=1

(b) On a
! !
(c) σ(ab) = = σ(a)σ(b).
P P P P P
d|ab d = d2 |b d1 d2 = d1 |a d1 d2 |b db
 
2n (2n)!
d1 |a
= .
α −1
n (n!)2
pi i+1
(d) Si n = pα1 1 . . . pαNN alors σ(n) = . Pour tout p ∈ P ,
QN
i=1 pi −1
  ∞    
(2n)! X 2n n
vp = −2 k
Exercice 37 : [énoncé] (n!)2
k=1
pk p

Diusion autorisée à titre entièrement gratuit uniquement - dD

[http://mp.cpgedupuydelome.fr] édité le 3 novembre 2017 Corrections 11

or b2xc − 2bxc = 0 ou 1 donc puis

2n n
ln k ∼ ln(2)(2n).
∞     X X
2n n n  o  ln(2n)  ln k − 2
.
X
≤ Card k ∈ N∗  2n/pk > 0 ≤

−2 k

pk p ln p k=1 k=1
k=1
On en déduit
De plus les nombres premiers diviseurs de 2n 2n
n = (n!)2 sont diviseurs d'un
(2n)!
= O(π(2n)).


ln 2n
entier inférieur à 2n (lemme d'Euclide) et sont donc eux-mêmes inférieur à
2n. Il en découle Ajoutons
x 2bx/2c
 
2n Y
b
ln(2n)
ln p c ∼
| p ln x ln 2bx/2c
n
p∈P;p≤2n

car toutes les puissances de nombres premiers intervenant dans la par calculs et π(x) ∼ π(2bx/2c) car π(x) et π(2bx/2c) ne diérent qu'au plus
ln(2n) d'une unité et π(x) → +∞.
décomposition de 2n n divisent
b ln p c
.

Q
p∈P;p≤2n p Finalement, une certaine satisfaction.
Notons qu'en fait ce produit désigne
ppcm(1, 2, . . . , 2n).
Exercice 39 : [énoncé]
(c) On a (a) On a    
 
2n p p p−1
≤
Y
p b
ln(2n)
ln p c ≤
Y
p
ln(2n)
ln p ≤
Y
π(2n)
(2n) = (2n) . =
n k k k−1
p∈P;p≤2n p∈P;p≤2n p∈P;p≤2n
donc    
(d) En passant au logarithme : p p−1
k =p .
k k−1
2n n
Par suite p | k kp .


ln k ≤ π(2n) ln(2n).
X X
ln k − 2
Or p est premier et k < p donc k ∧ p = 1 puis p | kp en vertu du théorème de


k=1 k=1
Gauss.
À l'aide d'une comparaison intégrale on obtient
(b) Par récurrence nie sur n ∈ {0, 1, . . . , p − 1}
Z n n
X Z (n+1) Pour n = 0 : ok
1
ln(t) dt ≤ ln k ≤
1
ln(t) dt Supposons la propriété établie au rang n ∈ {0, 1, . . . , p − 2}
k=1 Par la formule du binôme
donc n p−1  
X p
(n + 1)p = np + nk + 1 ≡ n + 1 [p]
X
n ln n − n + 1 ≤ ln k ≤ (n + 1) ln(n + 1) − n k
k=1 k=1

donc n car pour 1 ≤ k ≤ p − 1.  

X
ln k = n ln n − n + O(ln n). p
≡ 0 [p] .
k=1 k
Par suite Récurrence établie.
2n n Pour tout n ∈ Z, il existe r ∈ {0, 1, . . . , p − 1} tel que n ≡ r [p] et
X X
ln k − 2 ln k = 2n ln(2n) − 2n − 2(n ln n − n) + O(ln n)
np ≡ rp ≡ r ≡ n [p] .
k=1 k=1

Diusion autorisée à titre entièrement gratuit uniquement - dD

[http://mp.cpgedupuydelome.fr] édité le 3 novembre 2017 Corrections 12

Exercice 40 : [énoncé]
Pour tout a ∈ {1, . . . , n − 1}, a est premier avec n. En eet, un diviseur commun à
a et n est diviseur de an−1 − 1 et donc de 1.
On en déduit que n est premier puisque premier avec chaque naturel strictement
inférieur à lui-même.

Exercice 41 : [énoncé]
Par hypothèse, on peut écrire n = p1 p2 . . . pr avec p1 , . . . , pr nombres premiers
deux à deux distincts.
Soit a ∈ Z. Considérons i ∈ {1, . . . , r}.
Si pi ne divise pas a, le petit théorème de Fermat assure api −1 ≡ 1 [pi ].
Puisque pi − 1 divise n − 1, on a encore an−1 ≡ 1 [pi ] et donc an ≡ a [pi ]
Si pi divise a alors pi divise aussi an et donc an ≡ 0 ≡ a [pi ].
Enn, chaque pi divisant an − a et les pi étant deux à deux premiers entre eux,
n = p1 . . . pr divise an − a et nalement an ≡ a [n].
La réciproque de ce résultat est vraie.
Ce résultat montre que le petit théorème de Fermat ne caractérise pas les nombres
premiers. Les nombres non premiers satisfaisant le petit théorème de Fermat, sont
les nombres de Carmichael. Le plus petit d'entre eux est 561, le suivant 1105.

Diusion autorisée à titre entièrement gratuit uniquement - dD