|

Exercices pour les élèves motivés : arithmétique (Maths expertes)

↩ Chapitre : Arithmétique (Maths expertes)

Introduction

Six exercices exigeants d’arithmétique, pour les élèves qui maîtrisent déjà le cours et la fiche d’exercices corrigés du chapitre : trois exercices ★★★ et trois exercices ★★★★, dont deux de niveau première année de prépa (ECG et MPSI-PCSI). Tout se fait avec le programme de Maths expertes : divisibilité, division euclidienne, congruences, PGCD, théorèmes de Bézout et de Gauss, nombres premiers et petit théorème de Fermat.

Mode d’emploi : cherchez chaque exercice au moins vingt minutes avant d’ouvrir les Indications, puis cherchez encore avant de lire le Corrigé. Les exercices ★★★ sont du niveau des questions les plus difficiles du bac ; les exercices ★★★★ demandent davantage d’initiative, et les deux derniers sont du niveau d’une première année de classe préparatoire, tout en restant dans le programme du chapitre.

Exercices

Exercice 1 · Congruences et divisibilité ★★★★

  1. Montrer que, pour tout entier naturel n, 3^{2n+1}+2^{n+2} est divisible par 7.
  2. Déterminer le reste de la division euclidienne de 2^{2026} par 7.
  3. Démontrer qu’un entier est divisible par 11 si et seulement si la somme alternée de ses chiffres (chiffre des unités moins chiffre des dizaines plus chiffre des centaines, etc.) l’est. Le nombre 918\,082 est-il divisible par 11 ?
  4. Déterminer les entiers n tels que n^2+n+1 soit divisible par 7.
Indications

1. 9\equiv2\ [7].

2. 2^3\equiv1\ [7].

3. 10\equiv-1\ [11].

4. Tableau des restes modulo 7.

Corrigé

1. 3^{2n+1}=3\times9^n\equiv3\times2^n\ [7] et 2^{n+2}=4\times2^n. La somme est congrue à 7\times2^n\equiv0\ [7].

2. 2026=3\times675+1, donc 2^{2026}=(2^3)^{675}\times2\equiv2\ [7] : le reste est 2.

3. Si N=\sum a_k10^k, alors N\equiv\sum a_k(-1)^k\ [11]. Pour 918\,082 : 2-8+0-8+1-9=-22\equiv0 : oui, 918\,082=11\times83\,462.

4. Pour n\equiv0,1,\dots,6, n^2+n+1\equiv1,3,0,6,0,3,1\ [7].

⇝ 7\mid n^2+n+1\iff n\equiv2\ [7] ou n\equiv4\ [7].

Exercice 2 · Une équation diophantienne ★★★★

  1. Justifier que l’équation 7x+12y=1 admet des solutions entières et en trouver une.
  2. Déterminer toutes les solutions entières de 7x+12y=1.
  3. En déduire toutes les solutions entières de 7x+12y=100.
  4. Un client dépense exactement 100 € en achetant des articles à 7 € et des articles à 12 €. Combien a-t-il acheté de chaque ?
Indications

1. 7 et 12 sont premiers entre eux ; algorithme d’Euclide.

2. Soustraire l’égalité obtenue pour la solution particulière, puis appliquer le théorème de Gauss.

4. Imposer x\geqslant0 et y\geqslant0.

Corrigé

1. PGCD(7\,;12)=1 : Bézout assure l’existence. 12=7+5, 7=5+2, 5=2\times2+1, d’où en remontant 7\times(-5)+12\times3=1.

2. Si 7x+12y=1, alors 7(x+5)=-12(y-3). 7 divise 12(y-3) et est premier avec 12 : 7\mid y-3, y=3-7k, puis x=-5+12k. Réciproquement, ces couples conviennent.

3. (-500\,;300) est solution, et de même : x=-500+12k, y=300-7k, k\in\mathbb Z.

4. x\geqslant0\iff k\geqslant\frac{500}{12}, soit k\geqslant42 ; y\geqslant0\iff k\leqslant\frac{300}7, soit k\leqslant42. Donc k=42 :

⇝ 4 articles à 7 € et 6 articles à 12 € (28+72=100).

Exercice 3 · PGCD dépendant d’un paramètre ★★★★

Soit n un entier naturel.

  1. Montrer que n et n+1 sont premiers entre eux, ainsi que 2n+1 et 3n+2.
  2. Montrer que PGCD(n+3\,;2n+1) divise 5.
  3. Déterminer les valeurs de n pour lesquelles PGCD(n+3\,;2n+1)=5.
  4. Pour quelles valeurs de n la fraction \frac{2n+1}{n+3} est-elle irréductible ?
Indications

1 et 2. Un diviseur commun divise toute combinaison linéaire : chercher une combinaison simple.

3. 5 divise n+3 si et seulement si n\equiv2\ [5].

Corrigé

1. (n+1)-n=1 et 3(2n+1)-2(3n+2)=-1 : tout diviseur commun divise 1.

2. 2(n+3)-(2n+1)=5.

3. Le PGCD vaut 1 ou 5. Il vaut 5 si et seulement si 5 divise n+3 et 2n+1. Or si 5\mid n+3, alors n\equiv2\ [5] et 2n+1\equiv5\equiv0\ [5].

⇝ PGCD(n+3\,;2n+1)=5\iff n\equiv2\ [5].

4. Irréductible si et seulement si n\not\equiv2\ [5]. Par exemple pour n=2 : \frac55.

Exercice 4 · Le petit théorème de Fermat au travail ★★★★

  1. Énoncer le petit théorème de Fermat.
  2. Montrer que, pour tout entier n, n^5-n est divisible par 30.
  3. En déduire que n et n^5 ont le même chiffre des unités.
  4. Déterminer le reste de la division de 3^{2026} par 13.
  5. Montrer que, pour tout entier n, n^{13}-n est divisible par 2730=2\times3\times5\times7\times13.
Indications

2. 30=2\times3\times5, nombres premiers deux à deux distincts. Pour 2 et 3, factoriser n^5-n=n(n-1)(n+1)(n^2+1).

4. 3^{12}\equiv1\ [13] ; on peut même trouver un exposant plus petit.

5. Pour p\in\{2,3,5,7,13\}, p-1 divise 12.

Corrigé

1. Si p est premier, n^p\equiv n\ [p] pour tout entier n ; si de plus p\nmid n, n^{p-1}\equiv1\ [p].

2. Fermat avec p=5 : 5\mid n^5-n. De plus n^5-n=(n-1)n(n+1)(n^2+1) contient le produit de trois entiers consécutifs, divisible par 2 et par 3. Comme 2, 3, 5 sont premiers entre eux, 30\mid n^5-n.

3. 10\mid n^5-n : n^5\equiv n\ [10].

4. 3^3=27\equiv1\ [13] et 2026=3\times675+1, donc 3^{2026}\equiv3\ [13].

5. Pour p premier avec p-1\mid12 : si p\mid n, p\mid n^{13}-n ; sinon n^{p-1}\equiv1, donc n^{12}\equiv1 et n^{13}\equiv n\ [p]. C’est vrai pour p=2,3,5,7,13, premiers distincts : leur produit 2730 divise n^{13}-n.

Exercice 5 · Chiffrement affine ★★★★ — niveau prépa ECG

On numérote les lettres de A à Z par les entiers de 0 à 25. Une lettre de numéro x est codée par la lettre de numéro y, reste de 7x+3 modulo 26.

  1. Coder le mot MATHS.
  2. Trouver un entier a' tel que 7a'\equiv1\ [26]. En déduire que y\equiv7x+3\ [26] équivaut à x\equiv a'(y-3)\ [26].
  3. Décoder le mot KSDUX.
  4. Plus généralement, on code par y\equiv ax+b\ [26]. Montrer que le codage est réversible (deux lettres distinctes donnent deux codes distincts) si et seulement si a est premier avec 26. Combien y a-t-il de clés (a\,;b) utilisables ?
  5. Écrire une fonction Python qui décode un mot en majuscules pour une clé (a\,;b) donnée.
Indications

2. Bézout : 7\times15=105=4\times26+1.

4. Si a est premier avec 26, a a un inverse modulo 26. Sinon, trouver x\neq0 tel que ax\equiv0\ [26].

Corrigé

1. M=12\mapsto87\equiv9 : J. A=0\mapsto3 : D. T=19\mapsto136\equiv6 : G. H=7\mapsto52\equiv0 : A. S=18\mapsto129\equiv25 : Z. Le mot codé est JDGAZ.

2. a'=15. Si y\equiv7x+3, alors 15(y-3)\equiv105x\equiv x\ [26], et réciproquement en multipliant par 7.

3. K=10 : 15\times7=105\equiv1 : B. S=18 : 15\times15=225\equiv17 : R. D=3 : 0 : A. U=20 : 15\times17=255\equiv21 : V. X=23 : 15\times20=300\equiv14 : O. Le mot clair est BRAVO.

4. Si PGCD(a\,;26)=1, a a un inverse modulo 26 et on décode comme ci-dessus. Si PGCD(a\,;26)=d > 1, alors x=\frac{26}d\in\{1,\dots,25\} vérifie ax\equiv0, et les lettres de numéros 0 et x ont le même code. Les a premiers avec 26=2\times13 sont les 12 impairs différents de 13 :

⇝ 12\times26=312 clés utilisables.

def decode(mot, a, b):
inv = next(u for u in range(26) if a * u % 26 == 1)
return ''.join(chr(inv * (ord(c) - 65 - b) % 26 + 65) for c in mot)

print(decode('JDGAZ', 7, 3)) # MATHS

Exercice 6 · Infinité de nombres premiers de la forme 4k+3 ★★★★ — niveau prépa MPSI-PCSI

  1. Rappeler pourquoi il existe une infinité de nombres premiers (démonstration d’Euclide).
  2. Montrer qu’un nombre premier impair est congru à 1 ou à 3 modulo 4, et qu’un produit d’entiers tous congrus à 1 modulo 4 est congru à 1 modulo 4.
  3. On suppose qu’il n’existe qu’un nombre fini de nombres premiers congrus à 3 modulo 4 : p_1,\dots,p_r. On pose N=4p_1p_2\cdots p_r-1. Montrer que N admet un diviseur premier q\equiv3\ [4].
  4. Conclure.
  5. Pourquoi la même méthode échoue-t-elle à montrer directement qu’il y a une infinité de nombres premiers de la forme 4k+1 ?
Indications

1. Considérer p_1\cdots p_r+1.

3. N est impair et N\equiv3\ [4] ; décomposer N en facteurs premiers.

5. Un produit de nombres \equiv3\ [4] peut être \equiv1\ [4].

Corrigé

1. Si p_1,\dots,p_r étaient tous les nombres premiers, p_1\cdots p_r+1 > 1 aurait un diviseur premier p_i, qui diviserait aussi 1 : absurde.

2. Un impair est congru à 1 ou 3 modulo 4. Si a\equiv b\equiv1, alors ab\equiv1\ [4], et par récurrence pour un produit quelconque.

3. N\equiv-1\equiv3\ [4], donc N est impair et N > 1. Ses facteurs premiers sont impairs ; s’ils étaient tous \equiv1\ [4], on aurait N\equiv1\ [4]. Donc l’un d’eux, q, vérifie q\equiv3\ [4].

4. Alors q est l’un des p_i, donc q\mid4p_1\cdots p_r et q\mid N, d’où q\mid1 : absurde. Il y a une infinité de nombres premiers de la forme 4k+3.

5. Un nombre \equiv1\ [4] peut n’avoir que des facteurs \equiv3\ [4] (exemple : 21=3\times7). L’argument ne garantit donc pas l’existence d’un nouveau facteur \equiv1\ [4] ; le résultat est vrai, mais sa preuve demande d’autres outils (par exemple n^2+1 et le petit théorème de Fermat).


Pour aller plus loin

Besoin d’aide sur ce chapitre, ou envie de viser plus haut ?

Un blocage sur une notion, un contrôle à préparer — ou l’ambition d’une mention au Bac et d’une bonne prépa : Pr. Elakili, agrégé de mathématiques depuis 1991, propose des cours particuliers aux lycéens (Première, Terminale, Maths expertes), en présentiel à Casablanca, ou à distance, partout au Maroc et en France.

🎯 Objectif : réussir son Bac, viser la mention et arriver dans le supérieur avec une formation solide.

Publications similaires