arithmétique

[invitec3d2af16]

Bonsoir
j'ai un exercice de spé a faire pour demain et je n'y arrive pas .

voila l'enoncé

on se propose de determiner le pgcd(a;b) avec a=5n-1 et b=3n+2
a l'aide d'un tableur on obtient le tableau suivant

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
a 4 9 14 19 24 29 34 39 44 49 54 59 64 69 74 79 84 89 94 99 104 109
b 5 8 11 14 17 20 23 26 29 32 35 38 41 44 47 50 53 56 59 62 65 68
pgcd(a;b) 1 1 1 1 1 1 1 1 13 1 1 1 1 1 1 1 1 1 1 1 1 13 1

Determiner le PGCD(a;b) suivant les valeurs de n

je ne vois pas vraiment comment il faut s'y prendre

le pgcd varie pour 8 et 21 . Il n'ya pas de lien entre ces deux nombres


pouvez vous m'aider svp?
-----

[Seirios]

Bonjour,

Tu devrais essayer de trouver une combinaison linéaire de a et b pour éliminer les n ; alors tout diviseur commun à a et b divisera ta combinaison linéaire.

[invite5150dbce]

a=5n-1 et b=3n+2
PGCD(a;b)|a et PGCD(a;b)|b ==>PGCD(a;b)|[3(5n-1)-5(3n+2)]
Donc PGCD(a;b)|-13
Or les diviseurs ppositifs de -13 sont 1 et 13 donc PGCD(a;b)=1 ou PGCD(a;b)=13

Si PGCD(a;b)=13, alors 13|a et 13|b
Donc 5n-1 congru 0 modulo 13 et 3n+2 congru 0 modulo 13
D'où -5n congru -1 modulo 13 et 6n congru -4 modulo 13
Par conséquent n est congru -5 est congru 8 modulo 13
Donc il existe k appartenant à IN tel que n=13k+8

Montrons que pour tout k appartenant à IN tel que n=13k+8, PGCD(a;b)=13
5(13k+8)-1=65k+39
3(13k+8)+2=39k+26
65k+39=39k+26+26k+13
39k+26=26k+13+13k+13
26k+13=13k+13+13k
13k+13=13k+13
Or 13|13k donc PGCD(a;b)=13

Je te laisse conclure