CAPES DE M ATH ÉMATIQUES Renaud Coulangeon

Écrit Mathématiques Générales

Concours 2010 Université Bordeaux 1

Feuille no 2
Arithmétique.

Dans toute la suite, on convient de noter a ∧ b le PGCD de deux entiers a et b, et a ∨ b leur PPCM.
Exercice 1. Par combien de (( 0 )) se termine (( 1000! )) ?
Exercice 2. Montrer que pour tout entier naturel n :

• 111 divise 106n + 103n − 2.

• 288 divise 72n+1 − 48n − 7.

n n
• 7 divise 42 + 22 + 1.

• 9 divise 22n + 15n − 1.

Exercice 3.
7
1. Quel est le dernier chiffre de 77 ?
n
2. Quel est le reste de la division euclidienne par 7 de 1010 (n ∈ N) ?

Exercice 4. Est-ce que 13 divise 270 + 370 ?

Exercice 5. Montrer que pour tout entier naturel k impair, et tout entier naturel n > 1, 2n+2 divise
n
k2 − 1.
Exercice 6.

1. Déterminer tous les entiers naturels ayant exactement 1789 diviseurs.

2. Pour n ∈ N∗ , on note N le nombre de ses diviseurs et P leur produit. Établir l’identité P2 = n N .

Exercice 7. Quels sont les nombres premiers p tels que p divise 2 p + 1 ?

Exercice 8.

1. Soient a, b et c trois entiers naturels. Montrer que

(a) Si 5 divise a2 + b2 + c2 alors 5 divise abc.

(b) Si 7 divise a3 + b3 + c3 alors 7 divise abc.
(c) Trouver une généralisation en observant que 5 et 7 sont premiers.

Exercice 9.

1. Soit m et n deux entiers naturels premiers entre eux, a et b deux entiers > 1. Montrer que
am = bn si et seulement si il existe un entier naturel x tel que a = x n et b = x m .

2. Que peut-on dire si l’on omet l’hypothèse (( m et n premiers entre eux )) ?

3. Étant donnés deux entiers naturels > 1 a et b, à quelle condition le réel logb a est-il rationnel ?

1
CAPES DE M ATH ÉMATIQUES
Renaud Coulangeon
Concours 2010

Exercice 10. Le produit de trois entiers naturels consécutifs peut-il être un carré ? un cube ? une puis-
sance kième ? [remarquer que le produit de 3 entiers consécutifs s’écrit sous la forme n(n2 − 1) et que n et
n2 − 1 sont premiers entre eux]
Exercice 11. Soit n un entier naturel > 2. Montrer que parmi n + 1 entiers distincts entre 2 et 2n, deux
au moins sont tels que l’un divise l’autre [on pourra écrire chacun de ces entiers sous la forme a = 2k b avec
b impair].
Exercice 12. Soient 1 < n 6 m deux entiers naturels et Sn,m = ∑m 1
k =n k . On veut montrer que Sn,m n’est
pas un entier. Pour n 6 k 6 m, on pose k = 2ak qk avec qk impair.
1. Montrer que a := max { ak , n 6 k 6 m} est atteint pour un unique entier k0 entre n et m.

2. En déduire que Sn,m n’est pas entier.

Exercice 13. Triplets pythagoriciens On appelle triplet pythagoricien tout triplet d’entiers naturels non
nuls( x, y, z) vérifiant la relation x2 + y2 = z2 . Un tel triplet est dit primitif si les trois entiers x, y, z sont
premiers entre eux.
1. Montrer que si( x, y, z) est un triplet pythagoricien primitif, alors x et y sont de parités différentes.

2. Montrer que les deux assertions suivantes sont équivalentes

(a) ( x, y, z) est un triplet pythagoricien primitif avec x impair.

(b) Il existe ( p, q) ∈ N∗2 avec p > q, p et q premiers entre eux et de parités différentes tels que
i. x = p2 − q2 .
ii. y = 2pq.
iii. z = p2 + q2 .

Exercice 14. Soient a et b deux entiers naturels, d = a ∧ b leur PGCD, m = a ∨ b leur PPCM. Montrer
que dm = ab
Exercice 15. Démontrer que pour a > 2, m ∈ N∗ et n ∈ N∗

( a m − 1) ∧ ( a n − 1) = a d − 1

où d = m ∧ n.
Exercice 16. Soient a, b, c, d quatre entiers tels que ad − bc = 1. Montrer que

( am + bn) ∧ (cm + dn) = m ∧ n.

Exercice 17. Théorème de Lamé. Le but de cet exercice est de montrer le théorème suivant :
Soient a et b deux entiers naturels non nuls, avec a > b. Alors, le nombre d’étapes de l’algorithme d’Euclide
appliqué au couple ( a, b) est majoré par

5 × ( nombre de chiffres de l’écriture en base 10 de b).

Écrivons les premières (et les dernières) étapes de l’algorithme d’Euclide :

r0 := a = bq1 + r2 , 0 6 r2 < b (1)

r1 : = b = r2 q2 + r3 , 0 6 r3 < r2 (2)
..
. (3)
r n −2 = r n −1 q n −1 + r n , 0 6 r n < r n −1 (4)
r n −1 = r n q n (5)

2
CAPES DE M ATH ÉMATIQUES
Renaud Coulangeon
Concours 2010

1. Montrer que pour tout 0 6 i 6 n on a

r n − i > f i +2

où f k désigne le kième terme de la suite de Fibonacci f 1 = f 2 = 1, f k = f k−1 + f k−2 pour k > 3.
[remarquer que qk > 1 pour tout k et qn > 2].
 √  n −1
2. En déduire que b > 1+2 5 .
 √ 
1+ 5
3. Montrer que log10 2 > 15 .

4. Conclure.

Exercice 18. Soit φn la suite de Fibonacci définie par φ0 = 0, φ1 = 1 et φn+2 = φn + φn+1 pour tout
n > 0.

1. Établir que ∀n ∈ N∗ , φn+1 φn−1 − φn2 = (−1)n . En déduire que ∀n ∈ N∗ , φn et φn−1 sont
premiers entre eux.

2. Montrer, pour tout n ∈ N∗ , les égalités suivantes :

n n 2n−1 [ n2 ] 
n−i

∑ φi = φn+2 − 1 , ∑ φi2 = φn φn+1 , ∑ φi φi+1 = 2
φ2n , ∑ i
= φn+1 .
i =1 i =1 i =1 i =1

3. Montrer que ∀n ∈ N, ∀m ∈ N∗ , φn+m = φm φn+1 + φm−1 φn . En déduire que ∀n ∈ N, ∀m ∈ N∗ ,

φn+m ∧ φm = φn ∧ φm .

4. Montrer que si r est le reste de la division euclidienne de a ∈ N par b ∈ N∗ , alors φa ∧ φb =

φb ∧ φr . En déduire que ∀n ∈ N, ∀m ∈ N∗ , φn ∧ φm = φn∧m .

Exercice 19. Algorithme d’Euclide étendu.

Soient a et b deux entiers naturels non nuls. On reprend les notations de l’exercice précédent pour
l’algorithme d’Euclide (1), et à côté de la suite des restes (ri )i∈N on définit deux suites (ui )i∈N et
(vi )i∈N de la façon suivante :
1. u0 = 1, v0 = 0, u1 = 0, v1 = 1.

2. pour i > 2, ui = ui−2 − ui−1 qi−1 et vi = vi−2 − vi−1 qi−1 .

Montrer que le couple (un , vn ) que l’on obtient à la sortie de l’algorithme fournit une relation de
Bezout, c’est-à-dire
aun + bvn = a ∧ b.
Montrer en outre que |un | 6 b et |vn | 6 a.
Exercice 20. Le problème des scores. Soient a et b deux entiers naturels non nuls et premiers entre eux.
Pour tout entier relatif c fixé, on considère l’équation

ax + by = c , ( x, y) ∈ Z2 (6)

1. Montrer que quel que soit l’entier c, l’équation (6) admet des solutions dans Z2 .

2. Montrer que si le couple ( x, y) est solution de (6), alors pour tout k ∈ Z, le couple ( x + kb, y − ka)
est également solution. En déduire que pour tout entier c, l’équation (6) admet une solution
( x, y) ∈ Z2 avec 0 6 y 6 a − 1.

3
CAPES DE M ATH ÉMATIQUES
Renaud Coulangeon
Concours 2010

3. En déduire que si c > ab − a − b, il existe (au moins) un couple ( x, y) d’entiers positifs ou nuls
solution de l’équation (6).

4. Montrer enfin que si c = ab − a − b, l’équation (6) n’a pas de solution avec x et y entiers naturels.

5. Application : quels sont les scores réalisables au rugby ? On rappelle qu’une pénalité ou un
drop rapportent 3 points, un essai 5 et un essai transformé 7.

Exercice 21. Montrer que 1996 a un multiple qui ne s’écrit qu’avec des 4.
Exercice 22. Test de Lucas - Nombres de Fermat

1. On rappelle que si p est un nombre premier, le groupe multiplicatif (Z/pZ)× des éléments inversibles
modulo p est cyclique d’ordre p − 1. On se propose de montrer dans cette question qu’un entier n
est premier si et seulement si il existe α ∈ (Z/nZ)× tel que

• αn−1 ≡ 1 mod n
n −1
• α p 6≡ 1 mod n pour tout diviseur premier p de n − 1.
Ce critère est souvent appelé test de Lucas dans la littérature.

(a) Montrer que si n est premier, tout générateur α du groupe (cyclique) α ∈ (Z/nZ)×
convient.
(b) Inversement, montrer qu’un élément α satisfaisant les conditions ci-dessus est nécessairement
d’ordre n − 1 dans (Z/nZ)× et conclure.

2. Soit a un entier > 2, et n un entier > 1. Montrer que si an + 1 est premier, alors a est pair et n est
une puissance de 2.
n
3. On définit pour n ∈ N le nombre Fn = 22 + 1 (“nième nombre de Fermat”).

(a) Montrer que si n 6= m, Fn et Fm sont premiers entre eux.

(b) En utilisant le test de Lucas, montrer que Fn est premier si et seulement si il existe k ∈ Z
Fn −1
tel que k 2 ≡ −1 mod Fn

p
Exercice 23. Soit x = q un rationnel non décimal avec p et q étrangers. On pose q = 2α 5β q1 , avec q1
étranger à 10, et l’on note γ := max (α, β) et ν := l’ordre de 10 dans le groupe multiplicatif (Z/q1 Z)× ,
c’est-à-dire le plus petit entier naturel non nul tel que 10ν ≡ 1 mod q1 .

1. Montrer que
x = a 0 , a 1 · · · a γ a γ +1 · · · a γ + ν ,
la notation aγ+1 · · · aγ+ν signifiant que le motif aγ+1 · · · aγ+ν se répète à l’infini.

2. Montrer en outre que ν est le plus petit entier vérifiant cette propriété, c’est-à-dire que tout
entier m tel que le développement de x se termine par un motif récurrent de longueur m est un
multiple de ν.

3. Déterminer, pour tout entier naturel k, un rationnel dont le développement décimal est périodique
de période k.