Chap. 1. Algèbre générale
2) On remarque que 1000 = 8 × 125 ≡ 0 (mod 8) donc 10
k
≡ 0 (mod 8) pour tout
k 3.
Ainsi, avec les notations précédentes n ≡ a 0 10
0 + a 1 10
1 + a 2 10
2
≡ a 2 a 1 a 0
(mod 8). Par conséquent, 8 | n = a p · · · a 1 a 0 si et seulement si 8 | a 2 a 1 a 0 .
Exercice 1.2
Mines-Ponts MP 2007
Quel est le dernier chiffre de l’écriture décimale de 7
7
7
?
On a 7
1
≡ −3 (mod 10), 7
2
≡ −1 (mod 10), d’où 7
4
≡ 1 (mod 10). Il suffit donc
de trouver le reste de la division euclidienne de l’exposant 7
7 par 4 :
7
7
≡ (−1)
7
≡ −1 ≡ 3 (mod 4), donc il existe n ∈ N tel que 7
7 = 4n + 3.
On en déduit que 7
7
7
= 7
4n 7
3
≡ 7
3
≡ −7 ≡ 3 (mod 10), donc le dernier chiffre de
l’écriture décimale de 7
7 7 est le chiffre 3.
Exercice 1.3
Petit théorème de Fermat
Soit p un nombre premier.
1) Montrer que pour k ∈ [[1 , p − 1]], p divise
p
k
.
2) En déduire que, pour tout (a, b) ∈ Z
2 , (a + b)
p
≡ a
p + b
p (mod p).
3) Montrer par récurrence que, pour tout a ∈ Z, a
p
≡ a (mod p), et que si p ne
divise pas a, alors a
p−1
≡ 1 (mod p).
1) On a
p
k
=
p( p − 1) · · · ( p − k + 1)
k!
mais factoriser par p n’est pas très éclairant car on ne sait pas si l’autre facteur est un entier.
Écrivons plutôt k!
p
k
= p( p − 1) · · · ( p − k + 1). Par conséquent, p | k!
p
k
,
or p est premier et k ∈ [[1 , p − 1]], donc p et k! sont premiers entre eux.
On déduit par le théorème de Gauss que p divise
p
k
.
2) D’après la formule du binôme de Newton : (a + b)
p =
p
k=0
p
k
a
k b
p−k .
D’après 1), pour k ∈ [[1 , p − 1]],
p
k
≡ 0 (mod p) donc, modulo p, seuls
restent dans le développement le premier et le dernier terme :
(a + b)
p
≡ a
p + b
p
(mod p) .
2) On remarque que 1000 = 8 × 125 ≡ 0 (mod 8) donc 10
k
≡ 0 (mod 8) pour tout
k 3.
Ainsi, avec les notations précédentes n ≡ a 0 10
0 + a 1 10
1 + a 2 10
2
≡ a 2 a 1 a 0
(mod 8). Par conséquent, 8 | n = a p · · · a 1 a 0 si et seulement si 8 | a 2 a 1 a 0 .
Exercice 1.2
Mines-Ponts MP 2007
Quel est le dernier chiffre de l’écriture décimale de 7
7
7
?
On a 7
1
≡ −3 (mod 10), 7
2
≡ −1 (mod 10), d’où 7
4
≡ 1 (mod 10). Il suffit donc
de trouver le reste de la division euclidienne de l’exposant 7
7 par 4 :
7
7
≡ (−1)
7
≡ −1 ≡ 3 (mod 4), donc il existe n ∈ N tel que 7
7 = 4n + 3.
On en déduit que 7
7
7
= 7
4n 7
3
≡ 7
3
≡ −7 ≡ 3 (mod 10), donc le dernier chiffre de
l’écriture décimale de 7
7 7 est le chiffre 3.
Exercice 1.3
Petit théorème de Fermat
Soit p un nombre premier.
1) Montrer que pour k ∈ [[1 , p − 1]], p divise
p
k
.
2) En déduire que, pour tout (a, b) ∈ Z
2 , (a + b)
p
≡ a
p + b
p (mod p).
3) Montrer par récurrence que, pour tout a ∈ Z, a
p
≡ a (mod p), et que si p ne
divise pas a, alors a
p−1
≡ 1 (mod p).
1) On a
p
k
=
p( p − 1) · · · ( p − k + 1)
k!
mais factoriser par p n’est pas très éclairant car on ne sait pas si l’autre facteur est un entier.
Écrivons plutôt k!
p
k
= p( p − 1) · · · ( p − k + 1). Par conséquent, p | k!
p
k
,
or p est premier et k ∈ [[1 , p − 1]], donc p et k! sont premiers entre eux.
On déduit par le théorème de Gauss que p divise
p
k
.
2) D’après la formule du binôme de Newton : (a + b)
p =
p
k=0
p
k
a
k b
p−k .
D’après 1), pour k ∈ [[1 , p − 1]],
p
k
≡ 0 (mod p) donc, modulo p, seuls
restent dans le développement le premier et le dernier terme :
(a + b)
p
≡ a
p + b
p
(mod p) .