[[Link]

fr] édité le 6 août 2013 Enoncés 1

Arithmétique dans Z Exercice 8

Montrer
[ 01194 ] [correction]

7 | x et 7 | y ⇔ 7 | x2 + y 2
Divisibilité
Exercice 1 [ 01187 ] [correction] Exercice 9 [ 03679 ] [correction]
Résoudre dans Z les équations suivantes : Montrer que si n est entier impair alors
a) x − 1 | x + 3 b) x + 2 | x2 + 2.
n2 ≡ 1 [8]

Exercice 2 [ 01188 ] [correction]

Résoudre dans Z2 les équations suivantes : Exercice 10 [ 03680 ] [correction]
a) xy = 3x + 2y b) x1 + y1 = 15 c) x2 − y 2 − 4x − 2y = 5. Soient λ, a, b ∈ Z et m ∈ N? . On suppose λ et m premiers entre eux. Montrer

a≡b [m] ⇔ λa ≡ λb [m]

Exercice 3 [ 01189 ] [correction]
Soient a ∈ Z et b ∈ N? , on note q le quotient de la division euclidienne de a − 1
par b. PGCD et PPCM
Déterminer pour tout n ∈ N, le quotient de la division euclidienne de (abn − 1)
par bn+1 . Exercice 11 [ 01195 ] [correction]
Déterminer le pgcd et les coefficients de l’égalité de Bézout (1730-1783) des entiers
a et b suivants :
Calcul en congruence a) a = 33 et b = 24 b) a = 37 et b = 27 c) a = 270 et b = 105.

Exercice 4 [ 01190 ] [correction]

Montrer que 11 | 2123 + 3121 . Exercice 12 [ 01196 ] [correction]
Soient a, b, d ∈ Z. Montrer l’équivalence :

Exercice 5 [ 01191 ] [correction] (∃u, v ∈ Z, au + bv = d) ⇔ pgcd(a, b) | d

Quel est le reste de la division euclidienne de 12344321 + 43211234 par 7 ?

Exercice 13 [ 01197 ] [correction]

Exercice 6 [ 01192 ] [correction] Montrer que le pgcd de 2n + 4 et 3n + 3 ne peut être que 1, 2, 3 ou 6.
Montrer que pour tout n ∈ N :

a) 6 | 5n3 + n b) 7 | 32n+1 + 2n+2 c) 5 | 22n+1 + 32n+1

Exercice 14 [ 01198 ] [correction]
d) 11 | 38n × 54 + 56n × 73 e) 9 | 4n − 1 − 3n f) 152 | 16n − 1 − 15n
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.
b) Montrer que pgcd(2a − 1, 2b − 1) = 2pgcd(a,b) − 1.
Exercice 7 [ 01193 ] [correction]
Trouver les entiers n ∈ Z tel que 10 | n2 + (n + 1)2 + (n + 3)2 .

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

[[Link] édité le 6 août 2013 Enoncés 2

Exercice 15 [ 01199 ] [correction] Exercice 21 [ 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.
2n
En déduire que n + 1 |
(
pgcd(x, y) = d .
n
ppcm(x, y) = m

possède un couple (x, y) ∈ N2 solution. Exercice 22 [ 01206 ] [correction]

Soient a et b premiers entre eux et c ∈ Z.
Montrer que pgcd(a, bc) = pgcd(a, c).
Exercice 16 [ 01200 ] [correction]
Résoudre dans N2 l’équation :
Exercice 23 [ 01207 ] [correction]
pgcd(x, y) + ppcm(x, y) = x + y 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.
a) Justifier l’existence d’au moins un couple solution (u0 , v0 ).
Exercice 17 [ 01201 ] [correction] b) Montrer que tout autre couple solution est de la forme (u0 + kb, v0 − ka) avec
Résoudre dans N2 les systèmes : k ∈ Z.
( ( c) Conclure.
pgcd(x, y) = 5 x + y = 100
a) b)
ppcm(x, y) = 60 pgcd(x, y) = 10
Exercice 24 [ 01208 ] [correction]
a) Pour n ∈ N, montrer qu’il existe un couple unique (an , bn ) ∈ N2 tel que
Nombres premiers entre eux √ √
(1 + 2)n = an + bn 2
Exercice 18 [ 01202 ] [correction]
b) Calculer a2n − 2b2n .
Soient a et b premiers entre eux.
c) En déduire que an et bn sont premiers entre eux.
Montrer que a ∧ (a + b) = b ∧ (a + b) = 1 puis (a + b) ∧ ab = 1.

Exercice 25 [ 01209 ] [correction]

Exercice 19 [ 01203 ] [correction] Soient a et b deux entiers relatifs premiers entre eux et d ∈ N un diviseur de ab.
Soient a, b ∈ Z. Montrer
a) On suppose a ∧ b = 1. Montrer que (a + b) ∧ ab = 1. ∃!(d1 , d2 ) ∈ N2 , d = d1 d2 , d1 | a et d2 | b
b) On revient au cas général. Calculer pgcd(a + b, ppcm(a, b)).

Exercice 26 [ 01210 ] [correction]

Exercice 20 [ 01204 ] [correction] On note div(n) l’ensemble des diviseurs positifs d’un entier n ∈ Z.
Montrer que pour tout n ∈ N? on a : Soient a, b ∈ Z premiers entre eux et ϕ : div(a) × div(b) → N définie par
ϕ(k, `) = k`.
a) (n2 + n) ∧ (2n + 1) = 1 b) (3n2 + 2n) ∧ (n + 1) = 1 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 6 août 2013 Enoncés 3

Exercice 27 [ 01211 ] [correction] Exercice 32 [ 03624 ] [correction]

Soient a et b deux entiers relatifs tels que a2 | b2 . Montrer que a | b. Soit n ∈ N. Montrer que les entiers

ai = i.n! + 1

Exercice 28 [ 01212 ] [correction] pour i ∈ {1, . . . , n + 1} sont deux à deux premiers entre eux.
Soit x ∈ Q. On suppose qu’il existe n ∈ N? tel que xn ∈ Z. Montrer que x ∈ Z.

Exercice 33 [ 03669 ] [correction]

On étudie l’équation algébrique
Exercice 29 [ 01213 ] [correction]
Soient a, b ∈ N? . On suppose qu’il existe m, n premiers entre eux tels que am = bn . (E) : xn + an−1 xn−1 + · · · + a1 x + a0 = 0
Montrer qu’il existe c ∈ N? tel que a = cn et b = cm .
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.
Exercice 30 [ 01214 ] [correction]
On divise un cercle en n arcs égaux et on joint les points de division de p en p Systèmes chinois
jusqu’à ce qu’on revienne au point de départ. Quel est le nombre de côtés du
polygone construit ?
Exercice 34 [ 01216 ] [correction]
Résoudre le système : (
x=2 [10]
Exercice 31 [ 01215 ] [correction]
x=5 [13]
On considère la suite (ϕn )n∈N définie par

ϕ0 = 0, ϕ1 = 1 et ∀n ∈ N, ϕn+2 = ϕn+1 + ϕn
Exercice 35 [ 01217 ] [correction]
a) Montrer Soient a, b, a0 , b0 ∈ Z avec b et b0 premiers entre eux.
Montrer que le système
∀n ∈ N? , ϕn+1 ϕn−1 − ϕ2n = (−1)n (
x = a [b]
b) En déduire x = a0 [b0 ]
∀n ∈ N? , ϕn ∧ ϕn+1 = 1
possède des solutions et que celles-ci sont congrues entres elles modulo bb0 .
c) Montrer
∀n ∈ N, ∀m ∈ N? , ϕn+m = ϕm ϕn+1 + ϕm−1 ϕn
Exercice 36 [ 01218 ] [correction]
d) En déduire Une bande de 17 pirates dispose d’un butin composé de N pièces d’or d’égale
∀m, n ∈ N? , pgcd(ϕn , ϕm+n ) = pgcd(ϕn , ϕm ) valeur. Ils décident de se le partager également et de donner le reste au cuisinier
puis pgcd(ϕm , ϕn ) = pgcd(ϕn , ϕr ) où r est le reste de la division euclidienne de m (non pirate). Celui ci reçoit 3 pièces. Mais une rixe éclate et 6 pirates sont tués.
par n. Tout le butin est reconstitué et partagé entre les survivants comme
e) Conclure précédemment ; le cuisinier reçoit alors 4 pièces. Dans un naufrage ultérieur, seul
le butin, 6 pirates et le cuisinier sont sauvés. Le butin est à nouveau partagé de la
pgcd(ϕm , ϕn ) = ϕpgcd(m,n)
même manière et le cuisinier reçoit 5 pièces. Quelle est alors la fortune minimale
que peut espérer le cuisinier lorsqu’il décide d’empoisonner le reste des pirates ?

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

[[Link] édité le 6 août 2013 Enoncés 4

Nombres premiers et décomposition primaire Exercice 44 [ 01225 ] [correction]

Soit n ∈ N, montrer √
Exercice 37 [ 01219 ] [correction] n ∈ Q ⇔ ∃m ∈ N, n = m2
√ √
Montrer que les nombres suivants sont composés : En déduire que 2 ∈ / Q et 3 ∈ /Q
a) 4n3 + 6n2 + 4n + 1 avec n ∈ N? b) n4 − n2 + 16 avec n ∈ Z.

Exercice 45 [ 01226 ] [correction]

Exercice 38 [ 01220 ] [correction] Pour p ∈ P et n ∈ Z, on note vp (n) l’exposant de la plus grande puissance de p
Soient a et p deux entiers supérieurs à 2. divisant n.
Montrer que si ap − 1 est premier alors a = 2 et p est premier. a) Montrer que v2 (1000!) = 994.  
b) Plus généralement, calculer vp (n!). On rappelle que ∀x ∈ R, E E(px)
p = E (x).

Exercice 39 [ 03623 ] [correction]

Soit n un naturel non nul. Montrer qu’il existe toujours un nombre premier
strictement compris entre n et n! + 2. Exercice 46 [ 01227 ] [correction]
Soit n ∈ N\ {0, 1}. Montrer que n est le produit de ses diviseurs non triviaux si, et
seulement si, n = p3 avec p ∈ P ou n = p1 p2 avec p1 , p2 ∈ P distincts.
Exercice 40 [ 01221 ] [correction]
Soit p > 3 un nombre premier. Montrer que 24 | p2 − 1.
Exercice 47 [ 01228 ] [correction]
Soient p ∈ P et α ∈ N? . Déterminer les diviseurs positifs de pα .
Exercice 41 [ 01222 ] [correction]
Soit p un nombre premier.
a) Montrer Exercice 48 [correction]
[ 01229 ]
! N
p pα
Q
Soit n ∈ N\ {0, 1} et n = k
k sa décomposition primaire.
∀k ∈ {1, 2, . . . , p − 1} , p | k=1
k Quel est le nombre de diviseurs positifs de n ?
b) En déduire que
∀n ∈ Z, np ≡ n [p]
Exercice 49 [ 01230 ] [correction]
Ce dernier résultat est connu sous le nom de petit théorème de Fermat (1601-1665) Soit n ∈ N\ {0, 1} dont la décomposition primaire est
N
Y
Exercice 42 [ 01223 ] [correction] n= pα
i
i

Soit E = {4k − 1/k ∈ N? }. i=1

a) Montrer que pour tout n ∈ E, il existe p ∈ P ∩ E tel que p | n.
On note d(n) le nombre de diviseurs supérieurs ou égaux à 1 de n et σ(n) la
b) En déduire qu’il y a une infinité de nombre premier p tel que p = −1 [4].
somme de ceux-ci.
Montrer
N N
Y Y piαi +1 − 1
Exercice 43 [ 01224 ] [correction] d(n) = (αi + 1) et σ(n) =
pi − 1
Justifier l’existence de 1000 entiers consécutifs sans nombres premiers. i=1 i=1

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

[[Link] édité le 6 août 2013 Enoncés 5

Exercice 50 [ 01231 ] [correction]

Soit σ : Z → N qui à n ∈ Z associe la somme de diviseurs positifs de n.
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
d = d1 d2 avec d1 et d2 diviseurs positifs de a et b.
c) En déduire que si a et b sont premiers entre eux alors σ(ab) = σ(a)σ(b).
d) Exprimer σ(n) en fonction de la décomposition primaire de n.

Exercice 51 Mines-Ponts MP [ 02653 ] [correction]

Soit p un nombre premier, p > 5. Montrer que p2 − 1 est divisible par 24.

Exercice 52 [ 03209 ] [correction]

Soient n > 2 et N la somme de n entiers impairs consécutifs. Montrer que N n’est
pas un nombre premier.

Exercice 53 X PC [ 03351 ] [correction]

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.

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

[[Link] édité le 6 août 2013 Corrections 6

Corrections Exercice 3 : [énoncé]

a − 1 = bq + r avec 0 6 r < b.
Exercice 1 : [énoncé] abn − 1 = (bq + r + 1)bn − 1 = qbn+1 + bn (r + 1) − 1.
a) x = 1 n’est pas solution. Pour x 6= 1 : Or 0 6 bn (r + 1) − 1 < bn+1 donc la relation ci-dessus est la division euclidienne
x − 1 | x + 3 ⇔ x−1x+3 4
= 1 + x−1 ∈ Z ⇔ x − 1 ∈ Div(4) = {1, 2, 4, −1, −2, −4} de abn − 1 par bn+1 .
Ainsi S = {2, 3, 5, 0, −1, −3}. Le quotient de celle-ci est donc q.
b) x = −2 n’est pas solution. Pour x 6= −2 :
2
x + 2 | x2 + 2 ⇔ xx+2 +2 6
= x − 2 + x+2 ∈ Z ⇔ x + 2 ∈ Div(6) =
{1, 2, 3, 6, −1, −2, −3, −6}. Exercice 4 : [énoncé]
Ainsi S = {−1, 0, 1, 4, −3, −4, −5, −8}. 25 = −1 [11] donc 210 = 1 [11] puis
2123 = 2120 × 23 = (210 )12 × 8 = 1 × 8 = 8 [11].
35 = 1 [11] donc 3121 = 3120 × 3 = (35 )24 × 3 = 1 × 3 = 3 [11].
Exercice 2 : [énoncé] Ainsi 2123 + 3121 = 8 + 3 = 0 [11] et donc 11 | 2123 + 3121 .
a) On a
xy = 3x + 2y ⇔ (x − 2)(y − 3) = 6
ce qui équivaut encore à Exercice 5 : [énoncé]
En détaillant les diviseurs de 6 possibles, on obtient 1234 = 2 [7] et 23 = 1 [7] donc 12344321 = 24321 = 24320 × 2 = 1 × 2 = 2 [7].
4321 = 2 [7] donc 43211234 = 21234 = 21233 × 2 = 1 × 2 = 2 [7].
S = {(3, 9), (4, 6), (5, 5), (8, 4), (1, −3), (0, 0), (−1, 1), (−4, 2)} Par suite 12344321 + 43211234 = 2 + 2 = 4 [7]. Le reste cherché est 4.
b) Pour x, y ∈ Z? ,
1 1 1 Exercice 6 : [énoncé]
+ = ⇔ 5x + 5y = xy ⇔ (x − 5)(y − 5) = 25
x y 5 a) Pour n = 0, 1, 2, 3, 4, 5 on a n3 = n [6] donc 5n3 + n = 6n = 0 [6].
En détaillant les diviseurs de 25 possibles, on obtient b) 32n+1 + 2n+2 = 3.(32 )n + 4.2n = 3.2n + 4.2n = 7.2n = 0 [7].
c) 22n+1 + 32n+1 = 2.(22 )n + 3.(32 )n = 2.4n + 3.4n = 5.4n = 0 [5].
S = {(6, 30), (10, 10), (30, 6), (4, −20), (−20, 4)} d) 38n × 54 + 56n × 73 = 5n × 9 + 5n × 2 = 11 × 5n = 0 [11].
e) 4n − 1 − 3n = (4 − 1)(1 + 4 + · · · + 4n−1 ) − 3n = 3(1 + 4 + · · · + 4n−1 − n)
c) On a or 1 + 4 + · · · + 4n−1 − n = 1 + · · · + 1 − n = n − n = 0 [3] donc 9 | 4n − 1 − 3n.
x2 − y 2 − 4x − 2y = 5 ⇔ (x − 2)2 − (y + 1)2 = 8 f)
et donc 16n − 1 − 15n = (16 − 1)(1 + 16 + · · · + 16n−1 ) − 15n = 15(1 + 16 + · · · + 16n−1 − n)
x2 − y 2 − 4x − 2y = 5 ⇔ (x − y − 3)(x + y − 1) = 8 or 1 + 16 + · · · + 16n−1 − n = 1 + · · · + 1 − n = n − n = 0 [15] donc
152 | 16n − 1 − 15n.
En détaillant les diviseurs de 8 possibles et sachant
a+b

x = +2
(
x−y−3=a

2 Exercice 7 : [énoncé]
⇔
x+y−1=b y = b − a − 1
 n 0 1 2 3 4 5 6 7 8 9
2 n2 + (n + 1)2 + (n + 3)2 0 1 8 1 0 5 6 3 6 5
donc 10 | n2 + (n + 1)2 + (n + 3)2 ⇔ n = 0 ou 4 [10].
on obtient
S = {(5, 0), (5, −2), (−1, 0), (−1, −2)}

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

[[Link] édité le 6 août 2013 Corrections 7

Exercice 8 : [énoncé] Exercice 13 : [énoncé]

(⇒) ok 3 × (2n + 4) − 2 × (3n + 3) = 6 donc pgcd(2n + 4, 3n + 3) | 6.
x 0 1 2 3 4 5 6
(⇐) On observe que : modulo 7.
x2 0 1 4 2 2 4 1
La seule possibilité pour que x2 + y 2 = 0 [7] est que x = y = 0 [7]. Exercice 14 : [énoncé]
a) On aa = bq + r avec 0 6 r < b.

Exercice 9 : [énoncé] 2a − 1 = 2bq+r − 1 = 2bq+r − 2r + 2r − 1 = (2b − 1)(1 + 2b + · · · + 2b(q−1) )2r + 2r − 1

On peut écrire n = 2p + 1 et alors
avec 0 6 2r − 1 < 2b − 1.
n2 = (2p + 1)2 = 4p(p + 1) + 1 b) Posons a0 = a, a1 = b et définissons a2 , . . . , am comme par l’algorithme
d’Euclide avec am = pgcd(am−1 , am−2 ).
Puisque l’un des facteurs de p(p + 1) est pair, le produit 4p(p + 1) est multiple de On a
8 et donc
pgcd(2a −1, 2b −1) = pgcd(2a0 −1, 2a1 −1) = pgcd(2a1 −1, 2a2 −1) = . . . = pgcd(2am −1, 20 −1
4p(p + 1) + 1 ≡ 1 [8]

Exercice 15 : [énoncé]
Exercice 10 : [énoncé]
Si le système possède une solution alors d | m est une condition nécessaire.
(⇒) Si a ≡ b [m] alors m divise b − a et divise a fortiori λb − λa = λ(b − a).
Inversement si d | m alors x = d et y = m donne un couple (x, y) ∈ N2 solution.
(⇐) Si λa ≡ λb [m] alors m divise λ(b − a). Or m et λ sont supposés premiers
entre eux donc m divise b − a.
Exercice 16 : [énoncé]
Soit (x, y) ∈ N2 un couple solution. Posons δ = pgcd(x, y).
Exercice 11 : [énoncé]
On peut écrire
a) pgcd(a, b) = 3 et 3a − 4b = 3.
x = δx0 et y = δy 0 avec x0 ∧ y 0 = 1
b) pgcd(a, b) = 1 et 11b − 8a = 1
c) pgcd(a, b) = 15 et 2a − 5b = 15 L’équation devient :

1 + x0 y 0 = x0 + y 0 ⇔ (x0 − 1)(y 0 − 1) = 0 ⇔ x0 = 1 ou y 0 = 1
Exercice 12 : [énoncé]
Ainsi (x, y) est de la forme (δ, δk) ou (δk, δ) avec k ∈ N.
(⇒) Supposons d = au + bv avec u, v ∈ Z.
Inversement ces couples sont solutions.
pgcd(a, b) | a et pgcd(a, b) | b donc pgcd(a, b) | au + bv = d.
(⇐) 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
Exercice 17 : [énoncé]
au0 + bv0 = pgcd(a, b) a) Soit (x, y) solution. pgcd(x, y) = 5 donc x = 5x0 et y = 5y 0 avec x0 , y 0 ∈ N
premiers entre eux.
et on a alors ppcm(x, y) = 5x0 y 0 = 60 donc x0 y 0 = 12 d’où
d = au + bv (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.
avec u = ku0 et v = kv0 ∈ Z
Finalement (x, y) ∈ {(5, 60), (15, 20), (20, 15), (60, 5)}.
Inversement : ok. Finalement S = {(5, 60), (15, 20), (20, 15), (60, 5)}.

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

[[Link] édité le 6 août 2013 Corrections 8

b) Soit (x, y) solution. pgcd(x, y) = 10 donc x = 10x0 et y = 10y 0 avec x0 , y 0 ∈ N Exercice 22 : [énoncé]
premiers entre eux. Posons d = pgcd(a, bc) et δ = pgcd(a, c).
x + y = 10(x0 + y 0 ) = 100 donc x0 + y 0 = 10. On δ | a et δ | c donc δ | bc puis δ | d.
Sachant x0 ∧ y 0 = 1, il reste (x0 , y 0 ) ∈ {(1, 9), (3, 7), (7, 3), (9, 1)} puis Inversement d | a et d | bc.
(x, y) ∈ {(10, 90), (30, 70), (70, 30), (90, 10)}. Or d ∧ b = 1 car d | a et a ∧ b = 1. Donc d | c puis d | δ.
Inversement : ok. Finalement S = {(10, 90), (30, 70), (70, 30), (90, 10)}. Par double divisibilité d = δ.

Exercice 18 : [énoncé] Exercice 23 : [énoncé]

Posons d = pgcd(a, a + b). a) Théorème de Bézout.
On a d | a et d | (a + b) alors d | b = (a + b) − a donc d | pgcd(a, b) = 1 puis d = 1. b) Soit (u, v) ∈ Z2 un couple solution. On a au + bv = 1 = au0 + bv0 donc
De même pgcd(b, a + b) = 1. Ainsi a ∧ (a + b) = b ∧ (a + b) = 1 et par suite a(u − u0 ) = b(v0 − v)
ab ∧ (a + b) = 1. On a a | b(v0 − v) or a ∧ b = 1 donc a | v0 − v. Ainsi ∃k ∈ Z tel que v = v0 − ka et
alors a(u − u0 ) = b(v0 − v) donne a(u − u0 ) = abk puis u = u0 + kb (sachant
a 6= 0).
Exercice 19 : [énoncé] c) Inversement les couples de la forme ci-dessus sont solutions.
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.
b) Posons δ = pgcd(a, b). On peut écrire a = δa0 et b = δb0 avec a0 ∧ b0 = 1. Exercice 24 : [énoncé]
pgcd(a + b, ppcm(a, b)) = δpgcd(a0 + b0 , ppcm(a0 , b0 )) = δ a) Unicité : Si (an , bn ) et (αn , βn ) sont solutions alors
√ √
an + bn 2 = αn + βn 2
Exercice 20 : [énoncé]
a) n2 + n = n(n + 1). donc √
1 × (2n + 1) − 2 × n = 1 donc (2n + 1) ∧ n = 1. (bn − βn ) 2 = (αn − an )
2 × (n + 1) − 1 × (2n + 1) = 1 donc (2n + 1) ∧ (n + 1) = 1
Si bn 6= βn alors
Par produit (2n + 1) ∧ (n2 + n) = 1. √ αn − a
b) 3n2 + 2n = n(3n + 2). 2= ∈Q
bn − β n
1 × (n + 1) − 1 × n = 1 donc n ∧ (n + 1) = 1.
3 × (n + 1) − 1 × (3n + 2) = 1 donc (3n + 2) ∧ (n + 1) = 1. ce qui est absurde.
Par produit (3n2 + 2n) ∧ (n + 1) = 1. On en déduit bn = βn puis an = αn
Existence : Par la formule du binôme
n
!
√ n
X n √ k
Exercice 21 : [énoncé] (1 + 2) = 2
2 × (n + !
1) − 1 × (2n +! 1) = 1 donc (n + 1) ∧ (2n k
! + 1) = 1. ! k=0
2n + 1 2n 2n + 1 2n
2n+1
= n+1 donc (n + 1) = (2n + 1) . En séparant les termes d’indices pairs de ceux d’indices impairs, on a
n+1 n n+1 n √ √
2n + 1
!
2n
! (1 + 2)n = an + bn 2
Puisque ∈ Z, on a (n + 1) | (2n + 1) or (n + 1) ∧ (2n + 1) = 1
n+1 n avec
E(n/2) E((n−1)/2)
! ! !
2n X n p
X n
donc (n + 1) | . an = 2 et bn = an = 2p
n p=0
2p p=0
2p + 1

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

[[Link] édité le 6 août 2013 Corrections 9

b) On a Exercice 27 : [énoncé]
√ √ 
Supposons a2 | b2 .

a2n − 2b2n = (an + bn 2) an − bn 2
Posons d = pgcd(a, b). On a d2 = pgcd(a, b)2 = pgcd(a2 , b2 ) = a2 donc d = |a| puis
Or en reprenant les calculs qui précèdent a | b.
√ √
(1 − 2)n = an − bn 2
Exercice 28 : [énoncé]
donc √ √ On peut écrire x = pq avec p ∈ Z, q ∈ N? et p ∧ q = 1.
a2n − 2b2n = (1 + 2)n (1 − 2)n = (−1)n xn = k ∈ Z donne q n k = pn . p ∧ q = 1 donc pn ∧ q n = 1. Puisque q n | pn × 1 on a
c) La relation qui précède permet d’écrire q n | 1 (par Gauss).
Par suite q n = 1 et donc q = 1 et x = p ∈ Z.
an u + bn v = 1 avec u, v ∈ Z

On en déduit que an et bn sont premiers entre eux. Exercice 29 : [énoncé]

Il existe u, v ∈ Z tel que mu + nv = 1.
Analyse : Si c convient alors c = cmu+nv = bu av . A priori c ∈ Q.
Exercice 25 : [énoncé] Synthèse : Soit c = bu av . On a cn = bnu anv = amu anv = a et de même cm = b.
Unicité : Si (d1 , d2 ) est solution alors pgcd(d, a) = pgcd(d1 d2 , a) Puisque le nombre rationnel c possède une puissance entière, c ∈ Z.
Or d2 ∧ a = 1 car d2 | b et a ∧ b = 1, donc pgcd(d1 d2 , a) = pgcd(d1 , a) = d1 car
d1 | a.
De même d2 = pgcd(d, b) d’où l’unicité. Exercice 30 : [énoncé]
Existence : Posons d1 = pgcd(d, a) et d2 = pgcd(d, b). On a d1 | a et d2 | b. Le nombre de côté du polygone construit est le plus petit entier k ∈ N? tel que
d1 | a et d2 | b donc d1 ∧ d2 = 1 car a ∧ b = 1. n | kp.
d1 | d, d2 | d et d1 ∧ d2 = 1 donc d1 d2 | d. Posons δ = pgcd(n, p). On peut écrire n = δn0 et p = δp0 avec n0 ∧ p0 = 1.
Inversement : Par l’égalité de Bézout on peut écrire d1 = u1 d + v1 a et n | kp ⇔ n0 | kp0 i.e. n0 | k. Ainsi k = n0 = n/δ.
d2 = u2 d + v2 b donc d | d1 d2 = U d + v1 v2 ab car d | ab.

Exercice 31 : [énoncé]
Exercice 26 : [énoncé] a) Par récurrence sur n ∈ N? :
Si k | a et ` | b alors k` | ab. Ainsi ϕ(div(a) × div(b)) ⊂ div(ab). Pour n = 1 : ϕ2 ϕ0 − ϕ21 = 0 − 1 = −1 : ok.
Soit d ∈ div(ab). Posons k = pgcd(d, a) et ` = pgcd(d, b). On a k ∈ div(a), Supposons la propriété établie au rang n > 1.
` ∈ div(b) et k ∧ ` = 1 car a ∧ b = 1. Comme k | d, ` | d et k ∧ ` = 1 on a k` | d. De
ϕn+2 ϕn −ϕ2n+1 = (ϕn +ϕn+1 )ϕn −ϕn+1 (ϕn +ϕn−1 ) = ϕ2n −ϕn+1 ϕn−1 = −(−1)n = (−1)n+1
plus k = du + av et ` = du0 + bv donc k` = dU + abV d’où d | k` et finalement HR
d = k`. Ainsi ϕ(div(a) × div(b)) = div(ab).
Récurrence établie.
Soit (k, `) ∈ div(a) × div(b) et (k 0 , `0 ) ∈ div(a) × div(b). Si ϕ(k, `) = ϕ(k 0 , `0 ) alors
b) Par l’égalité de Bézout on obtient que ϕn ∧ ϕn+1 = 1 puisque la relation
k` = k 0 `0 .
précédente permet d’écrire uϕn + vϕn+1 = 1 avec u, v ∈ Z.
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
c) Par récurrence sur m ∈ N?
` = `0 .
Pour m = 1 : ϕn+1 = ϕ1 ϕn+1 + ϕ0 ϕn car ϕ1 = 1 et ϕ0 = 0.
Ainsi ϕ est injective et finalement ϕ réalise une bijection de div(a) × div(b) vers
Supposons la propriété établie au rang n > 1
div(ab).
ϕ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
HR

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

[[Link] édité le 6 août 2013 Corrections 10

Récurrence établie. Exercice 34 : [énoncé]

d) Déterminons une solution particulière : x = 2 + 10k = 5 + 13k 0 avec k, k 0 ∈ Z.
10k − 13k 0 = 3. Cherchons u, v ∈ Z tel que 10u + 13v = 1. u = 4 et v = −3
pgcd(ϕm+n , ϕn ) = pgcd(ϕm ϕn−1 +ϕm−1 ϕn , ϕn ) = pgcd(ϕm ϕn−1 , ϕn ) = pgcd(ϕm , ϕn ) conviennent.
Prenons k = 12, k 0 = 9 ce qui donne x = 122.
car ϕn ∧ ϕn−1 = 1. Soit x une autre solution. On a
Par récurrence on obtient que (
x = 122 [10]
∀q ∈ N : ϕm ∧ ϕn = ϕm+qn ∧ ϕn x = 122 [13]
On en déduit alors pgcd(ϕm , ϕn ) = pgcd(ϕn , ϕr ) car on peut écrire m = nq + r
donc 10 | x − 122 et 13 | x − 122 donc 130 | x − 122 et par suite x = 122 + 130k
avec q ∈ N.
avec k ∈ Z.
e) Suivons l’algorithme d’Euclide calculant pgcd(m, n) :
Inversement : ok.
a0 = m, a1 = n, a0 = a1 q1 + a2 , a1 = a2 q2 + a3 ,..., ap−1 = ap qp + 0 avec
ap = pgcd(m, n)
Or pgcd(ϕn , ϕm ) = pgcd(ϕa0 , ϕa1 ) = pgcd(ϕa1 , ϕa2 ) = . . . = pgcd(ϕap , ϕ0 ) = ϕap Exercice 35 : [énoncé]
car ϕ0 = 0. Il existe u, v ∈ Z tel que bu + b0 v = 1.
Ainsi pgcd(ϕm , ϕn ) = ϕpgcd(m,n) . Soit x = a0 bu + ab0 v.
On a x = a0 bu + a − abu = a [b] et x = a0 − a0 b0 v + ab0 v = a0 [b0 ] donc x est
solution.
Exercice 32 : [énoncé] Soit x0 une autre solution. On a x = x0 [b] et x = x0 [b0 ] donc b | (x0 − x) et
Par l’absurde, supposons que ai et aj (avec i, j ∈ {1, . . . , n + 1}) ne soient pas b0 | (x0 − x).
premiers entre eux. Or b ∧ b0 = 1 donc bb0 | (x0 − x).
Considérons d un diviseur premier commun à ai et aj . L’entier d est diviseur de Inversement, soit x0 tel que bb0 | x0 − x, on a bien x0 = x = a [b] et
ai − aj donc de (i − j).n!. x0 = x = a0 [b0 ].
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
divise 1. Exercice 36 : [énoncé]
C’est absurde. Notons x ∈ N le montant du trésor. De part les hypothèses

 x = 3 [17]

Exercice 33 : [énoncé] x = 4 [11]
Supposons x = p/q une racine rationnelle de l’équation (E) avec p et q premiers

x = 5 [6]

entre eux.
En réduisant au même dénominateur, on obtient Déterminons un entier x tel que x = 3 + 17k = 4 + 11k 0 = 5 + 6k 00 avec
k, k 0 , k(00 ∈ Z.
pn + an−1 qpn−1 + · · · + a1 pq n−1 + a0 q n = 0 11k 0 − 6k 00 = 1
On a donc 17k − 6k 00 = 2.
Puisque q divise an−1 qpn−1 + · · · + a1 pq n−1 + a0 q n , on obtient que q divise pn . 17k − 11k 0 = 1
Or p et q sont premiers entre eux donc nécessairement q = 1 et donc x = p ∈ Z. Or k = −2 et k 00 = −6 définit une solution particulière de cette équation dont la
Ainsi les racines rationnelles de (E) sont entières. solution générale est alors

k = −2 + 6` et k 00 = −6 + 17` car 6 ∧ 17 = 1

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

[[Link] édité le 6 août 2013 Corrections 11

Prenons ` de sorte que 11 | 17k − 1. Exercice 40 : [énoncé]

p2 − 1 = (p − 1)(p + 1).
17k − 1 = −35 + 102` = −2 + 3` [11] Comme p > 3 on a p impair d’où p = 1 ou 3 [4].
Si p = 1 [4] alors 4 | p − 1 et 2 | p + 1.
Pour ` = 8, k = 46, k 0 = 71 et k 00 = 130 on a x = 785. Si p = 3 [4] alors 2 | p − 1 et 4 | p + 1.
La solution générale du système est Dans les deux cas 8 | p2 − 1.
Comme p > 3, p n’est pas multiple de 3 puisque p est premier d’où p = 1 ou
x = 785 + 1122k 2 [3].
Si p = 1 [3] alors 3 | p − 1.
Si p = 2 [3] alors 3 | p + 1.
Exercice 37 : [énoncé] Dans les deux cas 3 | p2 − 1.
a) 4n3 + 6n2 + 4n + 1 = (n + 1)4 − n4 = ((n + 1)2 − n2 )((n + 1)2 + n2 ) = Enfin, comme 8 ∧ 3 = 1 on obtient 24 | p2 − 1.
(2n + 1)(2n2 + 2n + 1).
Cet entier est composé pour n ∈ N? car 2n + 1 > 2 et 2n2 + 2n + 1 > 2.
b) n4 − n2 + 16 = (n2 + 4)2 − 9n2 = (n2 − 3n + 4)(n2 + 3n + 4). Exercice 41 : [énoncé]
De plus les équations n2 − 3n + 4 = 0, 1 ou − 1 et n2 + 3n + 4 = 0,1 ou − 1 a) On a ! !
n’ont pas de solutions car toutes de discriminant négatif. Par conséquent p p p−1
n4 − n2 + 16 est composée. =
k k k−1
donc ! !
p p−1
Exercice 38 : [énoncé] k =p
k k−1
Supposons que ap − 1 premier.
Comme ap − 1 = (a − 1)(1 + a + · · · + ap−1 ) on a a − 1 = 1 ou
!
p
1 + a + · · · + ap−1 = 1. Par suite p | k .
k
Or p > 2 et a 6= 0 donc 1 + a + · · · + ap−1 6= 1. Par conséquent a = 2. !
Montrons maintenant que p est premier. p
Or p est premier et k < p donc k ∧ p = 1 puis p | en vertu du théorème de
Si d | p alors on peut écrire p = cd puis ap − 1 = (ad )c − 1. k
Si d 6= p alors c > 2 puis par le résultat précédent on obtient ad = 2 puis d = 1. Gauss.
Ainsi les seuls diviseurs de p sont 1 et lui-même. b) Par récurrence finie sur n ∈ {0, 1, . . . , p − 1}
Finalement p est premier. Pour n = 0 : ok
Supposons la propriété établie au rang n ∈ {0, 1, . . . , p − 2}
Par la formule du binôme
Exercice 39 : [énoncé] p−1
!
p p
X p
Considérons l’entier n! + 1. Celui-ci est divisible par un nombre premier p (n + 1) = n + nk + 1 ≡ n + 1 [p]
inférieur à n! + 1. k=1
k
Si ce nombre premier p est aussi inférieur à n alors il divise n! (car apparaît
comme l’un des facteurs de ce produit) et donc il divise aussi 1 = (n! + 1) − n!. car pour 1 6 k 6 p − 1. !
Ceci est absurde et donc le nombre premier en question est au moins égal à n + 1. p
≡0 [p]
Finalement, il est strictement compris entre n et n! + 2. k
Récurrence établie.

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

[[Link] édité le 6 août 2013 Corrections 12

Pour tout n ∈ Z, il existe r ∈ {0, 1, . . . , p − 1} tel que n ≡ r [p] et Exercice 46 : [énoncé]

(⇐) clair
np ≡ r p ≡ r ≡ n [p] (⇒) n est divisible par un nombre premier p et ne peut lui être égal. On peut
donc écrire n = pd avec 1 < d < n. Si d est premier alors on obtient la seconde
forme. Sinon, il ne peut qu’être divisible par p (car q | d implique que n est un
Exercice 42 : [énoncé] multiple de pqd car n est produit de ses diviseurs non triviaux). Le nombre d est
a) n est impair, il n’est donc pas divisible par 2. Si tous les nombres premiers p alors de la forme d = pk . k = 1 et k > 3 sont à exclure puisque n est le produit de
divisant n sont tels que p = 1 [4] alors n = 1 [4] et donc n ∈ /E ses diviseurs non triviaux. Il reste d = p2 et alors n = p3
b) Supposons qu’il n’y en ait qu’un nombre fini de nombres premiers p1 p2 . . . pn .
Considérons Exercice 47 : [énoncé]
n = 4p1 p2 . . . pn − 1 ∈ E Soit d ∈ Div(pα ) ∩ N. Notons β la plus grande puissance de p telle que pβ | d.
Il existe p ∈ P ∩ E tel que p | n mais p | p1 p2 . . . pn donc p | 1. Absurde. On peut écrire d = pβ k avec p 6 |k.
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 α.
Inversement : ok.
Exercice 43 : [énoncé]
Considérons les xk = 1001! + k avec 2 6 k 6 1001. Ce sont 1000 entiers
consécutifs. Exercice 48 : [énoncé]
N
Pour tout 2 6 k 6 1001, on a k | (1001)! donc k | xk avec 2 6 k < xk donc xk ∈
/ P.
pβkk avec ∀1 6 k 6 N, 0 6 βk 6 αk .
Q
Les diviseurs positifs sont les d =
k=1
Le choix des βk conduisant à des diviseurs distincts, il y a exactement
QN
Exercice 44 : [énoncé] (αk + 1) diviseurs positifs de n.
(⇐) ok √ k=1
√
(⇒) Si n ∈ Q alors on peut écrire n = pq avec p ∧ q = 1.
On a alors q 2 n = p2 donc n | p2 Exercice 49 : [énoncé]
De plus q 2 n = p2 et p2 ∧ q 2 = 1 donne p2 | n. Soit d ∈ N diviseur de n.
Par double divisibilité n = p2 . √ √ Tout diviseur premier de d est aussi diviseur de n et c’est donc l’un des p1 , . . . , pN .
ni 2, ni 3 ne sont des carrés d’un entier, donc 2 ∈/ Q et 3 ∈
/ Q. N
pβi i avec βi ∈ N.
Q
Par suite, on peut écrire d =
i=1
pβi i | d donc pβi i | n d’où βi 6 αi .
N
Exercice 45 : [énoncé]
pβi i avec pour tout i ∈ {1, . . . , N }, 0 6 βi 6 αi .
Q
Ainsi d est de la forme d =
a) v2 (1000!) = 500 + v2 (500!) car 1000! = 2500 × 500! × k avec k produit de i=1
nombres impairs. Inversement de tels nombres sont bien diviseurs de n.
v2 (1000!) = 500
 +250 +125+ 62+ 31 + 15 + 7 + 3 + 1 = 994.   Il y a autant de nombres de cette forme distincts que de choix pour les
N

n n n E(n/p) E(n/p)
b) vp (n!) = E p + vp E p ! = E p + E + v p E or β1 , . . . , βN .Pour βi , il y a αi + 1 choix possibles, au total d(n) =
Q
(αi + 1).
    p   p
i=1
E E(px)p = E (x) avec x = pn2 donne E E(n/p) p = E pn2 puis finalement De plus
       
vp (n!) = E np + E pn2 + · · · + E pnk avec k = E ln n     
ln p . α1 X
X α2 αN
X α1
X α2
X αN
X
σ(n) = ... pβ1 1 pβ2 2 . . . pβNN =  pβ1 1   pβ2 2  . . .  pβNN 
β1 =0 β2 =0 βN =0 β1 =0 β2 =0 βN =0

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

[[Link] édité le 6 août 2013 Corrections 13

Par sommation géométrique Exercice 53 : [énoncé]

On peut écrire n = 2k (2p + 1) avec k, p ∈ N et l’enjeu est d’établir p = 0.
N k k
Y pαi +1 − 1
i Posons α = a2 et β = b2 . On a
σ(n) =
pi − 1
i=1 an + bn = α2p+1 + β 2p+1 = α2p+1 − (−β 2p+1 )

On peut alors factoriser par α − (−β) = α + β et puisque an + bn est un nombre

Exercice 50 : [énoncé] premier, on en déduit que α + β = 1 ou α + β = an + bn . Puisque α, β > 1, le cas
α+1
a) Div(pα ) ∩ N = 1, p, p2 , . . . , pα donc σ(pα ) = p p−1−1 .
 α + β = 1 est à exclure et puisque α 6 an et β 6 bn , le cas α + β = an + bn
entraîne
b) Soit d ∈ Div(ab) ∩ N. Posons d1 = pgcd(d, a) et d2 = pgcd(d, b).
α = an et β = bn
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. Puisque a > 2, l’égalité α = an = α2p+1 entraîne p = 0 et finalement n est une
d1 = du1 + av1 et d2 = du2 + bv2 donc d1 d2 = dk + abv1 v2 d’où d | d1 d2 . puissance de 2.
Finalement d = d1 d2 .
Supposons d = δ1 δ2 avec δ1 ∈ Div(a) ∩ N et δ2 ∈ Div(b) ∩ N.
On a d1 | δ1 δ2 et d1 ∧ δ2 = 1 donc d1 | δ1 et de même δ1 | d1 puis d1 = δ1 . De
même d2 = δ2 . ! !
P P P P P
c) σ(ab) = d= d1 d2 = d1 db = σ(a)σ(b).
d|ab d1 |a d2 |b d1 |a d2 |b
N α
pi i+1 −1
d) Si n = pα αN Q
1 . . . pN alors σ(n) =
1
pi −1 .
i=1

Exercice 51 : [énoncé]
p2 − 1 = (p − 1)(p + 1).
p est impair donc p − 1 et p + 1 sont deux entiers pairs consécutifs, l’un est
divisible par 2, l’autre par 4. Ainsi 8 | p2 − 1.
Les entiers p − 1, p, p + 1 sont consécutifs, l’un est divisible par 3, ce ne peut être p
car p > 5 premier. Ainsi 3 | p2 − 1.

Exercice 52 : [énoncé]
Notons 2p + 1 le premier nombre impair sommé. On a
n−1
X
N= (2k + 2p + 1) = n(n + 2p)
k=0

avec n > 2 et n + 2p > 2. Ainsi N est composé.

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