[TS-Spé] PGCD et multiples

[JALeX]

Bonsoir à tous,
voilà un exercice sur lequel je bute :

Exercice
a est un entier strictement positif. On pose :
m = 20a + 357 ; n = 15a + 187
g est le PGCD de m et de n. Démontrez les énoncés suivants

1/ g divise 323

2/ "g multiple de 19" "il existe un entier k tel que a=19k+4"

3/ 289 est le plus petit entier tel que g=323

[c pi]

Bonsoir

1) g divise 323

g divisant m, il divise aussi son multiple 3m
g divisant n, il divise aussi son multiple 4n
g divisant 3m et 4n, il divise aussi leur différence 3m-4n.

2) entier k tel que a=19k+4

m = 20a+357 = 19(a+18) + (a+15)
g étant multiple de 19, son multiple m l'est aussi, donc (a+15) aussi :
a+15 = 19q => a = 19q-15 = 19(q-1)+19-15 = 19(q-1)+4 = 19k+4

En exprimant m et n en fonction de k à partir de l'hypothèse a=19k+4
on montre facilement qu'ils sont tous les deux multiples de 19, donc g aussi.

3) plus petit entier a tel que g=323

g étant le pgcd à m et n, les rapports m/g et n/g sont entiers (et premiers entre eux) ;
pour a=19k+4 et g=323, on a :
m/g= (20a+357)/323= [19(20k+23)]/(19*17) = (20k+23)/17
n/g= (15a+187)/323= [19(15k+13)]/(19*17) = (15k+23)/17

Dire que ces deux rapports sont entiers,
revient à écrire qu'il existe deux entiers p et q tels que
20k+23 = 17p ou encore 17(k+1)+2(k+2) = 17p
15k+13 = 17q ou encore 17(k+1)-2(k+2) = 17q
et qu'il existe nécessairement un entier t tel que
2(k+2) = 17t équivalent à k = 17t/2-2.

Le plus petit t qui convienne pour k entier naturel non nul est t=2, donc k=15 et a=289.

C'est un peu laborieux, mais je n'ai pas trouvé plus élégant. :zen: