Arithmétique dans ℤ

Exercice 1 — Division euclidienne

Effectuer la division euclidienne de $-52$ par $7$.

Exercice 2 — Reste d'une puissance

Déterminer le reste de la division de $2^{20}$ par $7$.

Exercice 3 — PGCD et PPCM

Déterminer $\text{pgcd}(391,299)$ par l'algorithme d'Euclide, puis en déduire $\text{ppcm}(391,299)$.

Exercice 4 — Identité de Bézout

En utilisant l'algorithme d'Euclide, déterminer un couple d'entiers $(u,v)$ tel que $253u+161v=\text{pgcd}(253,161)$.

Exercice 5 — Équation diophantienne

Résoudre dans $\mathbb{Z}^2$ l'équation $7x-4y=3$.

Exercice 6 — Divisibilité par congruence

Montrer que pour tout entier naturel $n$, $3^{2n+1}+2^{n+2}$ est divisible par $7$.

Un grossiste doit livrer exactement 500 sacs de riz. Il loue des camionnettes, qui transportent chacune 19 sacs, et des tricycles, qui transportent chacun 12 sacs. Tous les véhicules loués doivent partir pleins. On note \(x\) le nombre de camionnettes et \(y\) le nombre de tricycles : ces deux entiers vérifient l'équation \((E)\) : \(19x+12y=500\).

1) À l'aide de l'algorithme d'Euclide, démontre que 19 et 12 sont premiers entre eux, puis détermine deux entiers relatifs \(u\) et \(v\) tels que \(19u+12v=1\).

2) Déduis-en une solution particulière \((x_0\,;\,y_0)\) de l'équation \((E)\) dans l'ensemble des entiers relatifs.

3) Résous l'équation \((E)\) dans l'ensemble des couples d'entiers relatifs. Tu préciseras à quel endroit intervient le théorème de Gauss.

4) Détermine tous les couples d'entiers naturels solutions de \((E)\), c'est-à-dire toutes les façons d'organiser la livraison.

5) La location coûte 9000 francs par camionnette et 5000 francs par tricycle. Calcule le coût de chaque organisation. La moins chère est-elle celle qui emploie le moins de véhicules ? Interprète ce résultat.

Une mutuelle attribue à chaque adhérent un numéro \(N\) écrit avec six chiffres \(a\), \(b\), \(c\), \(d\), \(e\), \(f\), lus de gauche à droite : \(N=10^5a+10^4b+10^3c+10^2d+10e+f\). Elle ajoute une clé \(K\), qui est le reste de la division euclidienne de \(N\) par 11. À chaque saisie, l'ordinateur recalcule la clé : si elle ne correspond pas, la saisie est refusée.

1) Démontre que, pour tout entier naturel \(k\), \(10^k\equiv(-1)^k\ [11]\). Déduis-en que \(N\equiv f-e+d-c+b-a\ [11]\).

2) Calcule la clé du numéro \(N=483726\).

3) Un agent se trompe sur un seul des six chiffres d'un numéro \(N\) et saisit un numéro \(N'\). Démontre que \(N'\) et \(N\) n'ont pas le même reste dans la division par 11 : l'erreur est toujours repérée.

4) Un agent échange deux chiffres voisins et différents d'un numéro \(N\). En notant \(N'\) le numéro saisi, exprime \(N'-N\) puis démontre, à l'aide du théorème de Gauss, que cette erreur est toujours repérée.

5) Vérifie sur le numéro \(483726\) que l'échange du quatrième et du sixième chiffre n'est pas repéré. Explique ce défaut de la clé dans le cas général de deux chiffres séparés par un seul chiffre.

6) Sur une fiche abîmée, on lit le numéro \(52x641\), dont le troisième chiffre \(x\) est illisible, et la clé 7. Retrouve le chiffre \(x\).

On considère dans \(\mathbb{C}\) les équations \((E_1)\) : \(z^{84}=1\) et \((E_2)\) : \(z^{60}=1\). On cherche les nombres complexes qui sont solutions des deux équations à la fois.

1) Calcule le PGCD de 84 et 60 par l'algorithme d'Euclide, puis détermine deux entiers relatifs \(u\) et \(v\) tels que \(84u+60v=12\).

2) Soit \(z\) une solution commune à \((E_1)\) et \((E_2)\). Justifie que \(z\neq 0\), puis démontre à l'aide de la question 1 que \(z^{12}=1\).

3) Démontre la réciproque, puis conclus : donne le nombre de solutions communes et écris-les sous forme exponentielle.

4) On pose \(\omega=e^{i\frac{2\pi}{84}}\) ; les solutions de \((E_1)\) sont les nombres \(\omega^k\), où \(k\) est un entier compris entre 0 et 83. Démontre, à l'aide du théorème de Gauss, que \(\omega^k\) est solution de \((E_2)\) si et seulement si \(k\) est un multiple de 7. Retrouve ainsi le résultat de la question 3.

5) Détermine le plus petit entier \(n\geq 1\) tel que \(z^n=1\) pour toute solution \(z\) de \((E_1)\) et pour toute solution \(z\) de \((E_2)\). Justifie ta réponse.

On cherche tous les couples \((a\,;\,b)\) d'entiers naturels, avec \(a\leq b\), dont le PGCD est 18 et le PPCM est 1512. On rappelle que, pour deux entiers naturels non nuls \(a\) et \(b\), le produit de leur PGCD par leur PPCM est égal à \(ab\).

1) Décompose 1512 et 18 en produits de facteurs premiers. Déduis-en la décomposition de l'entier \(\dfrac{1512}{18}\).

2) Justifie que 1512 possède exactement 32 diviseurs positifs. Combien d'entre eux sont des multiples de 18 ?

3) Soit \((a\,;\,b)\) un couple qui convient. On pose \(a=18a'\) et \(b=18b'\), où \(a'\) et \(b'\) sont des entiers naturels. Démontre que \(a'\) et \(b'\) sont premiers entre eux et que \(a'b'=84\).

4) Détermine tous les couples \((a'\,;\,b')\) d'entiers naturels premiers entre eux tels que \(a'\leq b'\) et \(a'b'=84\). Déduis-en tous les couples \((a\,;\,b)\) cherchés.

5) Un seul de ces couples vérifie \(a+b=342\). Lequel ? Contrôle son PGCD par l'algorithme d'Euclide, puis son PPCM.