Quel est le PGCD de 4539 et 1958 ?
On utilise l'algorithme d'Euclide :
4\ 539 = 1\ 958 \times 2 +623
1\ 958= 623\times 3 +89
623= 89\times 7
On en déduit que :
PGCD \left(4\ 539 ; 1\ 958\right) = 89
Quel est le PGCD de 3 354 et 1 625 ?
On utilise l'algorithme d'Euclide :
3\ 354= 1\ 625\times 2 +104
1\ 625= 104\times 15 +65
104= 65\times 1+39
65= 39\times 1+26
39= 26\times 1+13
26= 13\times 2+0
On en déduit que :
PGCD \left(3\ 354 ; 1\ 625\right) = 13
Quel est le PGCD de 14 478 et 7011 ?
On utilise l'algorithme d'Euclide :
14\ 478= 7\ 011\times 2 +456
7\ 011= 456\times 15 +171
456= 171\times 2+114
171= 114\times 1+57
114= 57\times 2+0
On en déduit que :
PGCD \left(14\ 478; 7\ 011\right) = 57
Quel est, en fonction de n, le PGCD de \left(n+5\right) et \left(3n+10\right) ?
On pose d=PGCD\left(n+5 ; 3n+10\right).
D'après le cours, si d est le PGCD de \left(n+5\right) et \left(3n+10\right), alors d divise toute combinaison linéaire des deux expressions.
On détermine une combinaison linéaire de \left(n+5\right) et \left(3n+10\right) éliminant les n :
3\left(n+5\right) -\left(3n+10\right) = 15-10=5
On en déduit que d divise 5.
Donc d=5 ou d=1.
Si d=5
Si d=5, alors 5 divise \left(n+5\right) et \left(3n+10\right).
On s'aide d'un tableau modulo 5 afin de déterminer les valeurs de n :
| n | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| n + 5 | 0 | 1 | 2 | 3 | 4 |
| 3n + 10 | 0 | 3 | 1 | 4 | 2 |
Le seul cas possible est donc n = 0 +5k.
Donc, si n = 5k, PGCD\left(n+5 ; 3n+10\right)=5.
Si d=1
Si d=1, alors PGCD\left(n+5 ; 3n+10\right)=1.
- Si n = 5k, PGCD\left(n+5 ; 3n+10\right)=5
- Sinon PGCD\left(n+5 ; 3n+10\right)=1
Quel est le PGCD de 2184 et 1645 ?
On utilise l'algorithme d'Euclide :
2\ 184= 1\ 645\times 1 +539
1\ 645= 539\times 3 +28
539= 28\times 19+7
28= 7\times 4+0
On en déduit que :
PGCD \left(2\ 184; 1\ 645\right) = 7
Quel est, en fonction de n, le PGCD de \left(n+1\right) et \left(2n+4\right) ?
On pose d=PGCD\left(n+1 ; 2n+4\right).
D'après le cours, si d est le PGCD de \left(n+1\right) et \left(2n+4\right), alors d divise toute combinaison linéaire des deux expressions.
On détermine une combinaison linéaire de \left(n+1\right) et \left(2n+4\right) éliminant les n :
-2\left(n+1\right) +\left(2n+4\right) = -2+4=2
On en déduit que d divise 2.
Donc d=2 ou d=1.
Si d=2
Si d=2, alors 2 divise \left(n+1\right) et \left(2n+4\right).
On s'aide d'un tableau modulo 2 afin de déterminer les valeurs de n :
| n | 0 | 1 |
|---|---|---|
| n + 1 | 1 | 0 |
| 2n + 4 | 0 | 0 |
Le seul cas possible est donc n = 1 +2k.
Donc, si n = 1+2k, PGCD\left(n+1 ; 2n+4\right)=2.
Si d=1
Si d=1, alors PGCD\left(n+1 ; 2n+4\right)=1.
- Si n = 1+2k, PGCD\left(n+1 ; 2n+4\right)=2
- Sinon PGCD\left(n+1 ; 2n+4\right)=1
Quel est, en fonction de n, le PGCD de \left(2n+1\right) et \left(3n+3\right) ?
On pose d=PGCD\left(2n+1 ; 3n+3\right).
D'après le cours, si d est le PGCD de \left(2n+1\right) et \left(3n+3\right), alors d divise toute combinaison linéaire des deux expressions.
On détermine une combinaison linéaire de \left(2n+1\right) et \left(3n+3\right) éliminant les n :
-3\left(2n+1\right) +2\left(3n+3\right) = -3+6=3
On en déduit que d divise 3.
Donc d=3 ou d=1.
Si d=3
Si d=3, alors 3 divise \left(2n+1\right) et \left(3n+3\right).
On s'aide d'un tableau modulo 3 afin de déterminer les valeurs de n :
| n | 0 | 1 | 2 |
|---|---|---|---|
| 2n + 1 | 1 | 0 | 2 |
| 3n + 3 | 0 | 0 | 0 |
Le seul cas possible est donc n = 1 +3k.
Donc, si n = 1+3k, PGCD\left(2n+1 ; 3n+3\right)=3.
Si d=1
Si d=1, alors PGCD\left(2n+1 ; 3n+3\right)=1.
- Si n = 1+3k, PGCD\left(2n+1 ; 3n+3\right)=3
- Sinon PGCD\left(2n+1 ; 3n+3\right)=1