J´ai un problème de math SPE que j´arrive pas à resoudre! Voici le problème qui porte sur les diviseurs communs, PGCD et nombres premiers entre eux :

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

1) g divise 323

2)"g est un multiple de 17" équivaut à "a est un multiple de 17"

3) "g est un multiple de 19" équivaut à "il existe un entier k, tel que a = 19k + 4"

4) 289 est le plus petit entier a tel que g= 323

beaucoup de votre aide !!

! !

c´est si dur que ca pour que personne ne trouve ??

att 3 sec

t´en fais pas j´ai le temps ! Je vais continuer à chercher !

algorithme d´Euclide:
pgcd(a,b) = pgcd(b,a-b)
d´autre part, pgcd(a,b)=pgcd(b,a)
En utilisant cela, on obtient:

g
= pgcd(20a+357,15a+187)
= pgcd(15a+187,5a+170)
= pgcd(5a+170,10a+17)
= pgcd(10a+17,5a+170)
= pgcd(5a+170,5a-153)
= pgcd(5a-153,323)

donc
1) forcément g divise 323
2) 323 = 19*17 donc g est un multiple de 17 ssi 5a-153 est un multiple de 17, or 153 = 9*17, donc g est un multiple de 17 ssi 5a est un multiple de 17 ssi a est un multiple de 17
3) on a deja vu que 323 est un multiple de 19, donc g est un multiple de 19 ssi 5a-153 est un multiple de 19, or 153 = 19*8+1 donc g est un multiple de 19 ssi 5a-1 est un multiple de 19 ssi 5a est congru a 1 modulo 19 ssi a est congru à 4 modulo 19 (puisque 5*4=20=1 mod 19)
4) pour que g = 323, il faut que 5a-153 soit un multiple de 17 et un multiple de 19. il faut donc, par les points 2 et 3 que a soit un multiple de 17 congru à 4 modulo 19.
Il faut trouver le plus petit k tel que 17k=4(mod 19)
en essayant les cas successifs k=1,k=2,... on trouve que le premier est k=17, ce qui donne a = 289

c´est super le_duche mais le problème c´est qu´on a pas encore etudiés le modulo et les congruences alors je peux pas les utiliser !! Je fais comment alors ?

sorry j´ai pas le net chez moi, donc je ne suis jamais là apres 19h...

quand je dis que "a est congru à b modulo c" tu peux le traduire par, "le reste de la division de a par c est b"

ok !! merci !!