next up previous
suivant: Nombres premiers, nombres premiers monter: Arithmétique dans précédent: Sous-groupe de

Pgcd, ppcm, algorithme d'Euclide

Exercice 290 Calculer le pgcd des nombres suivants :

  1. 126, 230.
  2. 390, 720, 450.
  3. 180, 606, 750.



Exercice 291

  1. Calculer le ppcm des nombres : 108 et 144 ; 128 et 230 ; 6, 16 et 50.
  2. Montrer que si $ a\geqslant 1$ et $ b\geqslant 1$ sont des entiers de pgcd $ d$ et, si on pose $ a=da' ; b=db' $, le ppcm de $ a$ et $ b$ est $ da'b'$.
  3. Montrer que si $ a,b,c$ sont des entiers supérieurs à $ 1$, on a :

    ppcm$\displaystyle (a,b,c)=$ppcm$\displaystyle ($ppcm$\displaystyle (a,b),c).$



Exercice 292 Déterminer les couples d'entiers naturels de pgcd 18 et de somme 360. De même avec pgcd 18 et produit 6480.



Exercice 293 Si $ a,b,c,d$ sont des entiers supérieurs à $ 1$, montrer que l'on a :

$\displaystyle (a,b,c,d)=((a,b),(c,d))$

où ( , ) désigne le pgcd .

Exercice 294

  1. Soient $ a,b,c$ des entiers relatifs tels que $ (a,b)\not =(0,0)$, montrer que pour que l'équation

    $\displaystyle ax+by=c$

    ait une solution $ (x,y)$ en entiers relatifs $ x$ et $ y$, il faut et il suffit que le pgcd de $ a$ et $ b$ divise $ c$.
  2. Résoudre en entiers relatifs les équations suivantes :

    $\displaystyle 7x-9y=1,$

    $\displaystyle 7x-9y=6,$

    $\displaystyle 11x+17y=5.$



Exercice 295 Soient $ a$ et $ b$ deux entiers tels que $ a\geqslant b\geqslant 1$ et pgcd$ (a,b)=1$.

  1. Montrer que pgcd$ (a+b,a-b)=1$ ou $ 2$,
  2. Si pgcd$ (a,b)=1$, montrer que pgcd $ (a+b,ab)=1$,
  3. Si pgcd$ (a,b)=1$, montrer que pgcd $ (a+b,a^2+b^2)=1$ ou $ 2$.


Exercice 296 Calculer par l'algorithme d'Euclide : $ 18480\wedge 9828$. En déduire une écriture de $ 84$ comme combinaison linéaire de $ 18480$ et $ 9828$.



Exercice 297 Déterminer le pgcd de $ 99 099$ et $ 43 928$. Déterminer le pgcd de $ 153 527$ et $ 245 479$.

Exercice 298 Déterminer l'ensemble de tous les couples $ (m,n)$ tels que

$\displaystyle 955m+183n=1.$



Exercice 299 Calculer, en précisant la méthode suivie,

$\displaystyle a=$pgcd$\displaystyle (720,252) \quad\quad b =$   ppcm$\displaystyle (720,252)$

ainsi que deux entiers $ u$ et $ v$ tels que $ 720u+252v=a$.

Exercice 300 Démontrer :

$\displaystyle a\wedge(b_1b_2)=1 \Leftrightarrow (a\wedge b_1=1$    et $\displaystyle a\wedge b_2 =1), $

puis par récurence :

$\displaystyle a\wedge(b_1 \ldots b_n)=1 \Leftrightarrow \forall i=1,\ldots,n  a\wedge b_i =1. $



Exercice 301 Démontrer pour $ m,n\in\mathbb{N}^*$ :

$\displaystyle a^m \wedge b^n=1 \Rightarrow a \wedge b=1.$



Exercice 302 Déteminer deux entiers naturels connaissant leur somme, $ 1008$, et leur pgcd, $ 24$.

Exercice 303 Notons $ a=1\;111\;111\;111$ et $ b=123\;456\;789$.

  1. Calculer le quotient et le reste de la division euclidienne de $ a$ par $ b$.
  2. Calculer $ p= $   pgcd$ (a,b)$.
  3. Déterminer deux entiers relatifs $ u$ et $ v$ tels que $ au+bv=p$.



Exercice 304 Soient $ m$ et $ n$ deux entiers $ (m>n>0)$ et $ a \geqslant 2$ un entier. Montrer que le reste de la division euclidienne de $ a^m-1$ par $ a^n-1$ est $ a^r-1$$ r$ est le reste de la division euclidienne de $ m$ par $ n$, et que le pgcd de $ a^m-1$ et $ a^n-1$ est $ a^d-1$, où $ d$ est le pgcd de $ m$ et $ n$.

Exercice 305 Résoudre dans $ {\mathbb{Z}}:1665x+1035y=45.$



Exercice 306 Montrer qu'il n'existe pas d'entiers $ m$ et $ n$ tels que

$\displaystyle m+n=101$   et   pgcd$\displaystyle (m,n)=3$



Exercice 307 Soit $ m$ et $ n$ deux entiers positifs.

  1. Si pgcd$ (m,4)=2$ et pgcd$ (n,4)=2$, montrer que pgcd$ (m+n,4)=4$.
  2. Montrer que pour chaque entier $ n$, $ 6$ divise $ n^3-n$.
  3. Montrer que pour chaque entier $ n$, $ 30$ divise $ n^5-n$.
  4. Montrer que si $ m$ et $ n$ sont des entiers impairs, $ m^2+n^2$ est pair mais non divisible par $ 4$.
  5. Montrer que le produit de quatre entiers consécutifs est divisible par $ 24$.
  6. Montrer que si pgcd$ (a,b)=1$, alors


Exercice 308 Trouver une CNS pour que $ ax+b\equiv 0  \rm {mod}  n$ ait une solution.

Exercice 309

  1. Calculer pgcd$ (18,385)$ par l'algorithme d'Euclide, en déduire un couple $ (u_0,v_0)\in\mathbb{Z}^2$ solution de l'équation $ 18u+385v=1$, avec $ (u,v)\in\mathbb{Z}^2$.
  2. Fournir enfin l'ensemble des solutions entières de

    $\displaystyle 18u+385v=1;\quad
18u+385v=3;\quad 54u+1155v=3;\quad 54u+1155v=5.$



Exercice 310 Trouver $ a$ et $ b$ entiers naturels tels que

  1. $ a+b=2070$ et ppcm$ (a,b)=9180$ ;
  2. $ a^2+b^2=5409$ et ppcm$ (a,b)=360$ (on pourra commencer par montrer que pgcd$ (a,b)$ divise pgcd$ (5409,360)$ et considérer ensuite différents cas).


Exercice 311 Résoudre dans $ \mathbb{Z}$ les équations: $ 35x \equiv 7  \rm {mod}  4;   22x \equiv 33 \rm {mod} 5 $

Exercice 312 Résoudre dans $ \mathbb{Z}$ le système suivant:

\begin{displaymath}S : \left\{
\begin{array}{cccc}
x&\equiv &4&\rm {mod} 6\\
x&\equiv &7&\rm {mod} 9
\end{array}\right.
\end{displaymath}

On recherchera d'abord une solution particulière.

Exercice 313

  1. Résoudre dans $ \mathbb{Z}$ les équations: $  x^2\equiv 2 \rm {mod} 6;\quad  x^3\equiv 3 \rm {mod} 9$.
  2. Résoudre dans $ \mathbb{Z}^2$ les équations suivantes: $ 5x^2 +2xy-3=0 ;\quad y^2+4xy-2=0$.


Exercice 314 Résoudre dans $ \mathbb{Z}^2$ les équations suivantes:

\begin{displaymath}\begin{array}{lcr}
\hbox{a) } 17x+6y=1 &\qquad & \hbox{b) } 2...
...ox{c) } 118x+35y=1 &\qquad & \hbox{d) } 39 x+26 y=1
\end{array}\end{displaymath}



Exercice 315 Montrer que si $ a$ divise $ 42n+37$ et $ 7n+4$, pour une valeur de $ n$ donnée, alors $ a$ divise $ 13$. Quelles sont les valeurs possibles pour $ n$ ?

Exercice 316 Trouver pgcd$ (-357,629)$ et trouver des entiers $ x$ et $ y$ tels que

pgcd$\displaystyle (-357,629)=-357x+629y$



Exercice 317 Trouver pgcd$ (2183,6313)=d$ et trouver des entiers $ x$ et $ y$ tels que

$\displaystyle d=2183x+6313y$



Exercice 318 Supposons pgcd$ (a,b)=d$ et soit $ x_{0}$ et $ y_{0}$ des entiers tels que $ d=ax_{0}+by_{0}$. Montrer que :

  1. pgcd$ (x_{0},y_{0})=1$,
  2. $ x_{0}$ et $ y_{0}$ ne sont pas uniques.


Exercice 319 Soit $ a$, $ b$, $ c$ des entiers.

  1. Montrer que pgcd$ (ca,cb)=\vert c\vert\;$pgcd$ (a,b)$.
  2. Montrer que pgcd$ (a^2,b^2)=($pgcd$ (a,b))^2$.
  3. Montrer que si pgcd$ (a,b)=1$ et si $ c$ divise $ a$, alors pgcd$ (c,b)=1$.
  4. Montrer que pgcd$ (a,bc)=1 \iff$   pgcd$ (a,b)=$pgcd$ (a,c)=1$.
  5. Montrer que si pgcd$ (b,c)=1$ alors pgcd$ (a,bc)=$pgcd$ (a,b)$   pgcd$ (a,c)$.
  6. Montrer que pgcd$ (a,b)=$pgcd$ (a+b,$ppcm$ (a,b))$.


Exercice 320

En divisant un nombre par $ 8$, un élève a obtenu $ 4$ pour reste ; en divisant ce même nombre par $ 12$, il a obtenu $ 3$ pour reste. Qu'en pensez-vous ?

Le fort en calcul de la classe, qui ne fait jamais d'erreur, a divisé le millésime de l'année par $ 29$, il a trouvé $ 25$ pour reste ; il a divisé le même millésime par $ 69$, il a trouvé $ 7$ pour reste. En quelle année cela se passait-il ?

Exercice 321 Trouver deux nombres sachant que leur somme est $ 581$ et que le quotient de leur PPCM par leur pgcd est $ 240$.

Exercice 322 Trouver les solutions entières de l'équation :

$\displaystyle 102x-18018y=18.$

Combien y a-t-il de solutions telles que $ x$ et $ y$ soient compris entre entre 0 et $ 4000$ ?

Exercice 323 Le pgcd de deux nombres est $ 12$ ; les quotients successifs obtenus dans le calcul de ce pgcd par l'algorithme d'Euclide sont $ 8$, $ 2$ et $ 7$. Trouver ces deux nombres.

Exercice 324 Trouver les couples de nombres $ a$ et $ b$, divisibles par $ 3$, vérifiant les propriétés suivantes : leur ppcm est $ 7560$, et si on augmente chacun de ces nombres d'un tiers de sa valeur, le pgcd des deux nombres obtenus est $ 84$.

Exercice 325 Un terrain rectangulaire dont les dimensions en mètres $ a$ et $ b$ sont des nombres entiers, a pour aire $ 3024\;$   m$ ^2$. Calculer son périmètre sachant que le pgcd de $ a$ et $ b$ est $ 6$. Combien y a-t-il de solutions possibles ?

Exercice 326

  1. Dans $ \mathbb{Z}/n\mathbb{Z}$, écrire l'ensemble des multiples de $ \bar x$, classe de $ x$, pour $ x$ variant de 0 à $ n-1$ dans chacun des cas suivants : $ \mathbb{Z}/5\mathbb{Z}$, $ \mathbb{Z}/6\mathbb{Z}$, $ \mathbb{Z}/8\mathbb{Z}$.
  2. Dans $ \mathbb{Z}/n\mathbb{Z}$, montrer l'équivalence des trois propositions :
    i)
    $ \bar x$ est inversible ;
    ii)
    $ x$ et $ n$ sont premiers entre eux ;
    iii)
    $ \bar x$ engendre $ \mathbb{Z}/n\mathbb{Z}$, c'est à dire que l'ensemble des multiples de $ \bar x$ est $ \mathbb{Z}/n\mathbb{Z}$.
  3. La classe de $ 18$ est-elle inversible dans $ \mathbb{Z}/49\mathbb{Z}$ ? Si oui, quel est son inverse ? (On pourra utiliser le théorème de Bézout).


Exercice 327 Résoudre dans $ \mathbb{Z}$ les équations suivantes :

  1. $ 91x-65y=156$.
  2. $ 135 x-54y=63$.
  3. $ 72x+35y=13$.


Exercice 328 Résoudre dans $ \mathbb{N}$ les équations suivantes :

  1. $ 31x-13y=1$.
  2. $ 31x-13y=-1$.
Application : Au bord d'une piscine pleine d'eau, on dispose d'une cuve fixe de 31 litres munie à sa base d'un robinet de vidange, et d'un seau de 13 litres. Expliquer comment opérer pour obtenir exactement 1 litre dans le seau.

Exercice 329 Résoudre dans $ \mathbb{N}$ l'équation $ 77x+105y=2401$.

Exercice 330 Dans un pays nommé ASU, dont l'unité monétaire est le rallod, la banque nationale émet seulement des billets de 95 rallods et des pièces de 14 rallods.

  1. Montrer qu'il est possible de payer n'importe quelle somme entière (à condition bien sûr que les deux parties disposent chacune d'assez de pièces et de billets).
  2. On suppose que vous devez payer une somme $ S$, que vous avez une quantité illimitée de pièces et de billets, mais que votre créancier ne puisse pas rendre la monnaie. Ainsi, il est possible de payer si $ S=14$, mais pas si $ S=13$ ou si $ S=15$... Montrer qu'il est toujours possible de payer si $ S$ est assez grande. Quelle est la plus grande valeur de $ S$ telle qu'il soit impossible de payer $ S$ ?


Exercice 331 Trouver tous les points à coordonnées entières du plan d'équation $ 6x+10y+15z=1997$. Combien y a-t-il de solutions dans $ \mathbb{N}^3$ ?

Exercice 332

  1. Trouver tous les points à coordonnées entières de la droite de l'espace d'équations \begin{displaymath}\left\{
\begin{array}{rcl}
4x-2y-z-5 & = & 0 \\
x+3y-4z-7 & = & 0
\end{array}\right.\end{displaymath}.
  2. Même question avec la droite \begin{displaymath}\left\{
\begin{array}{rcl}
x+3y-5z -5 & = & 0 \\
4x-2y+z+13 & = & 0
\end{array}\right.\end{displaymath}.


Exercice 333 Résoudre dans $ \mathbb{N}$ et dans $ \mathbb{Z}$ l'équation

$\displaystyle \frac{1}{x}+\frac{1}{y}=\frac{1}{15}$



Exercice 334 Un coq coûte $ 5$ pièces d'argent, une poule $ 3$ pièces, et un lot de quatre poussins $ 1$ pièce. Quelqu'un a acheté $ 100$ volailles pour $ 100$ pièces ; combien en a-t-il acheté de chaque sorte ?

Exercice 335 Soient $ a$ et $ b$ deux nombres entiers relatifs. On note $ d$ leur pgcd. Construisons les suites $ a_n$ et $ b_n $ $ n \in \mathbb{N},$ à valeurs dans $ \mathbb{Z}$de la manière suivante :

$\displaystyle a_0$ $\displaystyle =$ $\displaystyle a$  
$\displaystyle b_0$ $\displaystyle =$ $\displaystyle b$  

et pour tout $ n \in \mathbb{N},$ on pose $ a_{n+1}= b_n$ et $ b_{n+1}= r$$ r$ est le reste de la division euclidienne de $ a_n$ par $ b_n.$

  1. Montrer que si $ d_n$ est le pgcd de $ a_n$ et $ b_n $ alors $ d_n$ est également le pgcd de $ a_{n+1}$ et $ b_{n+1}.$
  2. Déduire de la questionh précédente que $ d$ est le pgcd des nombres $ a_n$ et $ b_n $ pour tout $ n \in \mathbb{N}.$
  3. Montrer que la suite $ b_n $ est strictement décroissante. Que peut-on en déduire?
  4. Déduire de ce qui précède que pour tout couple d'entiers relatifs $ (a,b)$ il existe un couple d'entier relatifs $ (u,v)$ tel que:

    $\displaystyle d = au+bv.
$




next up previous
suivant: Nombres premiers, nombres premiers monter: Arithmétique dans précédent: Sous-groupe de
Arnaud Bodin 2004-06-24