Devoir sur 20 : Arithmétique

Séries S1, S3 et S1A. Devoir d'une heure, sur 20 points. Calculatrice non nécessaire : les restes se calculent avec les congruences. Seuil proposé : 10/20. Corrigé et barème à la fin.

Sujet

Exercice 1 (7 points)

Déterminer les restes de la division euclidienne par $13$ de $5^1$ , $5^2$ , $5^3$ et $5^4$ . (2 points)
En déduire le reste de $5^{2\,026}$ dans la division par $13$ . (1,5 point)
Montrer que, pour tout entier naturel $n$ , $5^{4n + 1} + 8$ est divisible par $13$ . (1,5 point)
Justifier que $13$ est premier. Que donne le petit théorème de Fermat pour $5^{12}$ ? Est-ce cohérent avec la question 1 ? (1 point)
Le 4 novembre 2026 est un mercredi. Quel jour de la semaine serons-nous $2\,026$ jours plus tard ? (1 point)

Exercice 2 (8 points)

Calculer $\mathrm{PGCD}(221\,;65)$ par l'algorithme d'Euclide. (1,5 point)
L'équation $221x + 65y = 30$ a-t-elle des solutions dans $\mathbb{Z}^2$ ? Justifier. (1 point)
On considère l'équation $(E)$ : $221x + 65y = 26$ , d'inconnue $(x\,;y) \in \mathbb{Z}^2$ .
a. Montrer que $(E)$ équivaut à $17x + 5y = 2$ . (1 point)
b. Vérifier que le couple $(1\,;-3)$ est solution de $(E)$ . (0,5 point)
c. Résoudre $(E)$ dans $\mathbb{Z}^2$ . (2,5 points)
d. En déduire les entiers relatifs $x$ tels que $17x \equiv 2 \;[5]$ . (1,5 point)

Exercice 3 (5 points)

Décomposer $1\,260$ et $756$ en produit de facteurs premiers. (1 point)
En déduire $\mathrm{PGCD}(1\,260\,;756)$ et $\mathrm{PPCM}(1\,260\,;756)$ . (1,5 point)
Écrire $1\,260$ en base deux, puis en base seize. (1,5 point)
Écrire en base dix le nombre $\overline{2310}^{\,5}$ . (1 point)

Corrigé et barème (après avoir cherché)

Exercice 1

1. (2 pts) $5 \equiv 5$ ; $5^2 = 25 = 13 + 12$ , donc $5^2 \equiv 12$ ; $5^3 \equiv 5 \times 12 = 60 = 13 \times 4 + 8$ , donc $5^3 \equiv 8$ ; $5^4 \equiv 5 \times 8 = 40 = 13 \times 3 + 1$ , donc $5^4 \equiv 1 \;[13]$ . Les restes sont $5$ , $12$ , $8$ et $1$ . (0,5 pt par reste)

2. (1,5 pt) (0,5 pt) $2\,026 = 4 \times 506 + 2$ . (1 pt) $5^{2\,026} = (5^4)^{506} \times 5^2 \equiv 1 \times 12 \;[13]$ : le reste est $12$ .

3. (1,5 pt) (1 pt) $5^{4n + 1} = (5^4)^n \times 5 \equiv 5 \;[13]$ . (0,5 pt) Donc $5^{4n + 1} + 8 \equiv 13 \equiv 0 \;[13]$ .

4. (1 pt) (0,5 pt) $13$ n'est divisible ni par $2$ ni par $3$ , et $4^2 > 13$ : il est premier. (0,5 pt) $13$ ne divise pas $5$ , donc $5^{12} \equiv 1 \;[13]$ . C'est cohérent : $5^{12} = (5^4)^3 \equiv 1 \;[13]$ .

5. (1 pt) $2\,026 = 7 \times 289 + 3$ : on avance de $3$ jours à partir du mercredi, ce sera un samedi.

Exercice 2

1. (1,5 pt) $221 = 65 \times 3 + 26$ ; $65 = 26 \times 2 + 13$ ; $26 = 13 \times 2 + 0$ . Le dernier reste non nul est $13$ : $\mathrm{PGCD}(221\,;65) = 13$ .

2. (1 pt) Pour tous entiers $x$ et $y$ , $221x + 65y$ est un multiple de $13$ ; or $13$ ne divise pas $30$ . Il n'y a pas de solution.

3.a. (1 pt) $221 = 13 \times 17$ , $65 = 13 \times 5$ et $26 = 13 \times 2$ . On divise les deux membres par $13 \neq 0$ : $(E)$ équivaut à $17x + 5y = 2$ .

3.b. (0,5 pt) $17 \times 1 + 5 \times (-3) = 17 - 15 = 2$ .

3.c. (2,5 pts)

(1 pt) Si $(x\,;y)$ est solution, on soustrait $17 \times 1 + 5 \times (-3) = 2$ : $17(x - 1) = 5(-3 - y)$ .
(1 pt) $5$ divise $17(x - 1)$ et $\mathrm{PGCD}(5\,;17) = 1$ ; d'après le théorème de Gauss, $5$ divise $x - 1$ : $x = 1 + 5k$ , $k \in \mathbb{Z}$ . Alors $17 \times 5k = 5(-3 - y)$ , d'où $y = -3 - 17k$ .
(0,5 pt) Réciproquement, $17(1 + 5k) + 5(-3 - 17k) = 2$ . Les solutions sont les couples $(1 + 5k\,;-3 - 17k)$ , $k \in \mathbb{Z}$ .

3.d. (1,5 pt) (1 pt) $17x \equiv 2 \;[5]$ équivaut à : il existe un entier $m$ tel que $17x - 2 = 5m$ , c'est-à-dire, en posant $y = -m$ , $17x + 5y = 2$ . (0,5 pt) D'après la question c, c'est le cas si, et seulement si, $x = 1 + 5k$ : les solutions sont les entiers $x \equiv 1 \;[5]$ . On peut aussi remarquer que $17 \equiv 2 \;[5]$ , donc $2x \equiv 2 \;[5]$ , et multiplier par $3$ , car $2 \times 3 \equiv 1 \;[5]$ .

Exercice 3

1. (1 pt) $1\,260 = 2^2 \times 3^2 \times 5 \times 7$ et $756 = 2^2 \times 3^3 \times 7$ .

2. (1,5 pt) (0,75 pt) $\mathrm{PGCD} = 2^2 \times 3^2 \times 7 = 252$ . (0,75 pt) $\mathrm{PPCM} = 2^2 \times 3^3 \times 5 \times 7 = 3\,780$ . Contrôle : $252 \times 3\,780 = 952\,560 = 1\,260 \times 756$ .

3. (1,5 pt) (1 pt) Divisions successives par $2$ : $1\,260 = \overline{10011101100}^{\,2}$ ( $1\,024 + 128 + 64 + 32 + 8 + 4$ ). (0,5 pt) Divisions par $16$ : $1\,260 = 16 \times 78 + 12$ , $78 = 16 \times 4 + 14$ , $4 = 16 \times 0 + 4$ , donc $1\,260 = \overline{4\mathrm{EC}}^{\,16}$ . On peut aussi grouper les chiffres binaires par quatre : $100\ 1110\ 1100$ donne $4$ , $\mathrm{E}$ , $\mathrm{C}$ .

4. (1 pt) $\overline{2310}^{\,5} = 2 \times 125 + 3 \times 25 + 1 \times 5 + 0 = 330$ .

Compétences évaluées

Question	Compétence (objectif de la fiche du chapitre)
Ex. 1, 1 à 3 et 5	O3 Utiliser les congruences pour calculer des restes et résoudre des problèmes
Ex. 1, 4	O9 et O11 Reconnaître un nombre premier ; petit théorème de Fermat
Ex. 2, 1	O4 PGCD par l'algorithme d'Euclide
Ex. 2, 2 et 3	O7 et O8 Théorème de Gauss ; équations $ax + by = c$
Ex. 2, 3.d	O3 Congruences et équations
Ex. 3, 1 et 2	O4, O9 et O10 Décomposition, PGCD et PPCM
Ex. 3, 3 et 4	O12 Numération en bases deux, cinq et seize