Exercices — Arithmétique

On rappelle que, pour deux entiers relatifs $a$ et $b$, on dit que $b$ divise $a$, et on note $b\mid a$, lorsqu'il existe un entier relatif $k$ tel que $a=kb$. On dit alors que $a$ est un multiple de $b$, ou que $b$ est un diviseur de $a$.

1. Dresser la liste des diviseurs positifs de chacun des entiers suivants :

   a. $24$

   b. $45$

   c. $28$

2. Dresser la liste de tous les diviseurs de $10$ dans $\mathbb{Z}$.

3. Pour chacune des affirmations suivantes, dire si elle est vraie ou fausse, en justifiant à chaque fois par une égalité ou une division :

   a. $7\mid 91$

   b. $8\mid 100$

   c. $-6\mid 54$

   d. $13\mid -78$

   e. $5\mid 0$

   f. $1\mid -17$

4. Soit $n$ un entier relatif.

   a. Montrer que la somme de trois entiers consécutifs $n$, $n+1$ et $n+2$ est divisible par $3$.

   b. Montrer que $(2n+1{)}^2-1$ est divisible par $4$.

Dans tout l'exercice, $a$, $b$ et $d$ désignent des entiers relatifs, avec $d$ non nul.

1. Démontrer la propriété suivante : si $d\mid a$ et $d\mid b$, alors pour tous entiers relatifs $u$ et $v$, on a $d\mid (au+bv)$. On dit que $d$ divise toute combinaison linéaire de $a$ et $b$.

2. Soit $n$ un entier relatif et soit $d$ un diviseur commun à $2n+3$ et à $n+1$.

   a. En choisissant une combinaison linéaire bien adaptée de $2n+3$ et de $n+1$, montrer que $d\mid 1$.

   b. Que peut-on en déduire sur les diviseurs communs à $2n+3$ et $n+1$ ?

3. On cherche tous les entiers relatifs $n$ tels que $(n+2)\mid (n^2+3n+7)$.

   a. Vérifier que, pour tout entier relatif $n$ :

b. En déduire que $(n+2)\mid (n^2+3n+7)$ si et seulement si $(n+2)\mid 5$.

c. Conclure : déterminer tous les entiers relatifs $n$ solutions, et vérifier l'un d'eux par un calcul direct.

On rappelle que, pour tout entier relatif $a$ et tout entier naturel non nul $b$, il existe un unique couple $(q;r)$ d'entiers tel que :

L'entier $q$ est le quotient et $r$ le reste de la division euclidienne de $a$ par $b$. Attention : le reste est toujours positif ou nul, y compris lorsque $a$ est négatif.

1. Écrire la division euclidienne de $a$ par $b$ (donner $q$ et $r$) dans chacun des cas suivants :

   a. $a=251$ et $b=13$

   b. $a=1000$ et $b=27$

   c. $a=2026$ et $b=7$

   d. $a=-58$ et $b=7$

   e. $a=-125$ et $b=11$

   f. $a=6$ et $b=9$

2. La division euclidienne d'un entier $a$ par $17$ a pour quotient $23$ et pour reste $11$. Déterminer $a$.

3. La division euclidienne de $325$ par un entier naturel $b$ a pour quotient $12$ et pour reste $1$. Déterminer $b$, en vérifiant que la condition sur le reste est bien satisfaite.

4. La division euclidienne d'un entier naturel $n$ par $8$ a pour quotient $15$. Déterminer toutes les valeurs possibles de $n$.

La division euclidienne permet de raisonner par disjonction de cas : tout entier $n$ s'écrit sous l'une des formes $bq$, $bq+1$, ..., $bq+(b-1)$ selon son reste dans la division par $b$.

1. Soit $n$ un entier relatif.

   a. En distinguant les cas $n=2q$ et $n=2q+1$ (avec $q$ entier), montrer que $n^2$ est de la forme $4k$ ou $4k+1$, avec $k$ entier.

   b. En déduire que $2027$ n'est pas le carré d'un entier.

   c. Montrer que la somme des carrés de deux entiers impairs n'est jamais le carré d'un entier.

2. Soit $n$ un entier relatif. On note $r$ le reste de la division euclidienne de $n$ par $5$, de sorte que $n=5q+r$ avec $r\in \{0;1;2;3;4\}$.

   a. Montrer que le reste de la division euclidienne de $n^2$ par $5$ ne dépend que de $r$, puis dresser le tableau de ces restes. Quels sont les restes possibles de $n^2$ dans la division par $5$ ?

   b. Soit $N$ un entier naturel dont le chiffre des unités est $2$, $3$, $7$ ou $8$. Déterminer le reste de la division euclidienne de $N$ par $5$, et en déduire que $N$ n'est jamais le carré d'un entier.

Soit $n$ un entier naturel non nul. On rappelle que deux entiers relatifs $a$ et $b$ sont congrus modulo $n$, ce qui se note $a\equiv b[n]$, lorsque $n\mid (a-b)$, c'est-à-dire lorsque $a$ et $b$ ont le même reste dans la division euclidienne par $n$.

1. Pour chacune des congruences suivantes, dire si elle est vraie ou fausse, en justifiant par un calcul de $a-b$ :

   a. $41\equiv 5[6]$

   b. $58\equiv 8[9]$

   c. $-13\equiv 2[5]$

   d. $2026\equiv 1[3]$

   e. $77\equiv -7[12]$

   f. $100\equiv 10[11]$

2. Déterminer dans chaque cas le reste de la division euclidienne de $a$ par $n$, c'est-à-dire l'unique entier $r$ tel que $a\equiv r[n]$ et $0⩽r<n$ :

   a. $a=123$, $n=10$

   b. $a=87$, $n=6$

   c. $a=-5$, $n=7$

   d. $a=-30$, $n=4$

   e. $a=145$, $n=12$

   f. $a=999$, $n=11$

3. Dresser la table d'addition et la table de multiplication modulo $4$ : pour chaque couple de restes $(x;y)$ avec $x$ et $y$ dans $\{0;1;2;3\}$, indiquer le reste de $x+y$ puis celui de $x\times y$ dans la division par $4$.

4. Deux entiers $a$ et $b$ vérifient $a\equiv 3[7]$ et $b\equiv 5[7]$. Déterminer le reste de la division euclidienne par $7$ de chacun des entiers suivants :

   a. $a+b$

   b. $ab$

   c. $a^2$

   d. $3a+2b$

Pour trouver le reste d'une grande puissance $a^N$ dans la division par $n$, on repère d'abord un cycle dans la suite des restes de $a^0,a^1,a^2,\dots$ modulo $n$, puis on utilise la division euclidienne de l'exposant $N$ par la longueur du cycle.

1. On étudie les restes de $3^n$ dans la division par $7$.

   a. Recopier et compléter le tableau des restes de $3^n$ modulo $7$ pour $n$ allant de $0$ à $6$, en calculant chaque reste à partir du précédent (on multipliera par $3$ puis on réduira modulo $7$).

   $n$	$0$	$1$	$2$	$3$	$4$	$5$	$6$
   reste de $3^n$ par $7$	$1$

   b. Justifier que, pour tout entier naturel $n$, on a $3^{n+6}\equiv 3^n[7]$.

   c. Écrire la division euclidienne de $2026$ par $6$, puis en déduire le reste de la division euclidienne de $3^{2026}$ par $7$.

2. En suivant la même démarche, dresser le tableau des restes de $2^n$ modulo $5$ pour $n$ allant de $0$ à $4$, repérer la longueur du cycle, puis déterminer le reste de la division euclidienne de $2^{2027}$ par $5$.

3. Application. Le chiffre des unités d'un entier naturel est le reste de sa division euclidienne par $10$. Déterminer le chiffre des unités de $7^{2026}$.

Soit $N$ un entier naturel dont l'écriture décimale est $\overline{c_p{c}_{p-1}\cdots c_1{c}_0}$, c'est-à-dire :

où $c_0,c_1,\dots ,c_p$ sont les chiffres de $N$ ($c_0$ est le chiffre des unités). L'objectif est de démontrer les critères de divisibilité par $9$ et par $11$, puis de les utiliser.

1. Critère de divisibilité par $9$.

   a. Justifier que $10\equiv 1[9]$, puis que ${10}^k\equiv 1[9]$ pour tout entier naturel $k$.

   b. En déduire que $N\equiv c_0+c_1+\cdots +c_p[9]$, puis énoncer le critère : à quelle condition sur la somme de ses chiffres l'entier $N$ est-il divisible par $9$ ?

2. Critère de divisibilité par $11$.

   a. Justifier que $10\equiv -1[11]$, puis que ${10}^k\equiv (-1{)}^k[11]$ pour tout entier naturel $k$.

   b. En déduire que :

puis énoncer le critère : $N$ est divisible par $11$ si et seulement si la somme alternée de ses chiffres (en partant du chiffre des unités) est divisible par $11$.

3. Applications numériques. Répondre sans poser aucune division.

   a. L'entier $852471$ est-il divisible par $9$ ? par $11$ ? Mêmes questions pour $918082$.

   b. Déterminer le chiffre $x$ pour que l'entier $\overline{81585x}$ soit divisible à la fois par $9$ et par $11$.

1. En déroulant l'algorithme d'Euclide (on écrira chaque division euclidienne), calculer le PGCD suivant :

   a. $\gcd (252;198)$

   b. $\gcd (1071;462)$

   c. $\gcd (325;143)$

2. On rappelle que les diviseurs communs à deux entiers sont exactement les diviseurs de leur PGCD. Dresser la liste de tous les diviseurs communs positifs de $252$ et $198$.

3. On considère la fonction Python suivante, qui prend en entrée deux entiers naturels non nuls :

   def pgcd(a, b):
       while b != 0:
           a, b = b, a % b
       return a
   

   a. Faire fonctionner cette fonction « à la main » pour a = 252 et b = 198 : donner les valeurs successives du couple (a, b) à chaque passage dans la boucle, ainsi que la valeur renvoyée.

   b. Expliquer pourquoi cette fonction renvoie bien le PGCD de a et b.

Partie A — Un problème de dallage.

On souhaite carreler entièrement le sol d'une pièce rectangulaire de $462$ cm sur $378$ cm avec des dalles carrées, toutes identiques, dont le côté est un nombre entier de centimètres. On ne veut découper aucune dalle.

1. Expliquer pourquoi le côté d'une dalle convenable doit être un diviseur commun de $462$ et de $378$.

2. Déterminer, à l'aide de l'algorithme d'Euclide, la plus grande taille de dalle possible.

3. Combien de dalles faut-il alors pour carreler toute la pièce ?

Partie B — Deux propriétés du PGCD.

Dans cette partie, $n$ désigne un entier naturel non nul.

4. Démontrer que $\gcd (n;n+1)=1$, c'est-à-dire que deux entiers consécutifs sont toujours premiers entre eux.

5. a. Soit $d$ un diviseur commun de $n$ et de $n+2$. Montrer que $d$ divise $2$.

   b. En déduire les valeurs possibles de $\gcd (n;n+2)$, puis préciser la valeur obtenue selon la parité de $n$.

On rappelle qu'une fraction ${\displaystyle \frac{a}{b}}$ (avec $a$ et $b$ entiers, $b\mathrm{\ne }0$) est dite irréductible lorsque $a$ et $b$ sont premiers entre eux, c'est-à-dire lorsque $\gcd (a;b)=1$.

1. À l'aide de l'algorithme d'Euclide, rendre irréductible chacune des fractions suivantes :

   a. ${\displaystyle \frac{1071}{462}}$

   b. ${\displaystyle \frac{325}{143}}$

2. Soit $n$ un entier naturel. On considère la fraction ${\displaystyle \frac{2n+1}{3n+2}}$.

   a. Soit $d$ un diviseur commun de $2n+1$ et de $3n+2$. Calculer $3(2n+1)-2(3n+2)$ et en déduire que $d$ divise $1$.

   b. Que peut-on en conclure pour la fraction ${\displaystyle \frac{2n+1}{3n+2}}$ ?

3. La fraction ${\displaystyle \frac{n+4}{2n+5}}$ est-elle irréductible pour tout entier naturel $n$ ? Justifier en s'inspirant de la méthode de la question 2, à l'aide d'une combinaison bien choisie de $n+4$ et de $2n+5$.

Le théorème de Bézout affirme que deux entiers $a$ et $b$ sont premiers entre eux si et seulement s'il existe des entiers relatifs $u$ et $v$ tels que $au+bv=1$. Pour trouver un tel couple $(u;v)$, on déroule l'algorithme d'Euclide, puis on « remonte » les divisions successives en exprimant à chaque étape le PGCD comme combinaison des restes.

1. a. Dérouler l'algorithme d'Euclide pour $33$ et $17$, et vérifier que ces deux entiers sont premiers entre eux.

   b. En remontant les calculs, déterminer un couple d'entiers relatifs $(u;v)$ tel que $17u+33v=1$.

2. a. Dérouler l'algorithme d'Euclide pour $87$ et $31$.

   b. En déduire, par remontée, un couple d'entiers relatifs $(u;v)$ tel que $87u+31v=1$.

3. Le couple trouvé à la question 1 est-il le seul couple d'entiers relatifs vérifiant $17u+33v=1$ ? Exhiber un second couple solution, en justifiant.

On rappelle le corollaire du théorème de Bézout : deux entiers $a$ et $b$ sont premiers entre eux si et seulement s'il existe des entiers relatifs $u$ et $v$ tels que $au+bv=1$.

Dans tout l'exercice, $n$ désigne un entier naturel.

Partie A — Un PGCD constant.

1. Calculer $1\times (2n+3)-2\times (n+1)$.

2. En déduire que $2n+3$ et $n+1$ sont premiers entre eux pour tout entier naturel $n$.

Partie B — Un PGCD qui dépend de $n$.

On pose $a=n+3$ et $b=2n+1$, et on note $d=\gcd (a;b)$.

3. Calculer $2(n+3)-(2n+1)$. En déduire que $d$ divise $5$.

4. Quelles sont les deux valeurs possibles de $d$ ?

5. a. Montrer que $d=5$ si et seulement si $n\equiv 2[5]$.

   b. Vérifier ce résultat sur les valeurs $n=2$ et $n=7$, puis donner la valeur de $d$ pour $n=4$.

On rappelle le théorème de Gauss : si $a$ divise le produit $bc$ et si $a$ est premier avec $b$, alors $a$ divise $c$.

1. Déterminer tous les couples $(x;y)$ d'entiers relatifs tels que $5x=7y$.

2. Soit $N$ un entier naturel divisible à la fois par $6$ et par $35$.

   a. Vérifier que $6$ et $35$ sont premiers entre eux.

   b. Démontrer que $210$ divise $N$.

   c. Le résultat serait-il encore vrai en remplaçant $6$ et $35$ par $6$ et $15$ ? Justifier à l'aide d'un contre-exemple.

3. Soit $p$ un nombre premier et $a$, $b$ deux entiers relatifs tels que $p$ divise $ab$ et $p$ ne divise pas $a$.

   a. Justifier que $p$ et $a$ sont premiers entre eux.

   b. En déduire que $p$ divise $b$.

   c. Application : démontrer que si $11$ divise $n^2$, alors $11$ divise $n$.

On se propose de résoudre dans ${\mathbb{Z}}^2$ l'équation diophantienne :

1. Justifier que l'équation $(E)$ admet au moins une solution.

2. a. Dérouler l'algorithme d'Euclide pour $33$ et $17$, puis, par remontée, déterminer un couple d'entiers relatifs $(u;v)$ tel que $17u-33v=1$.

   b. En déduire une solution particulière $(x_0;y_0)$ de $(E)$.

3. a. Montrer que $(x;y)$ est solution de $(E)$ si et seulement si $17(x-x_0)=33(y-y_0)$.

   b. À l'aide du théorème de Gauss, en déduire l'ensemble des solutions de $(E)$.

4. Question bonus. Déterminer l'unique solution $(x;y)$ de $(E)$ telle que $0\le x<33$.

Une association organise un spectacle de fin d'année. Les places sont vendues $23$ € pour les adultes et $15$ € pour les enfants. À la fin de la soirée, la recette totale s'élève à $500$ €. On cherche à déterminer le nombre de places de chaque type qui ont été vendues.

1. On note $x$ le nombre de places adulte vendues et $y$ le nombre de places enfant vendues. Montrer que le problème revient à résoudre l'équation

où $x$ et $y$ sont des entiers naturels.

2. En appliquant l'algorithme d'Euclide, montrer que $23$ et $15$ sont premiers entre eux. Pourquoi peut-on en déduire que l'équation $23x+15y=500$ admet des solutions dans ${\mathbb{Z}}^2$ ?

3. En remontant l'algorithme d'Euclide, déterminer un couple d'entiers $(u;v)$ tel que $23u+15v=1$. En déduire une solution particulière $(x_0;y_0)$ de l'équation $23x+15y=500$.

4. Résoudre l'équation $23x+15y=500$ dans ${\mathbb{Z}}^2$. On utilisera le théorème de Gauss.

5. Déterminer toutes les solutions $(x;y)$ telles que $x⩾0$ et $y⩾0$, vérifier qu'elles conviennent, puis répondre au problème posé.

1. Critère d'arrêt. Soit $n$ un entier naturel supérieur ou égal à $2$. Démontrer que si $n$ n'est pas premier, alors $n$ admet un diviseur premier $p$ tel que $p⩽\sqrt{n}$.

2. En utilisant ce critère, déterminer si les entiers suivants sont premiers. On précisera à chaque fois la liste des nombres premiers à tester.

   a. $397$

   b. $391$

3. Décomposer en produit de facteurs premiers les entiers suivants :

   a. $2520$

   b. $3300$

4. On rappelle que si $n=p_1^{{\alpha }_1}\times p_2^{{\alpha }_2}\times \cdots \times p_k^{{\alpha }_k}$ est la décomposition en facteurs premiers de $n$, alors le nombre de diviseurs positifs de $n$ vaut $({\alpha }_1+1)({\alpha }_2+1)\cdots ({\alpha }_k+1)$. En déduire le nombre de diviseurs positifs de $2520$ et de $3300$.

5. À l'aide des décompositions de la question 3, déterminer $\gcd (2520;3300)$.

L'objectif de cet exercice est de démontrer, en suivant l'idée d'Euclide, qu'il existe une infinité de nombres premiers.

Partie A — Expérimentation

1. Calculer $2\times 3\times 5+1$ et $2\times 3\times 5\times 7+1$. Vérifier que ces deux entiers sont premiers.

2. On admet que $2\times 3\times 5\times 7\times 11\times 13+1=30031$. Vérifier que $30031=59\times 509$. Que peut-on en conclure sur l'affirmation « le produit des premiers nombres premiers augmenté de $1$ est toujours un nombre premier » ?

Partie B — Démonstration

On raisonne par l'absurde : on suppose qu'il n'existe qu'un nombre fini de nombres premiers, que l'on note $p_1,p_2,\dots ,p_r$ (la liste est supposée complète). On pose

3. Justifier que $N⩾2$, puis que $N$ admet au moins un diviseur premier.

4. Soit $i\in \{1;2;\dots ;r\}$. Quel est le reste de la division euclidienne de $N$ par $p_i$ ? En déduire qu'aucun des nombres $p_1,p_2,\dots ,p_r$ ne divise $N$.

5. Conclure.

6. Au vu de la Partie A, l'entier $N$ construit dans la démonstration est-il nécessairement premier ? Expliquer pourquoi cela ne remet pas en cause le raisonnement.

On rappelle le petit théorème de Fermat : si $p$ est un nombre premier et si $a$ est un entier non divisible par $p$, alors $a^{p-1}\equiv 1[p]$.

1. a. Justifier que $8^{10}\equiv 1[11]$.

   b. En déduire le reste de la division euclidienne de $8^{100}$ par $11$.

2. a. Justifier que $5^{12}\equiv 1[13]$.

   b. Effectuer la division euclidienne de $2026$ par $12$, puis montrer que $5^{2026}\equiv 5^{10}[13]$.

   c. En remarquant que $5^2\equiv -1[13]$, déterminer le reste de la division euclidienne de $5^{2026}$ par $13$.

3. Un élève affirme : « d'après le petit théorème de Fermat, ${21}^6\equiv 1[7]$, donc le reste de la division de ${21}^{2026}$ par $7$ se calcule comme aux questions précédentes ». Expliquer pourquoi ce raisonnement est incorrect, puis déterminer le reste de la division euclidienne de ${21}^{2026}$ par $7$.

L'objectif de cet exercice est de démontrer que pour tout entier relatif $n$,

On rappelle la deuxième forme du petit théorème de Fermat : si $p$ est un nombre premier, alors pour tout entier $a$, $a^p\equiv a[p]$.

1. Vérifier le résultat pour $n=2$ et pour $n=3$ : calculer $n^7-n$ et effectuer la division par $42$.

2. Décomposer $42$ en produit de facteurs premiers.

3. Justifier que pour tout entier $n$, $n^7\equiv n[7]$.

4. Soit $n$ un entier.

   a. Justifier que $n^3\equiv n[3]$.

   b. En écrivant $n^7=(n^3{)}^2\times n$, en déduire que $n^7\equiv n[3]$.

5. Démontrer que pour tout entier $n$, $n^7\equiv n[2]$. On pourra raisonner sur la parité de $n$, ou utiliser le petit théorème de Fermat avec $p=2$.

6. Énoncer le corollaire du théorème de Gauss utilisé ici, vérifier que ses hypothèses sont satisfaites par $2$, $3$ et $7$, puis conclure que $42\mid n^7-n$ pour tout entier $n$.

Pour chacune des affirmations suivantes, dire si elle est vraie ou fausse. Une affirmation vraie doit être démontrée dans le cas général ; une affirmation fausse doit être réfutée par un contre-exemple explicite.

Dans tout l'exercice, $a$, $b$, $c$ désignent des entiers relatifs et $n$ un entier naturel supérieur ou égal à $2$.

1. Si $a\mid bc$, alors $a\mid b$ ou $a\mid c$.

2. Si $a\mid b$ et $b\mid a$, alors $a=b$ ou $a=-b$.

3. Si $a\equiv b[n]$, alors $a^2\equiv b^2[n]$.

4. Si $a^2\equiv b^2[n]$, alors $a\equiv b[n]$.

5. Pour tous entiers naturels non nuls $a$ et $b$ avec $a>b$ : $\gcd (a;b)=\gcd (a-b;b)$.

6. S'il existe des entiers $u$ et $v$ tels que $au+bv=6$, alors $\gcd (a;b)=6$.

7. Si $a\mid c$ et $b\mid c$, alors $ab\mid c$.

On souhaite chiffrer des messages écrits avec les $26$ lettres de l'alphabet. Chaque lettre est d'abord remplacée par un nombre selon la table suivante :

Pour chiffrer une lettre de numéro $x$, on calcule l'unique entier $y\in \{0;1;\dots ;25\}$ tel que

puis on remplace la lettre par celle de numéro $y$.

1. Chiffrer le mot MATHS.

2. On veut montrer que ce chiffrement est « décodable », c'est-à-dire que deux lettres différentes sont toujours chiffrées différemment, et qu'on peut retrouver $x$ à partir de $y$.

   a. En appliquant l'algorithme d'Euclide à $26$ et $11$, montrer que $\gcd (26;11)=1$, puis déterminer un couple d'entiers $(u;v)$ tel que $26u+11v=1$.

   b. En déduire un entier $d\in \{0;1;\dots ;25\}$ tel que $11d\equiv 1[26]$. Vérifier le résultat par un calcul direct.

3. a. Montrer que $y\equiv 11x+8[26]$ équivaut à $x\equiv 19(y-8)[26]$.

   b. À l'aide de cette formule de déchiffrement, décoder le message EGPA. Vérifier le résultat en le rechiffrant.

4. Un camarade propose de chiffrer plutôt avec la formule $y\equiv 13x+8[26]$.

   a. Chiffrer les lettres A et C avec cette formule. Que constate-t-on ?

   b. Expliquer pourquoi le choix $a=13$ rend le déchiffrement impossible, en lien avec la valeur de $\gcd (13;26)$.