[[Link]

fr] édité le 1er septembre 2014 Enoncés 1

Arithmétique Exercice 7 [ 01215 ] [correction]

On considère la suite (ϕn )n∈N définie par

Divisibilité ϕ0 = 0, ϕ1 = 1 et ∀n ∈ N, ϕn+2 = ϕn+1 + ϕn

Exercice 1 [ 01187 ] [correction] a) Montrer

Résoudre dans Z les équations suivantes : ∀n ∈ N? , ϕn+1 ϕn−1 − ϕ2n = (−1)n
a) x − 1 | x + 3 b) x + 2 | x2 + 2.
b) En déduire
∀n ∈ N? , ϕn ∧ ϕn+1 = 1
Exercice 2 [ 01188 ] [correction] c) Montrer
Résoudre dans Z2 les équations suivantes :
∀n ∈ N, ∀m ∈ N? , ϕn+m = ϕm ϕn+1 + ϕm−1 ϕn
1 1 1
a) xy = 3x + 2y b) + = c) x2 − y 2 − 4x − 2y = 5 d) En déduire
x y 5
∀m, n ∈ N? , pgcd(ϕn , ϕm+n ) = pgcd(ϕn , ϕm )

puis pgcd(ϕm , ϕn ) = pgcd(ϕn , ϕr ) où r est le reste de la division euclidienne de m

Exercice 3 [ 00155 ] [correction] par n.
Soit A un ensemble de n + 1 > 2 entiers distincts tous inférieurs ou égaux à 2n. e) Conclure
Montrer qu’il existe deux éléments de A tels que l’un divise l’autre.
pgcd(ϕm , ϕn ) = ϕpgcd(m,n)

Exercice 4 [ 02358 ] [correction]

Pour n ∈ N? , on désigne par N le nombre de diviseurs positifs de n et par P leur
PGCD et PPCM
produit. Quelle relation existe-t-il entre n, N et P ?
Exercice 8 [ 01195 ] [correction]
Déterminer le pgcd et les coefficients de l’égalité de Bézout (1730-1783) des entiers
Division euclidienne a et b suivants :
a) a = 33 et b = 24 b) a = 37 et b = 27 c) a = 270 et b = 105.
Exercice 5 [ 01189 ] [correction]
Soient a ∈ Z et b ∈ N? , on note q le quotient de la division euclidienne de a − 1
par b.
Exercice 9 [ 01196 ] [correction]
Déterminer pour tout n ∈ N, le quotient de la division euclidienne de (abn − 1)
Soient a, b, d ∈ Z. Montrer l’équivalence :
par bn+1 .
(∃u, v ∈ Z, au + bv = d) ⇔ pgcd(a, b) | d

Exercice 6 [ 01198 ] [correction]

a) Montrer que si r est le reste de la division euclidienne de a ∈ N par b ∈ N? alors
2r − 1 est le reste de la division euclidienne de 2a − 1 par 2b − 1. Exercice 10 [ 01197 ] [correction]
b) Montrer que pgcd(2a − 1, 2b − 1) = 2pgcd(a,b) − 1. Montrer que le pgcd de 2n + 4 et 3n + 3 ne peut être que 1, 2, 3 ou 6.

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

[[Link] édité le 1er septembre 2014 Enoncés 2

Exercice 11 [ 01199 ] [correction] Exercice 17 [ 01205 ] [correction]

Soient d, m ∈ N. Donner une condition nécessaire et suffisante pour que le système Montrer que pour tout entier n ∈ N? , n + 1 et 2n + 1 sont premiers entre eux.
( En déduire !
pgcd(x, y) = d 2n
n+1|
ppcm(x, y) = m n

possède un couple (x, y) ∈ N2 solution.

Exercice 18 [ 01206 ] [correction]
Soient a et b premiers entre eux et c ∈ Z.
Exercice 12 [ 01200 ] [correction] Montrer que pgcd(a, bc) = pgcd(a, c).
Résoudre dans N2 l’équation :

pgcd(x, y) + ppcm(x, y) = x + y Exercice 19 [ 01207 ] [correction]

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.
Exercice 13 [ 01201 ] [correction] a) Justifier l’existence d’au moins un couple solution (u0 , v0 ).
Résoudre dans N2 les systèmes : b) Montrer que tout autre couple solution est de la forme (u0 + kb, v0 − ka) avec
( ( k ∈ Z.
pgcd(x, y) = 5 x + y = 100 c) Conclure.
a) b)
ppcm(x, y) = 60 pgcd(x, y) = 10

Exercice 20 [ 01208 ] [correction]

Nombres premiers entre eux a) Pour n ∈ N, montrer qu’il existe un couple unique (an , bn ) ∈ N2 tel que
√ √
Exercice 14 [ 01202 ] [correction] (1 + 2)n = an + bn 2
Soient a et b premiers entre eux.
Montrer que a ∧ (a + b) = b ∧ (a + b) = 1 puis (a + b) ∧ ab = 1. b) Calculer a2n − 2b2n .
c) En déduire que an et bn sont premiers entre eux.

Exercice 15 [ 01203 ] [correction]

Soient a, b ∈ Z. Exercice 21 [ 01209 ] [correction]
a) On suppose a ∧ b = 1. Montrer que (a + b) ∧ ab = 1. 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 16 [ 01204 ] [correction]

Exercice 22 [ 01210 ] [correction]
Montrer que pour tout n ∈ N? on a :
On note div(n) l’ensemble des diviseurs positifs d’un entier n ∈ Z.
a) (n2 + n) ∧ (2n + 1) = 1 b) (3n2 + 2n) ∧ (n + 1) = 1 Soient a, b ∈ Z premiers entre eux et ϕ : div(a) × div(b) → N définie par
ϕ(k, `) = k`.
Montrer que ϕ réalise une bijection de div(a) × div(b) vers div(ab).

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

[[Link] édité le 1er septembre 2014 Enoncés 3

Exercice 23 [ 03624 ] [correction] Exercice 31 [ 02656 ] [correction]

Soit n ∈ N. Montrer que les entiers Soient des entiers a > 1 et n > 0.
Montrer que si an + 1 est premier alors n est une puissance de 2.
ai = i.n! + 1

pour i ∈ {1, . . . , n + 1} sont deux à deux premiers entre eux. Exercice 32 [ 03351 ] [correction]
Soient a, b ∈ N\ {0, 1} et n ∈ N? .
Nombres premiers On suppose que an + bn est un nombre premier. Montrer que n est une puissance
de 2.

Exercice 24 [ 03209 ] [correction]

Soient n > 2 et N la somme de n entiers impairs consécutifs. Montrer que N n’est Exercice 33 [ 01223 ] [correction]
pas un nombre premier. Soit E = {4k − 1/k ∈ N? }.
a) Montrer que pour tout n ∈ E, il existe p ∈ P ∩ E tel que p | n.
b) En déduire qu’il y a une infinité de nombre premier p tel que p = −1 [4].
Exercice 25 [ 01219 ] [correction]
Montrer que les nombres suivants sont composés :
a) 4n3 + 6n2 + 4n + 1 avec n ∈ N? b) n4 − n2 + 16 avec n ∈ Z. Exercice 34 [ 02654 ] [correction]
Montrer qu’il existe une infinité de nombres premiers de la forme 4n + 3.

Exercice 26 [ 03623 ] [correction]

Soit n un naturel non nul. Montrer qu’il existe toujours un nombre premier Exercice 35 [ 02657 ] [correction]
n
strictement compris entre n et n! + 2. Soit, pour n ∈ N, Fn = 22 + 1.
a) Montrer, si (n, m) ∈ N2 avec n 6= m, que Fn ∧ Fm = 1.
b) Retrouver à l’aide du a) le fait que l’ensemble des nombres premiers est infini.
Exercice 27 [ 01224 ] [correction]
Justifier l’existence de 1000 entiers consécutifs sans nombres premiers.
Etudes arithmétiques

Exercice 28 [ 02653 ] [correction] Exercice 36 [ 01225 ] [correction]

Soit p un nombre premier, p > 5. Montrer que p2 − 1 est divisible par 24. Soit n ∈ N, montrer √
n ∈ Q ⇔ ∃m ∈ N, n = m2
√ √
En déduire que 2 ∈ / Q et 3 ∈ /Q
Exercice 29 [ 02369 ] [correction]
On suppose que n est un entier > 2 tel que 2n − 1 est premier.
Montrer que n est nombre premier. Exercice 37 [ 01211 ] [correction]
Soient a et b deux entiers relatifs tels que a2 | b2 . Montrer que a | b.

Exercice 30 [ 01220 ] [correction]

Soient a et p deux entiers supérieurs à 2. Exercice 38 [ 01212 ] [correction]
Montrer que si ap − 1 est premier alors a = 2 et p est premier. Soit x ∈ Q. On suppose qu’il existe n ∈ N? tel que xn ∈ Z. Montrer que x ∈ Z.

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

[[Link] édité le 1er septembre 2014 Enoncés 4

Exercice 39 [ 01213 ] [correction] Exercice 45 [ 01228 ] [correction]

Soient a, b ∈ N? . On suppose qu’il existe m, n premiers entre eux tels que am = bn . Soient p ∈ P et α ∈ N? . Déterminer les diviseurs positifs de pα .
Montrer qu’il existe c ∈ N? tel que a = cn et b = cm .

Exercice 46 [correction]
[ 01229 ]
Exercice 40 [ 01214 ] [correction] N
pα
Q
Soit n ∈ N\ {0, 1} et n = k
k sa décomposition primaire.
On divise un cercle en n arcs égaux et on joint les points de division de p en p k=1
jusqu’à ce qu’on revienne au point de départ. Quel est le nombre de côtés du Quel est le nombre de diviseurs positifs de n ?
polygone construit ?

Exercice 47 [ 01230 ] [correction]

Exercice 41 [ 03669 ] [correction] Soit n ∈ N\ {0, 1} dont la décomposition primaire est
On étudie l’équation algébrique
N
Y
n
(E) : x + an−1 x n−1
+ · · · + a1 x + a0 = 0 n= pα
i
i

i=1
d’inconnue x et où les coefficients a0 , a1 , . . . , an−1 sont supposés entiers.
Montrer que les solutions réelles de (E) sont entières ou irrationnelles. On note d(n) le nombre de diviseurs supérieurs ou égaux à 1 de n et σ(n) la
somme de ceux-ci.
Montrer
N N
Exercice 42 [ 02361 ] [correction]
Y Y piαi +1 − 1
√ d(n) = (αi + 1) et σ(n) =
Soit P ∈ Z [X] et a, b deux√entiers relatifs avec b > 0 et b irrationnel. i=1 i=1
pi − 1
a) Exemple : montrer que 6 est √ irrationnel.
de (a + b)n ?
b) Quelle est la forme √ √
c) Montrer que si a + √ b est racine de P alors a − b aussi. Exercice 48 [ 01231 ] [correction]
d) On suppose que a + b est racine double de P . Montrer que P = RQ2 avec R Soit σ : Z → N qui à n ∈ Z associe la somme de diviseurs positifs de n.
et Q dans Z [X]. a) Soit p ∈ P et α ∈ N? . Calculer σ(pα ).
b) Soient a, b ∈ Z premiers entre eux.
Montrer que tout diviseur positif d du produit ab s’écrit de manière unique
Exercice 43 [ 03681 ] [correction] d = d1 d2 avec d1 et d2 diviseurs positifs de a et b.
On note d(n) le nombre de diviseurs positifs de n ∈ N? . c) En déduire que si a et b sont premiers entre eux alors σ(ab) = σ(a)σ(b).
Déterminer un équivalent de d) Exprimer σ(n) en fonction de la décomposition primaire de n.
n
1X
d(k)
n
k=1
Exercice 49 [ 03725 ] [correction]
représentant la moyenne du nombre de diviseurs positifs des entiers inférieurs à n. [Théorème d’Aubry]
Soit N un entier strictement positif.
On suppose que le cercle d’équation x2 + y 2 = N possède un point rationnel
Exercice 44 [ 01227 ] [correction] (x0 , y0 ).
Soit n ∈ N\ {0, 1}. Montrer que n est le produit de ses diviseurs non triviaux si, et On introduit (x00 , y00 ) un point entier obtenu par arrondi de (x0 , y0 ).
seulement si, n = p3 avec p ∈ P ou n = p1 p2 avec p1 , p2 ∈ P distincts. En étudiant l’intersection du cercle avec la droite joignant (x0 , y0 ) et (x00 , y00 ),
montrer que le cercle contient un point entier (x1 , y1 ).

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

[[Link] édité le 1er septembre 2014 Enoncés 5

Valuation p-adique Montrer que n est un nombre premier

Exercice 50 [ 01226 ] [correction]

Pour p ∈ P et n ∈ Z, on note vp (n) l’exposant de la plus grande puissance de p Exercice 54 [ 00204 ] [correction]
divisant n. [Nombres de Carmichael]
a) Montrer que v2 (1000!) = 994. Soit n un entier supérieur à 2.
b) Plus généralement, calculer vp (n!). On rappelle que On suppose que n pour tout facteur premier p de n, p2 ne divise pas n mais p − 1
  divise n − 1.
bpxc Etablir
∀x ∈ R, = bxc
p ∀a ∈ Z, an ≡ a [n]

Exercice 51 [ 02370 ] [correction]

On note P l’ensemble des nombres premiers. Pour tout entier n > 0, on note Exercice 55 [ 03686 ] [correction]
vp (n) l’exposant de p dans la décomposition de n en facteurs premiers. On note On désire établir qu’il existe une infinité de nombres premiers de la forme 4n + 1.
bxc la partie entière de x. On note π(x) le nombre de nombres premiers au plus Pour cela on raisonne par l’absurde et on suppose que ceux-ci sont en nombre fini
égaux à x. et on les numérote pour former la liste p1 , . . . , pr .
+∞
Pjnk On pose alors
a) Montrer que vp (n!) = pk
. N = (2p1 . . . pr )2 + 1
! k=1
2n a) On suppose qu’il existe un facteur premier q de N de la forme 4n + 3.
 ln(2n) 
Q
b) Montrer que divise p ln p . Etablir
n p∈P;p62n
! (2p1 . . . pr )(q−1) ≡ −1 [q]
2n
c) Montrer que 6 (2n)π(2n) . b) Conclure en exploitant le petit théorème de Fermat.
n
d) Montrer que lnxx = O(π(x)) quand x → +∞

Petit théorème de Fermat

Exercice 52 [ 01222 ] [correction]
Soit p un nombre premier.
a) Montrer !
p
∀k ∈ {1, 2, . . . , p − 1} , p |
k
b) En déduire que
∀n ∈ Z, np ≡ n [p]

Exercice 53 [ 03636 ] [correction]

Soit n > 2 un entier. On suppose
∀a ∈ {1, . . . , n − 1} , an−1 ≡ 1 [n]

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

[[Link] édité le 1er septembre 2014 Corrections 6

Corrections Exercice 3 : [énoncé]

Raisonnons par récurrence sur n > 1.
Exercice 1 : [énoncé] Pour n = 1 : ok
a) x = 1 n’est pas solution. Pour x 6= 1 : Supposons la propriété établie au rang n.
x − 1 | x + 3 ⇔ x−1x+3 4
= 1 + x−1 ∈ Z ⇔ x − 1 ∈ Div(4) = {1, 2, 4, −1, −2, −4} Par l’absurde supposons que A soit une partie de n + 2 entiers distincts tous
Ainsi S = {2, 3, 5, 0, −1, −3}. inférieurs ou égaux à 2n + 2. Indexons les éléments de A par ordre croissant :
b) x = −2 n’est pas solution. Pour x 6= −2 : A = {a0 , . . . , an , an+1 } avec ai < ai+1 .
2 Si an 6 2n alors l’ensemble {a0 , . . . , a2n } est contraire à l’hypothèse de récurrence.
x + 2 | x2 + 2 ⇔ xx+2 +2 6
= x − 2 + x+2 ∈ Z ⇔ x + 2 ∈ Div(6) =
Sinon an = 2n + 1 et an+1 = 2n + 2. Puisque n + 1 | an+1 , nécessairement
{1, 2, 3, 6, −1, −2, −3, −6}.
n+1∈ / {a0 , . . . , an−1 }
Ainsi S = {−1, 0, 1, 4, −3, −4, −5, −8}.
Considérons alors {a0 , . . . , an−1 } ∪ {n + 1}. C’est une partie à n + 1 éléments tous
inférieur ou égaux à 2n. Par hypothèse de récurrence, l’un d’eux divise l’autre et il
en est donc de même dans {a0 , . . . , an−1 , an+1 }. Ceci induit une contradiction
Exercice 2 : [énoncé]
avec l’hypothèse de départ.
a) On a
Récurrence établie.
xy = 3x + 2y ⇔ (x − 2)(y − 3) = 6
En détaillant les diviseurs de 6 possibles, on obtient
Exercice 4 : [énoncé]
S = {(3, 9), (4, 6), (5, 5), (8, 4), (1, −3), (0, 0), (−1, 1), (−4, 2)} En associant dans P 2 = P × P chaque diviseur d avec celui qui lui est conjugué
n/d, on obtient un produit de N termes égaux à n. Ainsi
b) Pour x, y ∈ Z? ,
1 1 1 P 2 = nN
+ = ⇔ 5x + 5y = xy ⇔ (x − 5)(y − 5) = 25
x y 5
En détaillant les diviseurs de 25 possibles, on obtient Exercice 5 : [énoncé]
a − 1 = bq + r avec 0 6 r < b.
S = {(6, 30), (10, 10), (30, 6), (4, −20), (−20, 4)} abn − 1 = (bq + r + 1)bn − 1 = qbn+1 + bn (r + 1) − 1.
Or 0 6 bn (r + 1) − 1 < bn+1 donc la relation ci-dessus est la division euclidienne
c) On a de abn − 1 par bn+1 .
x2 − y 2 − 4x − 2y = 5 ⇔ (x − 2)2 − (y + 1)2 = 8 Le quotient de celle-ci est donc q.
et donc
x2 − y 2 − 4x − 2y = 5 ⇔ (x − y − 3)(x + y − 1) = 8
Exercice 6 : [énoncé]
En détaillant les diviseurs de 8 possibles et sachant a) On aa = bq + r avec 0 6 r < b.
a+b

(
x = +2 2a − 1 = 2bq+r − 1 = 2bq+r − 2r + 2r − 1 = (2b − 1)(1 + 2b + · · · + 2b(q−1) )2r + 2r − 1
x−y−3=a

⇔ 2
x+y−1=b y = b − a − 1
 avec 0 6 2r − 1 < 2b − 1.
2 b) Posons a0 = a, a1 = b et définissons a2 , . . . , am comme par l’algorithme
d’Euclide avec am = pgcd(am−1 , am−2 ).
on obtient
On a
S = {(5, 0), (5, −2), (−1, 0), (−1, −2)}
pgcd(2a −1, 2b −1) = pgcd(2a0 −1, 2a1 −1) = pgcd(2a1 −1, 2a2 −1) = . . . = pgcd(2am −1, 20 −1

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

[[Link] édité le 1er septembre 2014 Corrections 7

Exercice 7 : [énoncé] Exercice 9 : [énoncé]

a) Par récurrence sur n ∈ N? : (⇒) Supposons d = au + bv avec u, v ∈ Z.
Pour n = 1 : ϕ2 ϕ0 − ϕ21 = 0 − 1 = −1 : ok. pgcd(a, b) | a et pgcd(a, b) | b donc pgcd(a, b) | au + bv = d.
Supposons la propriété établie au rang n > 1. (⇐) Supposons pgcd(a, b) | d. On peut écrire d = kpgcd(a, b) avec k ∈ Z.
Par l’égalité de Bézout, il existe u0 , v0 ∈ Z tels que
ϕn+2 ϕn −ϕ2n+1 = (ϕn +ϕn+1 )ϕn −ϕn+1 (ϕn +ϕn−1 ) = ϕ2n −ϕn+1 ϕn−1 = −(−1)n = (−1)n+1
HR
au0 + bv0 = pgcd(a, b)
Récurrence établie.
et on a alors
b) Par l’égalité de Bézout on obtient que ϕn ∧ ϕn+1 = 1 puisque la relation
d = au + bv
précédente permet d’écrire uϕn + vϕn+1 = 1 avec u, v ∈ Z.
c) Par récurrence sur m ∈ N? avec u = ku0 et v = kv0 ∈ Z
Pour m = 1 : ϕn+1 = ϕ1 ϕn+1 + ϕ0 ϕn car ϕ1 = 1 et ϕ0 = 0.
Supposons la propriété établie au rang n > 1
Exercice 10 : [énoncé]
ϕn+m+1 = ϕ(n+1)+m = ϕm ϕn+2 +ϕm−1 ϕn+1 = ϕm ϕn+1 +ϕm ϕn +ϕm−1 ϕn+1 = ϕm+1 ϕn+1
3 ×+ϕ ϕn4) − 2 × (3n + 3) = 6 donc pgcd(2n + 4, 3n + 3) | 6.
(2nm+
HR

Récurrence établie.
d) Exercice 11 : [énoncé]
Si le système possède une solution alors d | m est une condition nécessaire.
pgcd(ϕm+n , ϕn ) = pgcd(ϕm ϕn−1 +ϕm−1 ϕn , ϕn ) = pgcd(ϕm ϕn−1 , ϕn ) = pgcd(ϕm , ϕn ) Inversement si d | m alors x = d et y = m donne un couple (x, y) ∈ N2 solution.

car ϕn ∧ ϕn−1 = 1.
Par récurrence on obtient que
Exercice 12 : [énoncé]
∀q ∈ N : ϕm ∧ ϕn = ϕm+qn ∧ ϕn Soit (x, y) ∈ N2 un couple solution. Posons δ = pgcd(x, y).
On peut écrire
On en déduit alors pgcd(ϕm , ϕn ) = pgcd(ϕn , ϕr ) car on peut écrire m = nq + r x = δx0 et y = δy 0 avec x0 ∧ y 0 = 1
avec q ∈ N. L’équation devient :
e) Suivons l’algorithme d’Euclide calculant pgcd(m, n) :
a0 = m, a1 = n, a0 = a1 q1 + a2 , a1 = a2 q2 + a3 ,..., ap−1 = ap qp + 0 avec 1 + x0 y 0 = x0 + y 0 ⇔ (x0 − 1)(y 0 − 1) = 0 ⇔ x0 = 1 ou y 0 = 1
ap = pgcd(m, n)
Or pgcd(ϕn , ϕm ) = pgcd(ϕa0 , ϕa1 ) = pgcd(ϕa1 , ϕa2 ) = . . . = pgcd(ϕap , ϕ0 ) = ϕap Ainsi (x, y) est de la forme (δ, δk) ou (δk, δ) avec k ∈ N.
car ϕ0 = 0. Inversement ces couples sont solutions.
Ainsi pgcd(ϕm , ϕn ) = ϕpgcd(m,n) .

Exercice 13 : [énoncé]
Exercice 8 : [énoncé] a) Soit (x, y) solution. pgcd(x, y) = 5 donc x = 5x0 et y = 5y 0 avec x0 , y 0 ∈ N
a) pgcd(a, b) = 3 et 3a − 4b = 3. premiers entre eux.
b) pgcd(a, b) = 1 et 11b − 8a = 1 ppcm(x, y) = 5x0 y 0 = 60 donc x0 y 0 = 12 d’où
c) pgcd(a, b) = 15 et 2a − 5b = 15 (x0 , y 0 ) ∈ {(1, 12), (2, 6), (3, 4), (4, 3), (6, 2), (12, 1)}.
Les couples (2, 6) et (6, 2) sont à éliminer car 2 et 6 ne sont pas premiers entre eux.
Finalement (x, y) ∈ {(5, 60), (15, 20), (20, 15), (60, 5)}.

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

[[Link] édité le 1er septembre 2014 Corrections 8
!
Inversement : ok. Finalement S = {(5, 60), (15, 20), (20, 15), (60, 5)}. 2n + 1
b) Soit (x, y) solution. pgcd(x, y) = 10 donc x = 10x0 et y = 10y 0 avec x0 , y 0 ∈ N Puisque ∈ Z, on a
n+1
premiers entre eux.
x + y = 10(x0 + y 0 ) = 100 donc x0 + y 0 = 10.
!
2n
Sachant x0 ∧ y 0 = 1, il reste (x0 , y 0 ) ∈ {(1, 9), (3, 7), (7, 3), (9, 1)} puis (n + 1) | (2n + 1)
(x, y) ∈ {(10, 90), (30, 70), (70, 30), (90, 10)}. n
Inversement : ok. Finalement S = {(10, 90), (30, 70), (70, 30), (90, 10)}.
or (n + 1) ∧ (2n + 1) = 1 donc
!
Exercice 14 : [énoncé] 2n
(n + 1) |
Posons d = pgcd(a, a + b). n
On a d | a et d | (a + b) alors d | b = (a + b) − a donc d | pgcd(a, b) = 1 puis d = 1.
De même pgcd(b, a + b) = 1. Ainsi a ∧ (a + b) = b ∧ (a + b) = 1 et par suite
ab ∧ (a + b) = 1. Exercice 18 : [énoncé]
Posons d = pgcd(a, bc) et δ = pgcd(a, c).
On δ | a et δ | c donc δ | bc puis δ | d.
Exercice 15 : [énoncé] Inversement d | a et d | bc.
a) pgcd(a, a + b) = pgcd(a, b) et pgcd(b, a + b) = pgcd(a, b) = 1. Or d ∧ b = 1 car d | a et a ∧ b = 1. Donc d | c puis d | δ.
Ainsi (a + b) ∧ a = 1 et (a + b) ∧ b = 1 donc (a + b) ∧ ab = 1. Par double divisibilité d = δ.
b) Posons δ = pgcd(a, b). On peut écrire a = δa0 et b = δb0 avec a0 ∧ b0 = 1.
pgcd(a + b, ppcm(a, b)) = δpgcd(a0 + b0 , ppcm(a0 , b0 )) = δ
Exercice 19 : [énoncé]
a) Théorème de Bézout.
Exercice 16 : [énoncé]
b) Soit (u, v) ∈ Z2 un couple solution. On a au + bv = 1 = au0 + bv0 donc
a) n2 + n = n(n + 1).
a(u − u0 ) = b(v0 − v)
1 × (2n + 1) − 2 × n = 1 donc (2n + 1) ∧ n = 1.
On a a | b(v0 − v) or a ∧ b = 1 donc a | v0 − v. Ainsi ∃k ∈ Z tel que v = v0 − ka et
2 × (n + 1) − 1 × (2n + 1) = 1 donc (2n + 1) ∧ (n + 1) = 1
alors a(u − u0 ) = b(v0 − v) donne a(u − u0 ) = abk puis u = u0 + kb (sachant
Par produit (2n + 1) ∧ (n2 + n) = 1.
a 6= 0).
b) 3n2 + 2n = n(3n + 2).
c) Inversement les couples de la forme ci-dessus sont solutions.
1 × (n + 1) − 1 × n = 1 donc n ∧ (n + 1) = 1.
3 × (n + 1) − 1 × (3n + 2) = 1 donc (3n + 2) ∧ (n + 1) = 1.
Par produit (3n2 + 2n) ∧ (n + 1) = 1.
Exercice 20 : [énoncé]
a) Unicité : Si (an , bn ) et (αn , βn ) sont solutions alors
Exercice 17 : [énoncé] √ √
an + bn 2 = αn + βn 2
2 × (n + 1) − 1 × (2n + 1) = 1 donc (n + 1) ∧ (2n + 1) = 1.
On a donc
! ! √
2n + 1 2n + 1 2n (bn − βn ) 2 = (αn − an )
=
n+1 n+1 n
Si bn 6= βn alors
donc √ αn − a
! ! 2= ∈Q
2n + 1 2n bn − β n
(n + 1) = (2n + 1)
n+1 n ce qui est absurde.

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

[[Link] édité le 1er septembre 2014 Corrections 9

On en déduit bn = βn puis an = αn Exercice 22 : [énoncé]

Existence : Par la formule du binôme Si k | a et ` | b alors k` | ab. Ainsi ϕ(div(a) × div(b)) ⊂ div(ab).
n
! Soit d ∈ div(ab). Posons k = pgcd(d, a) et ` = pgcd(d, b). On a k ∈ div(a),
√ X n √ k ` ∈ div(b) et k ∧ ` = 1 car a ∧ b = 1. Comme k | d, ` | d et k ∧ ` = 1 on a k` | d. De
(1 + 2)n = 2
k=0
k plus k = du + av et ` = du0 + bv donc k` = dU + abV d’où d | k` et finalement
d = k`. Ainsi ϕ(div(a) × div(b)) = div(ab).
En séparant les termes d’indices pairs de ceux d’indices impairs, on a Soit (k, `) ∈ div(a) × div(b) et (k 0 , `0 ) ∈ div(a) × div(b). Si ϕ(k, `) = ϕ(k 0 , `0 ) alors
√ √ k` = k 0 `0 .
(1 + 2)n = an + bn 2 Comme k | k 0 `0 et k ∧ `0 = 1 on a k | k 0 . De même k 0 | k donc k = k 0 . De même
` = `0 .
avec Ainsi ϕ est injective et finalement ϕ réalise une bijection de div(a) × div(b) vers
E(n/2) E((n−1)/2)
! !
X n X n div(ab).
an = 2p et bn = 2p
p=0
2p p=0
2p + 1

b) On a Exercice 23 : [énoncé]
√  √ 
a2n − 2b2n = (an + bn 2) an − bn 2 Par l’absurde, supposons que ai et aj (avec i, j ∈ {1, . . . , n + 1}) ne soient pas
premiers entre eux.
Or en reprenant les calculs qui précèdent Considérons d un diviseur premier commun à ai et aj . L’entier d est diviseur de
√ √ ai − aj donc de (i − j).n!.
(1 − 2)n = an − bn 2 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
donc √ √ divise 1.
a2n − 2b2n = (1 + 2)n (1 − 2)n = (−1)n C’est absurde.
c) La relation qui précède permet d’écrire

an u + bn v = 1 avec u, v ∈ Z Exercice 24 : [énoncé]

Notons 2p + 1 le premier nombre impair sommé. On a
On en déduit que an et bn sont premiers entre eux. n−1
X
N= (2k + 2p + 1) = n(n + 2p)
k=0
Exercice 21 : [énoncé]
Unicité : Si (d1 , d2 ) est solution alors pgcd(d, a) = pgcd(d1 d2 , a) avec n > 2 et n + 2p > 2. Ainsi N est composé.
Or d2 ∧ a = 1 car d2 | b et a ∧ b = 1, donc pgcd(d1 d2 , a) = pgcd(d1 , a) = d1 car
d1 | a.
Exercice 25 : [énoncé]
De même d2 = pgcd(d, b) d’où l’unicité.
a) 4n3 + 6n2 + 4n + 1 = (n + 1)4 − n4 = ((n + 1)2 − n2 )((n + 1)2 + n2 ) =
Existence : Posons d1 = pgcd(d, a) et d2 = pgcd(d, b). On a d1 | a et d2 | b.
(2n + 1)(2n2 + 2n + 1).
d1 | a et d2 | b donc d1 ∧ d2 = 1 car a ∧ b = 1.
Cet entier est composé pour n ∈ N? car 2n + 1 > 2 et 2n2 + 2n + 1 > 2.
d1 | d, d2 | d et d1 ∧ d2 = 1 donc d1 d2 | d.
b) n4 − n2 + 16 = (n2 + 4)2 − 9n2 = (n2 − 3n + 4)(n2 + 3n + 4).
Inversement : Par l’égalité de Bézout on peut écrire d1 = u1 d + v1 a et
De plus les équations n2 − 3n + 4 = 0, 1 ou − 1 et n2 + 3n + 4 = 0,1 ou − 1
d2 = u2 d + v2 b donc d | d1 d2 = U d + v1 v2 ab car d | ab.
n’ont pas de solutions car toutes de discriminant négatif. Par conséquent
n4 − n2 + 16 est composée.

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

[[Link] édité le 1er septembre 2014 Corrections 10

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

Considérons l’entier n! + 1. Celui-ci est divisible par un nombre premier p Supposons que ap − 1 premier.
inférieur à n! + 1. Comme ap − 1 = (a − 1)(1 + a + · · · + ap−1 ) on a a − 1 = 1 ou
Si ce nombre premier p est aussi inférieur à n alors il divise n! (car apparaît 1 + a + · · · + ap−1 = 1.
comme l’un des facteurs de ce produit) et donc il divise aussi 1 = (n! + 1) − n!. Or p > 2 et a 6= 0 donc 1 + a + · · · + ap−1 6= 1. Par conséquent a = 2.
Ceci est absurde et donc le nombre premier en question est au moins égal à n + 1. Montrons maintenant que p est premier.
Finalement, il est strictement compris entre n et n! + 2. Si d | p alors on peut écrire p = cd puis ap − 1 = (ad )c − 1.
Si d 6= p alors c > 2 puis par le résultat précédent on obtient ad = 2 puis d = 1.
Ainsi les seuls diviseurs de p sont 1 et lui-même.
Exercice 27 : [énoncé] Finalement p est premier.
Considérons les xk = 1001! + k avec 2 6 k 6 1001. Ce sont 1000 entiers
consécutifs.
Pour tout 2 6 k 6 1001, on a k | (1001)! donc k | xk avec 2 6 k < xk donc xk ∈
/ P. Exercice 31 : [énoncé]
On peut écrire
n = 2k (2p + 1)
Exercice 28 : [énoncé] On a alors
On peut factoriser an + 1 = b2p+1 − (−1)2p+1 = (b + 1)c
2
p − 1 = (p − 1)(p + 1) k
avec b = a2 .
p est impair donc les nombres p − 1 et p + 1 sont deux entiers pairs consécutifs, On en déduit que b + 1 | an + 1, or an + 1 est supposé premier et b + 1 > 1 donc
l’un est divisible par 2, l’autre par 4. Ainsi b + 1 = an + 1 puis n = 2k .

8 | p2 − 1
Exercice 32 : [énoncé]
Les entiers p − 1, p, p + 1 sont consécutifs, l’un est divisible par 3, ce ne peut être p
On peut écrire n = 2k (2p + 1) avec k, p ∈ N et l’enjeu est d’établir p = 0.
car p > 5 premier. Ainsi k k

3 | p2 − 1 Posons α = a2 et β = b2 . On a

Enfin, 3 et 8 étant premiers entre eux an + bn = α2p+1 + β 2p+1 = α2p+1 − (−β 2p+1 )

24 | p2 − 1 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 α 6 an et β 6 bn , le cas α + β = an + bn
Exercice 29 : [énoncé] entraîne
Si n = ab avec a, b ∈ N? alors α = an et β = bn
Puisque a > 2, l’égalité α = an = α2p+1 entraîne p = 0 et finalement n est une
2n − 1 = (2a − 1)(1 + 2a + · · · + 2a(b−1) ) puissance de 2.
donc 2a − 1 | 2n − 1 d’où 2a − 1 = 1 ou 2a − 1 = 2n − 1 ce qui implique a = 1 ou
a = n.
Exercice 33 : [énoncé]
Ainsi n ne possède que des diviseurs triviaux, il est premier.
a) n est impair, il n’est donc pas divisible par 2. Si tous les nombres premiers p
divisant n sont tels que p = 1 [4] alors n = 1 [4] et donc n ∈ /E

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

[[Link] édité le 1er septembre 2014 Corrections 11

b) Supposons qu’il n’y en ait qu’un nombre fini de nombres premiers p1 p2 . . . pn . Exercice 37 : [énoncé]
Considérons Supposons a2 | b2 .
n = 4p1 p2 . . . pn − 1 ∈ E Posons d = pgcd(a, b). On a d2 = pgcd(a, b)2 = pgcd(a2 , b2 ) = a2 donc d = |a| puis
a | b.
Il existe p ∈ P ∩ E tel que p | n mais p | p1 p2 . . . pn donc p | 1. Absurde.

Exercice 34 : [énoncé] Exercice 38 : [énoncé]

Par l’absurde, supposons qu’il n’y ait qu’un nombre fini de nombres premiers de On peut écrire x = pq avec p ∈ Z, q ∈ N? et p ∧ q = 1.
la forme 4n + 3. On peut introduire le nombre N égal au produit de ceux-ci. xn = k ∈ Z donne q n k = pn . p ∧ q = 1 donc pn ∧ q n = 1. Puisque q n | pn × 1 on a
Considérons alors l’entier 4N − 1. q n | 1 (par Gauss).
4N − 1 est impair donc 2 ne le divise pas. Par suite q n = 1 et donc q = 1 et x = p ∈ Z.
Si tous les facteurs premiers de 4N − 1 sont égaux à 1 modulo 4 alors
4N − 1 ≡ 1 [4] ce qui est absurde.
L’un au moins des facteurs premiers de 4N − 1 est alors de la forme 4n + 3 et Exercice 39 : [énoncé]
celui-ci apparaît donc dans le produit N . Ce facteur premier divise alors les Il existe u, v ∈ Z tel que mu + nv = 1.
nombres 4N − 1 et N , il divise donc −1, c’est absurde ! 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.
Puisque le nombre rationnel c possède une puissance entière, c ∈ Z.
Exercice 35 : [énoncé]
a) Quitte à échanger, supposons n < m.
On remarque que Exercice 40 : [énoncé]
m−n
(Fn − 1)2 = Fm − 1 Le nombre de côté du polygone construit est le plus petit entier k ∈ N? tel que
En développant cette relation par la formule du binôme, on parvient à une n | kp.
relation de la forme Posons δ = pgcd(n, p). On peut écrire n = δn0 et p = δp0 avec n0 ∧ p0 = 1.
Fm + vFn = 2 n | kp ⇔ n0 | kp0 i.e. n0 | k. Ainsi k = n0 = n/δ.
avec v ∈ Z car les coefficients binomiaux sont des entiers.
On en déduit que pgcd(Fn , Fm ) = 1 ou 2.
Exercice 41 : [énoncé]
Puisque Fn et Fm ne sont pas tous deux pairs, ils sont premiers entre eux.
Supposons x = p/q une racine rationnelle de l’équation (E) avec p et q premiers
b) Les Fn sont en nombre infini et possèdent des facteurs premiers distincts, il
entre eux.
existe donc une infinité de nombres premiers.
En réduisant au même dénominateur, on obtient

pn + an−1 qpn−1 + · · · + a1 pq n−1 + a0 q n = 0

Exercice 36 : [énoncé]
(⇐) ok √ √ Puisque q divise an−1 qpn−1 + · · · + a1 pq n−1 + a0 q n , on obtient que q divise pn .
(⇒) Si n ∈ Q alors on peut écrire n = pq avec p ∧ q = 1. Or p et q sont premiers entre eux donc nécessairement q = 1 et donc x = p ∈ Z.
On a alors q 2 n = p2 donc n | p2 Ainsi les racines rationnelles de (E) sont entières.
De plus q 2 n = p2 et p2 ∧ q 2 = 1 donne p2 | n.
Par double divisibilité n = p2 . √ √
ni 2, ni 3 ne sont des carrés d’un entier, donc 2 ∈/ Q et 3 ∈
/ Q. Exercice 42 :√[énoncé]
a) Supposons 6 = p/q avec p ∧ q = 1. On a 6q 2 = p2 donc p pair, p = 2k. On

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

[[Link] édité le 1er septembre 2014 Corrections 12

obtient alors 3q 2 = 2k 2 et donc q est pair. Absurde car p et q sont premiers entre Sachant qu’il est connu que
n
eux. X 1
b) Par ∼ ln n
√ développement √ selon la formule du binôme de Newton d
k=1
(a + b)n = αk + βk b avec αk , βk ∈ Z.
√ √ on obtient
n n
 n 
k k
P P P n
c) a + b racine de P = ak X donne ak αk = ak β b. 1X
k=0 k=0 k=0 d(k) ∼ ln n
√ Pn n
P n
L’irrationalité de b entraîne ak αk = ak βk = 0 ce qui permet de justifier k=1

√ k=0 k=0
P (a − b) = 0. √ √
d) Posons Q = (X − a + b)(X − a − b) = X 2 − 2aX + a2 − b ∈ Z [X]. Exercice 44 : [énoncé]
Par division euclidienne P = QS + T avec deg T < 2. Or en posant cette division (⇐) clair
euclidienne,
√ √on peut affirmer que S, T ∈ Z [X] avec P, Q ∈ Z [X] et Q unitaire. (⇒) n est divisible par un nombre premier p et ne peut lui être égal. On peut
a + b, a − b racine de P entraîne √ T = 0 et donc P = QS avec Q, S√∈ Z [X]. En donc écrire n = pd avec 1 < d < n. Si d est premier alors on obtient la seconde
dérivant P 0 = Q0 S + QS 0 et a + b entraîne racine de P 0 donne a + b racine de forme. Sinon, il ne peut qu’être divisible par p (car q | d implique que n est un
S. On peut alors comme ci-dessus justifier S = QR avec R ∈ Z [X] et conclure. multiple de pqd car n est produit de ses diviseurs non triviaux). Le nombre d est
alors de la forme d = pk . k = 1 et k > 3 sont à exclure puisque n est le produit de
ses diviseurs non triviaux. Il reste d = p2 et alors n = p3
Exercice 43 : [énoncé]
On peut écrire
n
X n X
X Exercice 45 : [énoncé]
d(k) = 1 Soit d ∈ Div(pα ) ∩ N. Notons β la plus grande puissance de p telle que pβ | d.
k=1 k=1 d|k On peut écrire d = pβ k avec p 6 |k.
et en permutant les deux sommes Puisque p 6 |k et p ∈ P on a p ∧ k = 1. Or k | pα × 1 donc, par Gauss : k | 1.
Par suite d = pβ avec β ∈ N. De plus d | pα donc pβ 6 pα puis β 6 α.
n
X n X
X Inversement : ok.
d(k) = 1
k=1 d=1 k∈Ad

avec Ad l’ensemble des multiples de d qui sont inférieurs à n. On a évidemment Exercice 46 : [énoncé]
N
pβkk avec ∀1 6 k 6 N, 0 6 βk 6 αk .
Q
Les diviseurs positifs sont les d =
CardAd = E(n/d) k=1
Le choix des βk conduisant à des diviseurs distincts, il y a exactement
et donc QN
n
X n
X n (αk + 1) diviseurs positifs de n.
d(k) = E k=1
d
k=1 d=1

Puisque Exercice 47 : [énoncé]

x − 1 < E (x) 6 x Soit d ∈ N diviseur de n.
on obtient l’encadrement Tout diviseur premier de d est aussi diviseur de n et c’est donc l’un des p1 , . . . , pN .
N
pβi i avec βi ∈ N.
Q
n
! n n Par suite, on peut écrire d =
X 1 X X 1 i=1
n −1 6 d(k) 6n
d=1
d
k=1 d=1
d pβi i | d donc pβi i | n d’où βi 6 αi .

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

[[Link] édité le 1er septembre 2014 Corrections 13

N
La droite joignant nos deux couples peut être paramétrée par
pβi i avec pour tout i ∈ {1, . . . , N }, 0 6 βi 6 αi .
Q
Ainsi d est de la forme d =
i=1 (
Inversement de tels nombres sont bien diviseurs de n. x = x00 + λ(x0 − x00 )
Il y a autant de nombres de cette forme distincts que de choix pour les avec λ ∈ R
y = y00 + λ(y0 − y00 )
N
Q
β1 , . . . , βN .Pour βi , il y a αi + 1 choix possibles, au total d(n) = (αi + 1).
i=1 Cette droite coupe le cercle en (x0 , y0 ) pour λ = 1 et recoupe encore celui-ci en
De plus (x1 , y1 ) obtenu pour
(x0 )2 + (y00 )2 − N 2
    
α2
α1 X αN α1 α2 αN
X X X X X λ= 0
σ(n) = ... pβ1 1 pβ2 2 . . . pβNN =  pβ1 1   pβ2 2  . . .  pβNN  D2
β1 =0 β2 =0 βN =0 β1 =0 β2 =0 βN =0 Puisque
d1
Par sommation géométrique D2 = N 2 − 2(x0 x00 + y0 y00 ) + (x00 )2 + (y00 )2 =
d0
N
Y pαi +1 − 1
i avec d1 ∈ N? et d1 < d0 car D2 < 1.
σ(n) =
i=1
pi − 1 Le nombre λ est donc de la forme d0 k/d1 avec k entier et les coordonnées (x1 , y1 )
sont alors de la forme

Exercice 48 : [énoncé] x1 = p1 /d1 et y1 = q1 /d1 avec p1 , q1 ∈ Z et d1 ∈ N? , d1 < d0

α+1
a) Div(pα ) ∩ N = 1, p, p2 , . . . , pα donc σ(pα ) = p p−1−1 .

Si d1 = 1, le processus s’arrête, sinon il suffit de répéter l’opération jusqu’à
b) Soit d ∈ Div(ab) ∩ N. Posons d1 = pgcd(d, a) et d2 = pgcd(d, b).
obtention d’un couple entier.
On a d1 ∈ Div(a) ∩ N et d2 ∈ Div(b) ∩ N.
Puisque a ∧ b = 1 on a d1 ∧ d2 = 1. Or d1 | d et d2 | d donc d1 d2 | d.
d1 = du1 + av1 et d2 = du2 + bv2 donc d1 d2 = dk + abv1 v2 d’où d | d1 d2 .
Finalement d = d1 d2 . Exercice 50 : [énoncé]
Supposons d = δ1 δ2 avec δ1 ∈ Div(a) ∩ N et δ2 ∈ Div(b) ∩ N. a) v2 (1000!) = 500 + v2 (500!) car 1000! = 2500 × 500! × k avec k produit de
On a d1 | δ1 δ2 et d1 ∧ δ2 = 1 donc d1 | δ1 et de même δ1 | d1 puis d1 = δ1 . De nombres impairs.
même d2 = δ2 . ! ! v2 (1000!) = 500 + 250 + 125 + 62 + 31 + 15 + 7 + 3 + 1 = 994.
P P P P P b) En isolant les multiples de p dans le produit décrivant p!, on obtient
c) σ(ab) = d= d1 d2 = d1 db = σ(a)σ(b).
d|ab d1 |a d2 |b d1 |a d2 |b
    
n n
N α
pi i+1 −1
vp (n!) = + vp !
d) Si n = pα 1
. . . pα N
alors σ(n) =
Q p p
1 N pi −1 .
i=1
puis      
n bn/pc bn/pc
Exercice 49 : [énoncé] vp (n!) = + + vp !
p p p
Si le couple (x0 , y0 ) est entier la conclusion est entendue.
or
Sinon, on peut écrire 
bpxc

= bxc
x0 = p0 /d0 et y0 = q0 /d0 avec p0 , q0 ∈ Z et d0 ∈ N\ {0, 1} p

Considérons alors un couple entier (x00 , y00 ) obtenu par arrondi de (x0 , y0 ). On a avec x = n/p2 donne    
bn/pc n
2
D = (x0 − x00 )2 + (y0 − y00 )2 6 1/4 + 1/4 = 2
p p

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

[[Link] édité le 1er septembre 2014 Corrections 14

puis finalement       Notons qu’en fait ce produit désigne

n n n
vp (n!) = + 2 + ··· + k ppcm(1, 2, . . . , 2n)
p p p
avec   c) On a
ln n
k=
!
2n
 ln(2n)  ln(2n)
ln p
Y Y Y
6 p ln p 6 p ln p 6 (2n) = (2n)π(2n)
n p∈P;p62n p∈P;p62n p∈P;p62n

Exercice 51 : [énoncé] d) En passant au logarithme :

 
a) Pour k suffisamment grand n/pk = 0, la somme évoquée existe donc car elle 2n
X n
X
ne comporte qu’un nombre fini de termes non nuls. n! = 1 × 2 × . . .× n, parmi les ln k − 2 ln k 6 π(2n) ln(2n)
entiers allant de 1 à n, il y en a exactement bn/pc divisibles par p, n/p2 k=1 k=1
divisibles par p2 , etc. . . donc A l’aide d’une comparaison intégrale on obtient
+∞   Z n n Z (n+1)
X n X
vp (n!) = ln(t) dt 6 ln k 6 ln(t) dt
pk 1 1
k=1 k=1

b) On a donc
! n
X
2n (2n)! n ln n − n + 1 6 ln k 6 (n + 1) ln(n + 1) − n
=
n (n!)2 k=1
donc
n
Pour tout p ∈ P, X
  ∞     ln k = n ln n − n + O(ln n)
(2n)! X 2n n
vp = −2 k k=1
(n!)2 pk p
k=1 Par suite
or b2xc − 2 bxc = 0 ou 1 donc 2n
X n
X
ln k − 2 ln k = 2n ln(2n) − 2n − 2(n ln n − n) + O(ln n)
∞      
X 2n n  ?
 k
 ln(2n) k=1 k=1
−2 k 6 Card k ∈ N / 2n/p > 0 6
pk p ln p puis
k=1
2n
X n
X
! ln k − 2 ln k ∼ ln(2)(2n)
2n (2n)!
De plus les nombres premiers diviseurs de = (n!)2 sont diviseurs d’un entier k=1 k=1
n On en déduit
inférieur à 2n (lemme d’Euclide) et sont donc eux-mêmes inférieur à 2n. Il en 2n
= O(π(2n))
découle ! ln 2n
2n Ajoutons
Y  ln(2n) 
| p ln p x 2 bx/2c
n p∈P;p62n ∼
ln x ln 2 bx/2c
car toutes
! les puissances de nombres premiers intervenant dans la décomposition par calculs et π(x) ∼ π(2 bx/2c) car π(x) et π(2 bx/2c) ne différent qu’au plus
2n
 ln(2n) 
de divisent
Q
p ln p . d’une unité et π(x) → +∞.
n p∈P;p62n Finalement, une certaine satisfaction.

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

[[Link] édité le 1er septembre 2014 Corrections 15

Exercice 52 : [énoncé] Soit a ∈ Z. Considérons i ∈ {1, . . . , r}.

a) On a ! ! Si pi ne divise pas a, le petit théorème de Fermat assure api −1 ≡ 1 [pi ].
p p p−1 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 ].
k k k−1
Enfin, chaque pi divisant an − a et les pi étant deux à deux premiers entre eux,
donc ! ! n = p1 . . . pr divise an − a et finalement an ≡ a [n] .
p p−1 La réciproque de ce résultat est vraie.
k =p
k k−1 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
p les nombres de Carmichael. Le plus petit d’entre eux est 561, le suivant 1105.
Par suite p | k .
k
!
p
Or p est premier et k < p donc k ∧ p = 1 puis p | en vertu du théorème de Exercice 55 : [énoncé]
k
a) Puisque q divise N , on a
Gauss.
b) Par récurrence finie sur n ∈ {0, 1, . . . , p − 1} (2p1 . . . pr )2 ≡ −1 [q]
Pour n = 0 : ok
Supposons la propriété établie au rang n ∈ {0, 1, . . . , p − 2} On peut écrire le nombre premier q sous la forme 4n + 3 et alors
Par la formule du binôme 2n+1
(2p1 . . . pr )(q−1) ≡ (2p1 . . . pr )2 ≡ (−1)2n+1 ≡ −1

p−1
! [q]
p p
X p
(n + 1) = n + nk + 1 ≡ n + 1 [p]
k b) Par le petit théorème de Fermat, on a aussi
k=1

car pour 1 6 k 6 p − 1. ! (2p1 . . . pr )(q−1) ≡ 1 [q]

p
≡0 [p] et puisque 1 et −1 ne sont pas congrus modulo q, on obtient une absurdité.
k
La décomposition en facteurs premiers de N , ne fait donc intervenir aucun
Récurrence établie. nombre premier de la forme 4n + 3. Les facteurs premiers de N ne peuvent donc
Pour tout n ∈ Z, il existe r ∈ {0, 1, . . . , p − 1} tel que n ≡ r [p] et qu’être 2 et ceux de la forme 4n + 1. Ceux-ci divisent alors 2p1 . . . pr et donc, par
opérations, ils divisent aussi 1.
np ≡ r p ≡ r ≡ n [p] C’est absurde.
Notons qu’on peut démontrer, plus simplement, qu’il existe aussi une infinité de
nombres premiers de la forme 4n + 3.
Exercice 53 : [énoncé]
Pour tout a ∈ {1, . . . , n − 1}, a est premier avec n. En effet, 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 54 : [énoncé]
Par hypothèse, on peut écrire n = p1 p2 . . . pr avec p1 , . . . , pr nombres premiers
deux à deux distincts.

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