Pour tout entier naturel n, on définit deux entiers a et b en posant :
et
On s'intéresse aux valeurs du PGCD de a et de b en fonction de n.
1. Conjecture
a. Sur un tableur, créer trois colonnes donnant les valeurs de n, a et b pour n variant de 0 à 100.
b. Remplir la quatrième colonne avec les valeurs du PGCD de a et de b.
c. Quelles semblent être les valeurs possibles de PGCD ?
d. Peut-on caractériser les valeurs de n telles que PGCD ?
2. Démonstrations
a. Démontrer la conjecture faite au 1. c.
b. En raisonnant par disjonction des cas, déterminer les valeurs de n telles que PGCD
1. c. Les valeurs possibles de PGCD (a, b) semblent être 1 et 7.
d. Il semble que lorsque
,
.
2. a. Soit d un diviseur positif commun à a et b.
il existe
tel que
il existe
tel que
Pour obtenir une propriété sur d, on cherche à éliminer n de ces expressions pour cela, on procède comme dans un système à plusieurs inconnues, par combinaison linéaire. |
,
, puis, par soustraction membre à membre :
Ainsi, d est un diviseur de −7, donc ou
.
PGCD étant le plus grand des diviseurs, on retrouve la conjecture.
b. ● Si,
mais 7 ne divise pas 1, donc 7 n'est pas un diviseur de a, donc 7 ne peut être le PGCD de a et b : on conclut que
si
.
● Si,
mais 7 ne divise pas 5, donc 7 n'est pas un diviseur de a. On conclut que
si
.
● Si ,
. De la même façon, on conclut que
si
.
● Si ,
et
,
si
.
● Si ,
,
et
si
.
● Si ,
,
, et 7 est un diviseur de 28k et de 21, donc
.
De plus, . Donc 7 est un diviseur de 35k et de 28, donc 7|b.
Comme PGCD = 1 ou 7, alors le PGCD de a et b est 7 si,
.
● Si ,
,
, donc
si
.
Ainsi, si et seulement si
,
.
Autre méthode : On peut présenter les différents cas dans un tableau des restes modulo 7 :
n (modulo 7) | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
4n+1 (modulo 7) | 1 | 5 | 2 | 6 | 3 | 0 | 4 |
5n+3 (modulo 7) | 3 | 1 | 6 | 4 | 2 | 0 | 5 |
On constate que le reste est égal à 0, c'est-à-dire 7 divise et
, où 7 est le PGCD cherché, lorsque
(modulo 7), donc pour
,
.