Exercice 3

1. On applique l'algorithme d'Euclide : le PGCD est le dernier reste non nul.

a) $$\begin{aligned} 840 &= 144\times 5+120 \\ 144 &= 120\times 1+24 \\ 120 &= 24\times 5+0 \end{aligned}$$

b) $$\begin{aligned} 202 &= 138\times 1+64 \\ 138 &= 64\times 2+10 \\ 64 &= 10\times 6+4 \\ 10 &= 4\times 2+2 \\ 4 &= 2\times 2+0 \end{aligned}$$

c) $$\begin{aligned} 777 &= 441\times 1+336 \\ 441 &= 336\times 1+105 \\ 336 &= 105\times 3+21 \\ 105 &= 21\times 5+0 \end{aligned}$$

d) $$\begin{aligned} 9185 &= 2004\times 4+1169 \\ 2004 &= 1169\times 1+835 \\ 1169 &= 835\times 1+334 \\ 835 &= 334\times 2+167 \\ 334 &= 167\times 2+0 \end{aligned}$$

2. a) $$\begin{aligned} 5633 &= 4847\times 1+786 \\ 4847 &= 786\times 6+131 \\ 786 &= 131\times 6+0 \end{aligned}$$

b) $$\begin{aligned} 5617 &= 813\times 6+739 \\ 813 &= 739\times 1+74 \\ 739 &= 74\times 9+73 \\ 74 &= 73\times 1+1 \\ 73 &= 1\times 73+0 \end{aligned}$$