\documentclass[12pt]{amsart}
\usepackage{kbexo}

\num{4}
\course{MHT203 -- Cryptologie}
\begin{document}

\exotitle[{\large PGCD - PPCM - Théorème de Bezout}]
\smallskip

\exo
Si $a=462$ et $b=104$ calculer $d=\pgcd(a,b)$, puis $\ppcm(a,b)$. Déterminer
un couple d'entiers $(u,v)$ tels que $au+bv=d$.

\exo
\Q Trouver deux entiers tels que $29u+24v=1$.
\Q Déterminer l'ensemble des couples $(u,v)\in \ZM^2$ tels que
$29u+24v=3$.
\Q Si $x,y\in\ZM$ sont tels que $29x +24y=3$, que peut-on dire
de $x$ et de $y$ ?

\Q Si $x,y\in\ZM$ sont tels que $29x +24y=5$, que peut-on dire de $x$
et de $y$ ?

\exo
Calculer les pgcd suivants :  $\pgcd(46848,2379)$, $\pgcd(13860,4488)$ et
$\pgcd(30076,12669,21733)$.

\exo
Quel est le plus petit entier $n > 0$, qui soit multiple de
$1,2,\dots,10$ ?

\exo
Calculer $\pgcd(357,629)$ puis $d=\pgcd(357,629,221)$. Trouver des entiers
$x,y$ et $z$ tels que $357x+629y+221z=d$.

\exo
Soit $a,b$ et $c$ des entiers. On suppose que $a \mid bc$ et
$\pgcd(a,b)=1$. En utilisant une relation de Bezout, montrer que $a \mid c$.

\exo
\Q Montrer que $15$ et $28$ sont premiers entre eux.
\Q Trouver une solution particulière de l'équation $28x-15y=1$. En déduire
une solution de $28x-15y=11$.
\Q Caculer le pgcd de $15$ et $21$. L'équation $15x-21y=3$ admet elle des
solutions dans $\ZM^2$ ?
\Q Même question pour l'équation $15x-21y=5$ ?
\end{document}
