Pgcd et algorithme d'Euclide (2/2)

Exercices corrigés

Exercice 1.
Pour tout

{n}

{\mathbb{N}^{*}}

, on note

{E_{n}=\{0,1,\ldots,n-1\}}

Pour ${m\in\mathbb{N}^{*}}$ , on note ${\varphi(n)=\text{card}\{k\in E_{n},\;k\wedge n=1\}}$ (indicatrice d’Euler).

Soient ${m,n}$ dans ${\mathbb{N}^{*}}$ , avec ${m\wedge n=1}$ .

Soit ${f : E_{m}\times E_{n}\rightarrow E_{mn}}$ définie par ${f(x,y)=xn+ym\ [mn]}$ .

Montrer que ${f}$ est bijective. En déduire que ${\varphi(mn)=\varphi(m)\varphi(n)}$ .

Cliquer ici pour voir (ou cacher) le corrigé

Pour voir la suite de ce contenu, vous devez :

Pour poursuivre votre exploration, vous pouvez :

Exercice 2.
Prouver que pour tout

{m\in\mathbb{Z}}

, la fraction

{\dfrac{21m+4}{14m+3}}

est irréductible.

Cliquer ici pour voir (ou cacher) le corrigé

Pour voir la suite de ce contenu, vous devez :

Pour poursuivre votre exploration, vous pouvez :

Exercice 3.

Soient ${m}$ et ${n}$ deux entiers premiers entre eux. Soient ${a}$ et ${b}$ deux entiers.
On considère le système ${(S):\ \begin{cases}x\equiv a\pmod m\cr x\equiv b\pmod n\end{cases}}$
Montrer que l’ensemble des solutions de $(S)$ est une classe d’entiers modulo ${mn}$ .
Résoudre le système ${\begin{cases}x\equiv 3\pmod {12}\cr x\equiv 5\pmod 9\end{cases}}$