PGCD

[Hugo]

Bonsoir à tous
J'ai une question concernant le PGCD

Dans un exo : il faut déterminer le PGCD de a et b sachant a=5n+1 et b=2n-1.
Soit d un diviseur commun à a et b.
d|5n+1 et d|2n-1 donc d divise toutes combinaisons de a et b, d'où d|2(5n+1)-5(2n-1) soit d|7.
Donc PGCD(a;b)=7 ou PGCD(a;b)=1.
Dans quel cas on a PGCD(a;b)=7 ?
Dans la correction il y a un tableau de congruence modulo 7, avec a et b.
Je ne comprends pas pourquoi on fait un tableau de congruence car ce n'est pas parce qu'un nombre est divisible par 7 qu’obligatoirement son PGCD vaut 7.

Merci de m'éclairer

[SoS-Math(9)]

Bonsoir Hugo,

Tout d'abord le PGCD d'un nombre n'a pas de sens ... on parle du pgcd de deux nombres !
Tu cherches à savoir pour quelles valeurs de n on a pgcd(a;b) = 7.
Je pense que le tableau est là pour t'aider à conjecturer la "forme" de n ...
Ensuite pour le prouver utilise les congruences :
5n+1 est divisible par 7, donc \(5n+1\equiv 0 [7]\)
2n-1 est divisible par 7, donc ...

SoSMath.

[Hugo]

Oui mais ce n'est pas parce que deux nombres sont divisible par 7 que leur PGCD est 7

[SoS-Math(9)]

Oui et où est le problème ?
Suivant les valeurs de n, a et b ne sont pas tous les deux divisibles par 7 ...
On recherche les valeurs de n pour que a et b soient divisibles par 7.

SoSMath.

[Hugo]

oui mais ça ne répond pas à la question posée dire que pour n=7k+4 on a PGCD(5n+1;2n-1)=7 me semble faux car pour n=7k+4, 5n+1 et 2n-1 sont divisibles par 7 maus leur PGCD n'est pas nécessairement 7.
Donc dire que pour tout n=7k+4 on a PGCD(5n+1;2n-1)=7 me parait faux.

[SoS-Math(9)]

Non Hugo !

Si n=7k+4, alors 5n+1=35n+21=7(5k+3) et 2n-1=14k+7=7/(2k+1)
Tu montres alors que le pgcd(5k+3;2k+1)=1.

SoSMath.

[Hugo]

Tu montres alors que le pgcd(5k+3;2k+1)=1.

Mais comment ?
Comment on peut être sur que pour tout k on a pgcd(5k+3;2k+1)=1

[sos-math(21)]

Bonjour,
Si tu appelles \(m=5k+3\) et \(n=2k+1\) et que tu notes \(d\) leur pgcd, alors \(d|m\) et \(d|n\).
Donc \(d|2m\) et \(d|5n\) donc \(d|2m-5n\).
Je te laisse calculer combien vaut \(2m-5n\) et j'espère que cela te convaincra que \(PGCD(m\,;\,n)=1\).
Bon calcul