Exercice corrigé Ancien programme

pgcd avec l'aide d'un tableur

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 , .

Accéder à tous les contenus
dès 6,79€/mois

  • Les dernières annales corrigées et expliquées
  • Des fiches de cours et cours vidéo/audio
  • Des conseils et méthodes pour réussir ses examens
  • Pas de publicités
S'abonner