Corrigé

Clique ICI pour revoir le cours sur le PGCD.

1. Il est clair que $PGCD(18\,600;47\,740)=PGCD(47\,740;18\,600)$.

On va effectuer des divisions euclidiennes successives et utiliser le lemme d'Euclide.
Etape 1: $47\,740=18\,600×2+10\,540$ avec $0≤10\,540 < 18\,600$
Etape 2: $18\,600=10\,540×1+8\,060$ avec $0≤8\,060 < 10\,540$
Etape 3: $10\,540=8\,060×1+2\,480$ avec $0≤2\,480 < 8\,060$
Etape 4: $8\,060=2\,480×3+620$ avec $0≤620< 2\,480 $
Etape 5: $2\,480=620×4+0$
On a donc: $PGCD(47\,740;18\,600)=PGCD(18\,600;10\,540)=PGCD(10\,540;8\,060)=...PGCD(620;0)=620$

Donc finalement: $PGCD(18\,600;47\,740)=620$

2. Comme $n$ est un entier naturel non nul, on a: $2n+1 > 3$.
Donc on a: $8n+6=4(2n+1)+2$ avec $0≤2 < 2n+1$
Le quotient de la division euclidienne de $8n+6$ par $2n+1$ est 4, et le reste est 2.
Par conséquent: $PGCD(8n+6;2n+1)=PGCD(2n+1;2)$
Or, les diviseurs de 2 étant 1 et 2, et 2 ne divisant pas $2n+1$, on a: $PGCD(2n+1;2)=1$.
Donc: $PGCD(8n+6;2n+1)=1$

3. On a: $PGCD(n;198)=33$.
Donc: il existe $k$ tel que $n=33k$.
Or, comme $n=33k$, et que $n≤ 350$, on en déduit que $k≤10$.

Cherchons la valeur de $k$.
On a: $198=33×6$
Et on vient de voir que $n=33k$.
On a donc: $PGCD(33k;33×6)=33$.
Et par là: $PGCD(k;6)=1$.
Et comme les diviseurs de 6 sont 1, 2, 3 et 6, on en déduit que $k$ ne peut pas être un multiple de 2, 3 ou 6.

Or on a vu que $k≤10$.
Par conséquent, les valeurs de $k$ possibles sont: 1, 5 et 7.
Et par là: $n$ vaut 33, ou 165, ou 231.

4. Exécutons la fonction recursivite(18,15) selon le programme ci-dessous.

On appelle recursivite(18,15)
a=18   b=15
Comme $ 18=15×1+3$ avec $0≤3 < 15$, on a: r=3
Comme r n'est pas nul, on va affecter à y la valeur retournée par recursivite(15,3)
Le programme exécute donc recursivite(15,3)
      a=15   b=3
      Comme $ 15=3×5+0$ avec $0≤0 < 3$, on a: r=0
      Comme r vaut 0, recursivite(15,3) retourne la valeur de b, c'est à dire 3.
On revient donc dans l'appel initial à recursivite(18,15).
La valeur de b est donc affectée à y, qui vaut alors 3.
Et finalement, la valeur retournée par recursivite(18,15) est 3.

On a reconnu ci-dessus que l'algorithme utilisé dans la fonction recursivite est l'algorithme d'Euclide.
Donc, dans le cas général, si a et b sont deux entiers naturels, recursivite(a,b) retourne pgcd(a,b).

La fonction recursivite(a,b) s'utilise elle même dans sa définition. Ce procédé s'appelle "récursivité". Il n'est pas exigible en terminale...