Arithmétique

Divisiblité, division euclidienne et congruences

Échauffements - Exercices de rappel

Exercice 1

Les nombres suivants sont-ils divisibles par 3 ? par 9 ? par 6 ? par 18 ?

27 - 129 - 567 - 837 - 22134 - 1556 - 50166

Correction

27 = 3 × 9 est bien divisible par 3
129 = 3 × 43 est bien aussi divisible par 3
567 = 3 × 189 est bien aussi divisible par 3
837 = 3 × 279 est bien aussi divisible par 3
22134 = 3 × 7378 est bien aussi divisible par 3
1554 = 3 × 518 et 1557 = 3 × 519 et donc 1556 n'est pas divisible par 3
50166 = 3 × 16722 est bien aussi divisible par 3

Il est bien plus simple de se remémorer de la règle:
Un nombre entier est divisible par 3 si la somme de ses chiffres est divisible par 3

On démontrera (enfin ?!) ce résultat plus tard dans ce cours.

On démontrera alors de même que
Un nombre entier est divisible par 9 si la somme de ses chiffres est divisible par 9

ce qui montre que, dans la liste, les nombres divisibles par 9 sont 27 - 567 - 837 - 50166 et non pas les autres: 129 - 22134 - 1556

Un nombre est divisible par 6 = 3 × 2 s'il est divisible par 3 et 2; il faut donc chercher dans la liste précédente des nombres divisibles par 3, ceux qui sont aussi pairs, à savoir: 22134 et 50166.

De même un nombre est divisible par 18 = 9 × 2 s'il est divisible par 9 et 2; il faut donc chercher dans la liste précédente des nombres divisibles par 9, ceux qui sont aussi pairs. Il n'y en a qu'un: 50166.

Exercice 2 - Sur la parité

Quelle est la parité du carré d'un nombre pair ? du carré d'un nombre impair ?
Quelle est la parité du produit de deux nombres pairs ? de deux nombres impairs ?
Quelle est la parité de la somme de deux nombres pairs ? de deux nombres impairs ?
Énoncer une règle sur la parité du produit de deux entiers et une règle sur la parité de la somme de deux entiers.

Pour un nombre pair, n=2k, son carré n²=(2k)²=4k²=2(2k²) est aussi pair.
De même, pour un nombre impair, n = 2k+1, son carré n² = (2k+1)² = 4k²+4k+1 = 2(2k²+2k)+1 est aussi impair.
Si n=2k et n'=2k' sont deux nombres pairs, alors le produit
nn'=(2k)(2k')=2(2kk')
est aussi pair.
De même, pour n=2k+1 et n'=2k'+1 deux nombres impairs, le produit
nn' =(2k+1)(2k'+1) =2(2kk'+k+k') + 1
est aussi impair.
Si n=2k et n'=2k' sont deux nombres pairs, alors la somme
n+n'=(2k) + (2k')=2(k+k')
est aussi paire.
Par contre, pour n=2k+1 et n'=2k'+1 deux nombres impairs, la somme
n+n' =(2k+1) + (2k'+1) =2(k + k' + 1)
est paire.
Le produit conserve la parité, tandis que l'addition de deux nombres de même parité est toujours paire.

Exercice 3 - Sur les puissances

Écrire sous la forme de produits et puissances, plus simples:
(5²)⁶ ; (2×3²)³ ; (2²ⁿ⁺¹)³
Factoriser:
2ⁿ⁺³−2ⁿ ; 3²ⁿ⁺¹ − 3ⁿ⁺¹ ; 4ⁿ⁺¹ − 2ⁿ⁺²

(5²)⁶ = 5¹² ; (2×3²)³ = 2³×3⁶ ; (2²ⁿ⁺¹)³ = 2⁶ⁿ⁺³
- 2ⁿ⁺³−2ⁿ = 2ⁿ(2³ −1) ;
- 3²ⁿ⁺¹ − 3ⁿ⁺¹ = 3ⁿ⁺¹(3ⁿ − 1) ;
- 4ⁿ⁺¹ − 2ⁿ⁺² = (2²)ⁿ⁺¹ − 2ⁿ⁺² = 2²ⁿ⁺² − 2ⁿ⁺² = 2ⁿ⁺²(2ⁿ − 1)

Introduction - A propos de N

L'arithmétique est la branche des mathématiques qui s'intéresse aux nombres entiers (naturels et relatifs), à leurs relations et propriétés en lien avec les opérations élémentaires: addition, soustraction, multiplication et division.
Tous les problèmes concernent donc ici l'ensemble des entiers naturels N ou celui des entiers relatif ℤ.

Axiomes de N

Principe du bon ordre: toute partie de N admet un plus petit élément
Principe de descente infinie: toute suite dans N strictement décroissante est finie.
Principe des tiroirs: si l’on range n + 1 chaussettes dans n tiroirs, alors un tiroir contiendra au moins deux chaussettes.

Remarques:

Le principe de bon ordre permet de donner une démonstration du principe de récurrence (qui devient alors un théorème de récurrence), voir la démonstration là
Le reste de la division par 7 d'un entier non multiple de 7 ne peut prendre que 6 valeurs: 1, 2, ...,6.
Ainsi, à partir de la 7ème division, on retrouve forcément un reste déjà obtenu (7 resultats dans 6 tiroirs).
Par exemple, on a 10/7 = 1, 42857 42857 42… est le développement est périodique.

Exercice 4

Je dispose de 100 chaussettes, 50 noires et 50 rouges, toutes mélangées en vrac.
Avoir une chaussette rouge à un pied et une noire à l’autre est particulièrement moche.
Combien dois-je en tirer, au minimum, pour être sûr d’avoir une paire de chaussettes de la même couleur ?

3…
n = 2 tiroirs, un pour les chaussettes rouges, un pour les noires.
Il suffit alors de ranger n+1 = 3 chaussettes pour qu'un des deux tiroirs en contienne au moins deux, c'est-à-dire 2 de la même couleur.

Divisibilité dans ℤ

Définition

Soit a et b deux entiers relatifs.
On dit que a divise b lorsque il existe un entier relatif k tel que b = ka.
On note a | b.
On dit aussi que a est un diviseur de b, ou encore que b est un multiple de a.

Exemples:

3 | 15 car 15 = 5×3 donc 3 divise 15, et 15 est un multiple de 3.
3 | −24 car −24 = 3×(−8) donc −8 et 3 sont des diviseurs de −24.
Tous les diviseurs de 24 dans N sont 1; 2; 3; 4; 8; 12; 24

Propriété: Rappels de règles de divisibilité

Un entier est divisible par 2 si et seulement si son chiffre des unités l'est, c'est-à-dire s'il se termnie par 0, 2, 4, 6 ou 8.
Un entier divisible par 2 est dit pair. S'il ne l'est pas, il est impair.
Un entier est divisible par 3 si et seulement si la somme de ses chiffres l'est
Un entier est divisible par 4 si et seulement si le nombre formé par ses deux derniers chiffres l'est
Un entier est divisible par 5 si et seulement si son chiffre des unités l'est, c'est-à-dire s'il se termnie par 0 ou 5
Un entier est divisible par 10 si et seulement si il est divisible à la fois par 2 et par 5, donc s'il se termine par 0.
Un entier est divisible par 9 si et seulement si la somme de ses chiffres l'est

Exercice 5

Donner les éventuels diviseurs parmi 2, 3, 4, 5, 9 et 10 des nombres suivants:
20 ; 54 ; 126 ; 1932 ; 2020 ; 2040 ; 10 ; 10004
Donner tous les diviseurs de:
20 ; 36 ; 54; 147

20 est divisible par 2, 4, 5 et 10.
54 est divisible par 2, 3, 9.
126 est divisible par 2, 3, 9.
1932 est divisible par 2, 3, 4.
2020 est divisible par 2, 4, 5, 10.
2040 est divisible par 2, 3, 4, 5, 10.
10004 est divisible par 2 seulement.
L'ensemble des diviseurs de 20 = 2²×5 est
{1; 2; 4; 5; 10; 20}

L'ensemble des diviseurs de 36 = 2²×3² est
{1; 2; 3; 4, 6, 9; 12; 18; 36}

L'ensemble des diviseurs de 54 = 2×3³ est
{1; 2; 3; 9; 18; 27; 54}

L'ensemble des diviseurs de 147 = 3×49 est
{1; 3; 49; 147}

Exercice 6

Déterminer tous les couples d’entiers naturels (x ; y) tels que x² − 2xy = 15
Déterminer tous les couples d’entiers naturels (x ; y) tels que 4x = 20 + 2xy

Ce qui nous intéresse particulièrement sont les multiples / diviseurs. On pense donc forcément à factoriser:
x² − 2xy = x(x−2y) = 15
ce qui montre que x et x−2y sont des diviseurs de 15, soit 1, 3, 5 ou 15.
Comme on cherche des entiers naturels, donc positifs, on a nécessairement que x est plus grand que x−2y et a donc deux possibilités: x = 15 x − 2y = 1 ou x = 5 x − 2y = 3
Le premier système donne x=15 et y=7 et le deuxième donne le couple solution x=5 et y=1
On procède de même qu'à la question précédente, en factorisant
4x = 20 + 2xy ⇔ 4x − 2xy = 2x(2−y)= 20 ⇔ x(2−y)= 10
ce qui montre que x et 2−y sont des diviseurs de 10, soit 1, 2, 5 ou 10.
Comme y est un etier naturel, donc positif, on a que 2−y est inférieur à 2, donc ne peut valoir que 1 ou 2, et on a donc les deux seules possibilités
- 2−y=1 ⇔ y=1 et alors x=10
- 2−y=2 ⇔ y=0 et alors x=5

Propriété: Divisibilité et combinaison linéraire

Si a | b et a | c alors, pour tous entiers relatifs α et β,

a | (α b + β c)

Exemples:

7 | 14 et 7 | 700 donc 7 | 728 car 728 = 2×14 + 1×700
Trouver une condition sur les diviseurs communs positifs à b = 3k+1 et c = 5k−2, pour un entier k quelconque.
Si a est un tel diviseur, alors a divise toute combinaison linéaire de b et c, en particulier, a divise
5b − 3c = 5(3k+1)−3(5k−2) = 11
Or 11 est premier: ses seuls diviseurs sont 1 lui-même.
Ainsi, un diviseur commun à b = 3k+1 et c = 5k−2 ne peut être que 1 ou 11.

Exercice 7

Déterminer, de deux manières différentes, les entiers naturels n tels que (n−3) divise (n+5).

en revenant à la définition de la divisibilité
en remarquant que (n−3) divise (n−3) et en faisant intervenir une combinaison linéaire judicieuse de (n−3) et (n+5).

(n−3) divise (n+5) signifie qu'il existe un entier k tel que (n+5) = k(n−3)
On cherche à factoriser, pour faire apparaître justement des produits et multiples, et on écrit pour cela que n+5 = n−3 +8
On obtient alors
(n+5) = k(n−3) ⇔ (n−3) +8 = k(n−3) ⇔ 8 = k(n−3) − (n−3) ⇔ 8 = (k−1)(n−3)
ce qui montre donc que (n−3) divise 8.
Or, les diviseurs de 8 sont 1; 2; 4; 8 et on a donc nécessairement que n−3=1 ⇔ n=4 ou n−3=2 ⇔ n=5 ou n−3=4 ⇔ n=7 ou enfin n−3=8 ⇔ n=11
Réciproquement, on vérifie bien que si n vaut 4, 5, 7 ou 11 alors n−3 divise bien n+5.
Comme n−3 divise n−3 et n+5, On sait que n−3 divise toute combinaison linéaire de n−3 et n+5 (d'après la propriété divisibilité et combinaison linéaire ci-dessus), c'est-à-dire que pour tous entiers α et β, on a que n−3 divise
α (n−3) + β (n+5)
On peut en particulier choisir les entiers qui nous intéressent, par exemple un choix qui fait disparaître l'nconnue n, par exemple, α=−1 et β=1.
On a alors dans ce cas que n−3 divise
α (n−3) + β (n+5) = −(n−3) + (n+5) = 8
et on retrouve donc ainsi, comme à la réponse précédente que n−3 divise 8.

Exercice 8

Pour quelles valeurs de l'entier naturel n a-t-on (n+8) divisible par n ?
Pour quelles valeurs de l'entier relatif n la fraction 6n+12/2n+1 est-elle un entier relatif ?

On peut soit traduire la divisibilité, soit utiliser une combinaison linéaire: comme n divise n et n+8, on sait alors que n divise
(n+8) − n = 8
donc que n∈ {1; 2; 4; 8}
Réciproquement, on vérifie que pour ces valeurs de n divise bien n+8.
Cette fraction est un entier lorsque le numérateur est un multiple du dénominateur, donc que 2n+1 divise 6n+12.
Comme à la question précédente, si 2n+1 divise 2n+1 et 6n+12 alors 2n+1 divise la combinaison linéaire
6n+12 − 3×(2n+1) = 9
et ainsi, 2n+1∈ {−9; −3; −1; 1; 3; 9} ou encore n∈ {−5; −2; −1; 0; 1; 4}
Réciproquement, on vérifie que ces six de valeurs de n donne bien une fraction réductible à un entier

Exercice 9

Montrer que si un entier naturel d divise 12n+7 et 3n+1 alors il divise 3.
En déduire que la fraction 12n+7/3n+1 est irréductible.

Comme d divise 12n+7 et 3n+1, on sait alors que n divise
(12n+7) − 4×(3n+1) = 3
donc d divise 3, c'est-à-dire que d∈ {1; 3}
Cette fraction est réductible si il existe un diviseur commun au numérateur et au dénominateur.
D'après la question précédente, ce diviseur divise aussi 3.
Or, 12n+7 ≡ 7 [3] ≡ 1 [3] n'est pas divisible par 3.
Il n'existe donc pas de diviseur commun, et la fraction est irréductible.

Division euclidienne

Soit a un entier relatif et b un entier naturel non nul.
Il existe alors un unique couple d'entiers relatifs (q ; r) tels que

a = bq + r avec 0≤ r < b

Revoir la division euclidienne posée

Exemples: Écrire les divisions euclidiennes de 112 par 5 puis de 86 par 7.

112 = 5 × 22 + 2, le quotient est 22 et le reste 2
86 = 7 × 12 + 2, le quotient est 12 et le reste 2

Exercice 10

Trouver les entiers naturels n qui ont, dans la division euclidienne par 4, un quotient égal au reste.

On écrit la division euclidienne, avec le reste égal au quotient, et le reste 0≤r=q<4

n = 4q + q = 5q

On trouve donc 4 valeurs possibles, pour q=0, ..., 3, à savoir

n = 0 (= 4×0+0),
n = 5 (= 4×1+1),
n = 10 (= 4×2+2),
et n = 15 (= 4×3+3).

Exercice 11

Trouver un entier naturel qui, dans la division euclidienne par 23 a pour reste 1, et dans la division euclidienne par 17 a le même quotient et pour reste 13.

On note n l'entier naturel recherché, et on a donc

n = 23q + 1 = 17q + 13

On doit donc avoir

6q = 12 ⇔ q=2

d'où

n = 23×2 + 1 = 17×2 + 13 = 47

Exercice 12

La différence de deux entiers naturels est 885. Si on divise l'un par l'autre, le quotient est 29 et le reste 17.
Quels sont ces deux entiers ?

On note n et m ces deux entiers, qui vérifient donc n−m = 885 et

n = 29m + 17

On a donc

n = m + 885 = 29m + 17

et donc

868 = 28m ⇔ m = 31

et alors n−m = 885 ⇔ n = 916

Exercice 13

Un entier naturel n est tel que si on le divise par 5 le reste vaut 3 et si on le divise par 6 le reste augmente de 1 et le quotient diminue de 1. Déterminer n.

On a donc d'une part

n = 5q + 3

et d'autre part

n = 6(q−1) + 4

d'où la relation

5q + 3 = 6(q−1) + 4

de laquelle on tire q = 5 et donc

n = 5×5 + 3 = 6×4 + 4 = 28

Exercice 14

Soit n et p deux entiers naturels. On sait que le reste dans la division euclidienne de n par 11 vaut 8 et que le reste dans la division euclidienne de p par 11 vaut 7. Quel est le reste de n+p dans la division euclidienne par 11 ?

On détaille les divisions euclidiennes:

n = 11q + 8

p = 11q' + 7

et alors, en ajoutant terme à terme ces deux équations

n+p = 11(q+q') + 15

Cette dernière relation n'est par contre pas la division euclidienne de p par 11 puisque le reste 15>11.
Il faut diminuer ce reste en ajoutant 1 au quotient:

n+p = 11(q+q'+1) + 4

et le reste recherché est donc de 4.

Congruences

Définition - Relation d'équivalence

Définition:

Soit a et b deux entiers relatifs et n≥2 un entier naturel.
On dit que a et b sont congrus modulo n lorsque a et b ont le même reste dans la division euclidienne par n.
On note

a≡b [n] ou a≡ b mod n

Exemples:

47 = 9×5 +2 et 32 = 6×5 + 2 d'où 47≡32 [5]
En fait, 47≡2 [5] et 32≡2 [5]
40≡0 [2] car 40=20×2 + 0.
"Congru à 0 modulo n " signifie "divisible par n"
"Congru à 0 modulo 2" signifie "pair"
−3≡4 [7] car −3= -1×7+4

Corollaires:

Tout nombre est congru à son reste dans la division euclidienne: si a = bq + r alors a≡ r [q]
n est un diviseur de a si et seulement si a≡0 [n] (⇔ a=qn+0)
Un nombre a est pair si et seulement si a≡0 [2]
a est impair si et seulement si a≡1 [2]
a≡ b [n] ⇔ a−b≡ 0 [n]

Congruences et opérations

Il est important de savoir comment se comportent les opérations usuelles avec les congruences.

Propriétés:

Soit a, b, c et d des entiers relatifs, et n>2 un entier naturel.
Si a ≡ b [n] et c ≡ d [n] alors
- a + c ≡ b + d [n] (addition terme à terme)
- a − c ≡ b − d [n] (soustraction terme à terme)
- ac ≡ bd [n] (multiplication terme à terme)
- En particulier, pour tout entier p, on a a^p ≡ b^p [n]

Exercice 15

Donner le reste de la division euclidienne de 4² par 15.
En déduire que que 4⁶ⁿ−1 est divisible par 15.

On a 4²=16≡1 [15].
On a alors,

4⁶ⁿ = (4²)³ⁿ≡1³ⁿ [15]

d'où

4⁶ⁿ≡1 [15]

et donc

4⁶ⁿ − 1 ≡0 [15]

ce qui signifie exactement que 4⁶ⁿ−1 est divisible par 15.

Exercice 16

Déterminer le reste de la division euclidienne de 39⁶⁰ par 7.

On a 39≡4 [7],
donc 39²≡4² [7] ≡ 2 [7],
donc 39³=39²×39≡2×4 [7] ≡ 1 [7].

On cherche donc à diviser par 3 la puissance de 39:

39⁶⁰=(39³)²⁰ ≡ 1²⁰ [7] ≡ 1 [7]

Ainsi, le reste recherché, de la division euclidienne de 39⁶⁰ par 7, est 1.

Exercice 17

Déterminer le chiffre des unités dans l'écriture décimale de 3²⁰²³.

Le chiffre des unités est le reste modulo 10.
Ici, 3²=9≡−1[10], et on cherche donc la parité de la puissance:

3²⁰²³ = 3^2×1011+1 = (3²)¹⁰¹¹×3 ≡ (−1)¹⁰¹¹×3 [10] ≡−3 [10] ≡7 [10]

Exercice 18

Déterminer, suivant les valeurs de n, les restes possibles de 2ⁿ dans la division par 9. Résumer les résultats dans un tableau de congruence.
En déduire les entiers n tels que 2ⁿ−1 est divisible par 9.

On remplit successivement le tableau de congruence:

n=… 0 1 2 3 4 5 6

2ⁿ≡ … [9] 1 2 4 8 7 5 1

et on trouve une période de 6.
On a
2ⁿ − 1 ≡ 0 [9] ⇔ 2ⁿ ≡ 1 [9]
et grâce au tableau précédent, on a donc
2ⁿ − 1 ≡ 0 [9] ⇔ n≡0 [6]
donc lorsque n est un multiple de 6.

Exercice 19

Déterminer, suivant les valeurs de n, les restes possibles de 3ⁿ dans la division par 7. Résumer les résultats dans un tableau de congruence.
En déduire les entiers n tels que 3ⁿ−6 est divisible par 7.
En déduire que 164²⁰²¹≡5 [7].

On remplit successivement le tableau de congruence:

n=… 0 1 2 3 4 5 6

3ⁿ≡ … [7] 1 3 2 6 4 5 1

et on trouve une période de 6.
On a
3ⁿ − 6 ≡ 0 [7] ⇔ 3ⁿ ≡ 6 [7]
et grâce au tableau précédent, on a donc
3ⁿ − 6 ≡ 0 [7] ⇔ n≡3 [6]
On peut démontrer ce résultat: n≡3 [6] ⇔ n = 6k + 3 , k∈>N et alors
3ⁿ = 3^{6k + 3} = (3⁶)^k 3³
or on a déjà calculé dans le tableau précédent que 3⁶ ≡ 1 [7] et 3³ ≡ 6 [7].
On en déduit que
3ⁿ = (3⁶)^k 3³ ≡ 1^k×6 [7] ≡ 6 [7]
ce qui est bien le résultat recherché.
On a 164=7×23+3 donc 164≡3 [7] et alors
164²⁰²¹≡3²⁰²¹ [7]
On divise (euclidienne) alors la puissance 2021 par 6, soit
2021=6×336+5 ⇒ 2021≡5 [6]
et alors
164²⁰¹²≡3²⁰¹² [7] ≡ 3⁵ [7] ≡ 5 [7]

Exercice 20

Le 1er janvier 2012 était un dimanche.

Calculer le nombre de jours séparant ce 1er janvier 2012 du 1er janvier 2019.
En déduire quel était le jour de la semaine du 1er janvier 2019.
Quel est le jour de la semaine du 1er janvier 2030 ?

Entre ces deux dates, il y a 7 ans, soit 7×365 jours, auquels il faut ajouter les jours de plus des années bissextiles.
Ce sont les années divisibles par 4. 2012 est une telle année et 2016 aussi.
Il y a donc en tout 7×365 + 2 jours entre les 1er janvier 2012 et 2019, et donc
7×365 + 2 ≡ 0×365 +2 [7] ≡2 [7]
Ainsi, il y a deux jours de la semaine de plus, et le 1er janvier 2019 était donc un mardi.
De même, il y a 11 ans entre les 1er janvier 2019 et 2030, dont 3 années bissextiles, soit n=11×365 + 3 jours.
Comme, avec 52 semaines par an,
365 = 7×52 + 1 ≡ 1 [7]
on obtient que
n≡4×1 + 3 [7] ≡ 0 [7]
et le 1er janvier 2030 donc le même jour de la semaine que le 1er janvier 2019, donc un mardi.

Exercice 21

On appelle inverse de x modulo 5, un entier y tel que xy≡1 [5].

Déterminer un inverse modulo 5 de x=2.
Déterminer un inverse modulo 5 de x=3 et x=4.
Est-ce que x=5 admet un inverse ?
&Acute; l'aide d'un tableau de congruence, déterminer suivant la valeur de x son inverse modulo 5.
Résoudre les équations
- E₁: 2x≡ 3 [5]
- E₂: 9x≡ 1 [5]

On a 2×3=6≡1 [5], d'où y=3 est un inverse modulo 5 de x=2.
De même y=2 est un inverse modulo 5 de x=3.
On a aussi 4×4=16≡1 [5], d'où y=4 est un inverse modulo 5 de x=4.
x=5 n'a pas d'inverse car x=5≡0 [5] et donc, pour tout nombre y on a xy≡0 [5] et on ne peut donc pas avoir xy≡1 [5].
On peut donc remplir le tableau de congruence:

x≡… [5] 0 1 2 3 4

Inverse modulo 5 de x × 1 3 2 4
- On multiplie des deux côtés par l'inverse modulo 5: E₁: 2x≡ 3 [5] ⇒ 3×2x≡ 3×3 [5] ≡4 [5] or 3×2x≡x [5]
  et on trouve finalement que les solutions sont x≡4 [5]
- Tout d'abord 9x≡4x [5] . Puis, on procède comme pour l'équation précédente. On multiplie des deux côtés par l'inverse modulo 5: E₂: 4x≡ 1 [5] ⇒ 4×4x≡ 4×1 [5] ≡4 [5] or 4×4x≡x [5]
  et on trouve finalement que les solutions sont x≡4 [5] et les solutions sont donc les mêmes que pour l'équation précédente.

Exercice 22

On décide de former des nombres dans le système décimal en écrivant de gauche à droite quatre chiffres consécutifs dans l'ordre croissant puis on permute les deux premiers chiffres de gauche.
Par exemple, à partir de 4567 on obtient 5467, ou encore à partir de 2345 on obtient 3245.
Démontrer que tous les entiers naturels ainsi obtenus sont multiples de 11.

On détaille l'écriture décimale des nombres, avant la permutation, qui s'écrivent donc

a = n×10³+(n+1)×10²+(n+2)×10+(n+3)

Après permutation, on obtient le nombre

a' = (n+1)×10³+n×10²+(n+2)×10+(n+3)

et donc, comme 10≡−1 [11], on trouve que

a' ≡ (n+1)×(−1)³ + n×(−1)² + (n+2)×(−1) + (n+3) [11] ≡ (n+1)×(−1) + n×(1) + (n+2)×(−1) + (n+3) [11] ≡ 0 [11]

ce qui montre que ce nopmbre obtenu est bien multiple de 11.

Exercice 23

On considère un entier de 3 chiffres. On appelle renversé de cet entier le nombre qui s'écrit en échangeant les chiffres des centaines et des unités.
Par exemple, le renversé de 238 est 832.
Montrer que la différence entre un entier et son renversé est divisible par 9.

Soit n un entier à 3 chiffres, qu'on écrit sous forme décimale

n = a×100 + b×10 + c

Son renversé est

n' = c×100 + b×10 + a

et leur différence

n−n' = (a−c)×100 + c−a

et donc, comme 100≡1[9], on obtient que

n−n' ≡ (a−c)×1 + c−a [9] ≡0 [9]

ce qui signifie exactement que cette différence est divisible par 9.

Exercice 24

On considère la suite (u_n) d'entiers définie par u₀=14 et, pour tout entier naturel n,

u_n+1 = 5 u_n − 6

Calculer u₁, u₂, u₃ et u₄.
Quelle conjecture peut-on faire concernant les deux derniers chiffres de u_n ?
Montrer que, pour tout entier n, on a u_n+2≡ u_n [4].
En déduire que, pour tout entier n, on a u_2n≡ 2 [4] et u_2n+1≡0 [4].
1. Montrer par récurrence que pour tout entier naturel n, on a 2u_n = 5ⁿ⁺²+3.
2. En déduire que, pour tout entier naturel n, 2u_n≡ 28 [100].
3. Déterminer les deux derniers chiffres de l'écriture décimale de u_n suivant les valeurs de n.

u₀ = 14, u₁ = 64, u₂ = 314, u₃ = 1564, et u₄ = 7314.
On peut donc conjecturer que les deux derniers chiffres alternent entre 14 et 64.
On a
u_n+2 = 5 u_n+1 − 6
donc
u_n+2 = 5 (5 u_n − 6) − 6 = 25u_n − 36
et comme 25≡1 [4] et 36≡0 [4], on obtient donc que
u_n+2≡ u_n [4]
On en déduit que, en considérant les termes de rang pair,
u_2n≡u_2(n−1)≡ … ≡ u₀≡2 [4]
et les termes de rang impair,
u_2n+1≡u_2n−1≡ … ≡ u₁≡0 [4]
1. Initialisation: d'une part, 2u₀ = 28 et d'autre part 5⁰⁺²+3=28, ce qui montre que la propriété est vraie initialement au rang n=0.
  Hérédité: Supposons que pour un certain entier n on ait 2u_n = 5ⁿ⁺²+3
  Alors, par définition de la suite,
  2u_n+1 = 2(5u_n−6) = 5(2u_n)−12
  et, en utilisant l'hypothèse de récurrence,
  2u_n+1 = 5(5ⁿ⁺²+3) − 12
  soit
  2u_n+1 = 5ⁿ⁺³ + 3
  ce qui montre que la propriété est encore vraie au rang n+1 suivant.
  Conclusion: on vient donc de démontrer, d'après le principe de récurrence, que pour tout entier natiurel n, on a
  2u_n = 5ⁿ⁺²+3
2. On a, 5³=125≡25 [100] puis 5⁴=5×5³≡5×25 [100]≡25 [100] et, de proche en proche (ou par une récurrence immédiate), pour tout entier n, on a
  5ⁱ⁺²≡25 [100]
  et donc,
  2u_n = 5ⁿ⁺²+3 ≡ 25 +3 [100] ≡ 28 [100]
3. On a ainsi trouvé que u_n≡14 [50] c'est-à-dire que les deux chiffres de u_n sont 14 ou 14+50=64, et démontre ainsi notre conjecture.

Voir aussi:

n=…	0	1	2	3	4	5	6
2ⁿ≡ … [9]	1	2	4	8	7	5	1

n=…	0	1	2	3	4	5	6
3ⁿ≡ … [7]	1	3	2	6	4	5	1

x≡… [5]	0	1	2	3	4
Inverse modulo 5 de x	×	1	3	2	4