Trouver un PGCD

[Anonyme]

bonjour est ce que vous pouvez m'aider je n'arrive pas a m'ensortir avec cet exercice d'arithmétique


trouver un pgcd

a et b sont 2 entiers strctement positifs et g est leur PGCD ; p,q,r,s sont des entiers positifs tels que ps-qr=1 et on pose A=pa+bq et B=ra+sb

objectif déterminer le PGCD g' de A et B

1- "g est un diviseur de A et B et g
2- "on se donne des valeurs numériques en choisissant d'abord des nombres p,q,r,s convenables. On choisit A=8a+11b et B=5a+7b puis on choisit des valeurs de a et b"
verifier que chaque fois on trouve a chaque fois g'=g

3-"on tente donc de démontrer que g'=g. d'aprés la 1 il suffit de démontrer que g'Mais pour démontrer que g' divise g il suffit de démontrer que g' divise a et b " justifier cette afirmation

4-"La question est maintenant celle ci : on sait que g' divise A=pa+qb et B=ra+sb , peut on en déduire que g' divise a et b? L'idée vient alors d'exprimer a en fonction de A et B et b aussi. "
Prouvez qu'il existe des entiers m et n, m' et n' , tels que a=mA+nB b=m'A+n'B

Puis concluez et rédiger une solution

merci

[becirj]

Bonjour
1. g divise a et divise b donc g divise pa et bq et par conséquent leur somme A.
Même raisonnement pour B
Un diviseur commun à 2 nombres est un diviseur de leur pgcd donc g divise g' d'où . 2. Si tu as un doute, propose ta solution.

[becirj]

3. Si g' divise a et b, alors g' divise leur pgcd g car tout diviseur commun à 2 nombres est un diviseur de leur pgcd.

4. Il s'agit de résoudre le système où a et b sont les inconnues.
Il ne faut pas oublier que ps-qr=1, c'est utile dans la résolution.