Arithmétique

1. 1

   Exercice 1

   Facile

   Déterminer tous les entiers relatifs $n$ tels que :

   1. $n-2$ divise $n+7$ ;
   2. $n+1$ divise $n^2+3$.
   Voir un indice

   Isoler la partie constante : écrire $n+7$ (respectivement $n^2+3$) comme un multiple de $n-2$ (respectivement $n+1$) augmenté d'un reste constant, puis se ramener aux diviseurs de ce reste.

   Voir la correction

   1. On écrit $n+7=(n-2)+9$. Comme $n-2\mid n-2$, on a par combinaison linéaire :

   $$(n-2)\mid (n+7)\iff (n-2)\mid 9.$$

   Les diviseurs de $9$ dans $\mathbb{Z}$ sont $\{-9,-3,-1,1,3,9\}$. En résolvant $n-2=d$ pour chacun, on obtient

   $$n\in\{-7,\,-1,\,1,\,3,\,5,\,11\}.$$

   2. La division euclidienne du polynôme $n^2+3$ par $n+1$ donne $n^2+3=(n+1)(n-1)+4$. Donc

   $$(n+1)\mid (n^2+3)\iff (n+1)\mid 4.$$

   Les diviseurs de $4$ sont $\{-4,-2,-1,1,2,4\}$, d'où

   $$n\in\{-5,\,-3,\,-2,\,0,\,1,\,3\}.$$

   Vérification par exemple pour $n=3$ : $n+1=4$ et $n^2+3=12$, et $4\mid 12$.

2. 2

   Exercice 2

   Facile
   1. Déterminer le reste de la division euclidienne de $2^{2023}$ par $7$.
   2. Montrer que, pour tout entier naturel $n$, le nombre $3^{2n+1}+2^{n+2}$ est divisible par $7$.
   Voir un indice

   Chercher un petit exposant $k$ tel que $2^k\equiv 1\pmod 7$. Pour la seconde question, exprimer $9^n$ et $4\cdot 2^n$ modulo $7$ afin de faire apparaître un facteur $7$.

   Voir la correction

   1. On calcule les puissances de $2$ modulo $7$ : $2^1\equiv 2$, $2^2\equiv 4$, $2^3\equiv 8\equiv 1\pmod 7$. La suite des restes est donc périodique de période $3$. Comme $2023=3\times 674+1$,

   $$2^{2023}=\bigl(2^{3}\bigr)^{674}\times 2^{1}\equiv 1^{674}\times 2\equiv 2\pmod 7.$$

   Le reste cherché est $\boxed{2}$.

   2. On travaille modulo $7$. D'une part $3^{2n+1}=3\cdot 9^{n}$ et $9\equiv 2\pmod 7$, donc $3^{2n+1}\equiv 3\cdot 2^{n}\pmod 7$. D'autre part $2^{n+2}=4\cdot 2^{n}$. Ainsi

   $$3^{2n+1}+2^{n+2}\equiv 3\cdot 2^{n}+4\cdot 2^{n}=7\cdot 2^{n}\equiv 0\pmod 7.$$

   Le nombre est donc divisible par $7$ pour tout $n\in\mathbb{N}$.

3. 3

   Exercice 3

   Facile
   1. Calculer $\operatorname{PGCD}(654,342)$ à l'aide de l'algorithme d'Euclide.
   2. Montrer que, pour tout entier relatif $n$, les entiers $5n+3$ et $3n+2$ sont premiers entre eux.
   Voir un indice

   Pour la question 2, chercher une combinaison linéaire à coefficients entiers de $5n+3$ et $3n+2$ qui élimine $n$ et donne une constante ; tout diviseur commun divisera alors cette constante.

   Voir la correction

   1. Divisions euclidiennes successives :

   $$\begin{aligned} 654&=1\times 342+312,\\ 342&=1\times 312+30,\\ 312&=10\times 30+12,\\ 30&=2\times 12+6,\\ 12&=2\times 6+0. \end{aligned}$$

   Le dernier reste non nul est $6$, donc $\operatorname{PGCD}(654,342)=6$.

   2. Soit $d$ un diviseur commun de $5n+3$ et $3n+2$. Alors $d$ divise toute combinaison linéaire entière ; or

   $$3(5n+3)-5(3n+2)=15n+9-15n-10=-1.$$

   Donc $d\mid 1$, c'est-à-dire $d=\pm 1$. Par conséquent $\operatorname{PGCD}(5n+3,\,3n+2)=1$ : ces entiers sont premiers entre eux quel que soit $n$.

4. 4

   Exercice 4

   Facile

   On considère les entiers $120$ et $23$.

   1. Justifier que $120$ et $23$ sont premiers entre eux.
   2. Déterminer un couple d'entiers $(u,v)$ tel que $120u+23v=1$.
   3. En déduire un inverse de $23$ modulo $120$, puis un inverse de $120$ modulo $23$.
   Voir un indice

   Dérouler l'algorithme d'Euclide, puis le « remonter » (algorithme d'Euclide étendu) pour exprimer $1$ comme combinaison de $120$ et $23$. La relation de Bézout se lit directement comme une congruence.

   Voir la correction

   1. L'algorithme d'Euclide donne :

   $$120=5\times 23+5,\quad 23=4\times 5+3,\quad 5=1\times 3+2,\quad 3=1\times 2+1,\quad 2=2\times 1.$$

   Le dernier reste non nul est $1$, donc $\operatorname{PGCD}(120,23)=1$.

   2. On remonte les égalités :

   $$\begin{aligned} 1&=3-1\times 2\\ &=3-(5-3)=2\times 3-5\\ &=2(23-4\times 5)-5=2\times 23-9\times 5\\ &=2\times 23-9(120-5\times 23)=47\times 23-9\times 120. \end{aligned}$$

   Ainsi $120\times(-9)+23\times 47=1$, d'où $(u,v)=(-9,\,47)$. On vérifie : $-1080+1081=1$.

   3. De $23\times 47\equiv 1\pmod{120}$ on déduit qu'un inverse de $23$ modulo $120$ est $\boxed{47}$.

   De $120\times(-9)\equiv 1\pmod{23}$ on déduit qu'un inverse de $120$ modulo $23$ est $-9\equiv 14\pmod{23}$. Vérification : $120\equiv 5\pmod{23}$ et $5\times 14=70=3\times 23+1\equiv 1\pmod{23}$.

5. 5

   Équation diophantienne $8x+5y=100$

   Moyen

   On considère l'équation, d'inconnue $(x,y)\in\mathbb{Z}^2$ :

   $$(E)\quad 8x+5y=100.$$

   1. Déterminer une solution particulière de $(E)$.
   2. Résoudre $(E)$ dans $\mathbb{Z}^2$.
   3. Déterminer les solutions $(x,y)$ de $(E)$ vérifiant $x\geq 0$ et $y\geq 0$.
   Voir un indice

   Commencer par une relation de Bézout entre $8$ et $5$, puis multiplier par $100$. Pour la forme générale, soustraire deux solutions et utiliser le théorème de Gauss ; enfin encadrer le paramètre pour la question 3.

   Voir la correction

   Ce contenu est réservé : laisse tes coordonnées pour débloquer toutes les indications et corrections du site, gratuitement.

   Ta classeTroisièmeSecondePremièreTerminalePrépa scientifique 1ère annéePrépa scientifique 2ème annéePrépa ECG 1ère annéeAutre

   Débloquer

   Tes coordonnées servent uniquement à t'informer de nos ressources et stages — jamais de spam. Politique de confidentialité

6. 6

   Résolution de congruences linéaires

   Moyen

   Résoudre dans $\mathbb{Z}$ les congruences suivantes :

   1. $7x\equiv 5\pmod{26}$ ;
   2. $6x\equiv 4\pmod{10}$.
   Voir un indice

   Dans le premier cas, $7$ est inversible modulo $26$ : trouver son inverse. Dans le second, $\operatorname{PGCD}(6,10)\neq 1$ : vérifier la condition d'existence, puis simplifier la congruence par ce PGCD (en divisant aussi le module).

   Voir la correction

   Ce contenu est réservé : laisse tes coordonnées pour débloquer toutes les indications et corrections du site, gratuitement.

   Ta classeTroisièmeSecondePremièreTerminalePrépa scientifique 1ère annéePrépa scientifique 2ème annéePrépa ECG 1ère annéeAutre

   Débloquer

   Tes coordonnées servent uniquement à t'informer de nos ressources et stages — jamais de spam. Politique de confidentialité

7. 7

   Divisibilité et petit théorème de Fermat

   Moyen
   1. Déterminer le reste de la division euclidienne de $2^{2024}$ par $13$.
   2. Montrer que, pour tout entier relatif $n$, le nombre $n^7-n$ est divisible par $42$.
   Voir un indice

   Utiliser le petit théorème de Fermat : $a^{p}\equiv a\pmod p$ pour $p$ premier. Pour la question 2, remarquer que $42=2\times 3\times 7$ et raisonner modulo chacun de ces trois nombres premiers.

   Voir la correction

   Ce contenu est réservé : laisse tes coordonnées pour débloquer toutes les indications et corrections du site, gratuitement.

   Ta classeTroisièmeSecondePremièreTerminalePrépa scientifique 1ère annéePrépa scientifique 2ème annéePrépa ECG 1ère annéeAutre

   Débloquer

   Tes coordonnées servent uniquement à t'informer de nos ressources et stages — jamais de spam. Politique de confidentialité

8. 8

   Chiffrement RSA

   Difficile

   Alice publie sa clé publique $(n,e)=(55,3)$. Elle a construit sa clé à partir des nombres premiers $p=5$ et $q=11$.

   1. Calculer $\varphi(n)=(p-1)(q-1)$ et vérifier que $e=3$ est bien un exposant de chiffrement admissible.
   2. Déterminer la clé privée $d$, inverse de $e$ modulo $\varphi(n)$.
   3. Bob souhaite envoyer le message $m=7$. Calculer le message chiffré $c\equiv m^{e}\pmod n$.
   4. Vérifier que le déchiffrement $c^{d}\bmod n$ redonne bien $m=7$.
   Voir un indice

   Ce contenu est réservé : laisse tes coordonnées pour débloquer toutes les indications et corrections du site, gratuitement.

   Ta classeTroisièmeSecondePremièreTerminalePrépa scientifique 1ère annéePrépa scientifique 2ème annéePrépa ECG 1ère annéeAutre

   Débloquer

   Tes coordonnées servent uniquement à t'informer de nos ressources et stages — jamais de spam. Politique de confidentialité

   Voir la correction

   Ce contenu est réservé : laisse tes coordonnées pour débloquer toutes les indications et corrections du site, gratuitement.

   Ta classeTroisièmeSecondePremièreTerminalePrépa scientifique 1ère annéePrépa scientifique 2ème annéePrépa ECG 1ère annéeAutre

   Débloquer

   Tes coordonnées servent uniquement à t'informer de nos ressources et stages — jamais de spam. Politique de confidentialité

9. 9

   Infinité de nombres premiers

   Difficile
   1. Démontrer qu'il existe une infinité de nombres premiers (démonstration d'Euclide).
   2. Montrer qu'il existe une infinité de nombres premiers de la forme $4k+3$.
   Voir un indice

   Ce contenu est réservé : laisse tes coordonnées pour débloquer toutes les indications et corrections du site, gratuitement.

   Ta classeTroisièmeSecondePremièreTerminalePrépa scientifique 1ère annéePrépa scientifique 2ème annéePrépa ECG 1ère annéeAutre

   Débloquer

   Tes coordonnées servent uniquement à t'informer de nos ressources et stages — jamais de spam. Politique de confidentialité

   Voir la correction

   Ce contenu est réservé : laisse tes coordonnées pour débloquer toutes les indications et corrections du site, gratuitement.

   Ta classeTroisièmeSecondePremièreTerminalePrépa scientifique 1ère annéePrépa scientifique 2ème annéePrépa ECG 1ère annéeAutre

   Débloquer

   Tes coordonnées servent uniquement à t'informer de nos ressources et stages — jamais de spam. Politique de confidentialité