Maths-cours

COURS & EXERCICES DE MATHÉMATIQUES

Close

Déterminer le PGCD

Soit nn un entier naturel.

On pose a=3n+1a=3n+1, b=5n+1b=5n+1 et d=PGCD(a;b)d=PGCD\left(a;b\right).

  1. Montrer que dd est un diviseur de 2.

  2. Déterminer les valeurs de dd en fonction de nn.

Corrigé

  1. dd divise aa et bb donc il divise toute combinaison linéaire de aa et bb ; en particulier il divise :

    5a3b=5(3n+1)3(5n+1)=25a - 3b=5\left(3n+1\right) - 3\left(5n+1\right)=2

    Remarque

    On a choisi les coefficients 55 et 3 - 3 de façon à éliminer les nn...

  2. Les seuls diviseurs entiers naturels de 22 sont 11 et 22.

    Par conséquent :

    • Si nn est pair, aa et bb sont impairs donc dd ne peut pas être égal à 22, d'où d=1d=1

    • Si nn est impair, aa et bb sont pairs donc dd est également pair d'où d=2d=2