Gcd

par **MathematicienPoche** » 31 Oct 2007, 17:26

Rebonjour,

j'aurais encore une question que je n'arrive pas a résoudre pour mon exam de demain.

Prouver que gcd(na,nb) = n gcd(a,b).

Faut-il que j'utilise un algorithme, ou y'a t-il une méthode quelconque?

Merci.

par **MathematicienPoche** » 31 Oct 2007, 17:33

c'est-a-dire gcd(a,b) = k, et alors nk|na et nk|nb puisque a et b sont multiples de k. Et ensuite? en quoi montrer que s'il n'y en a pas de plus grand va montrer qu'ils sont egaux?

par **MathematicienPoche** » 31 Oct 2007, 17:41

Ah! d'accord je viens d'allumer. Mais pour ce qui est de la preuve par l'absurde on si prend comment? Supposons z = pgdc(a,b) > k .. ensuite?

par **MathematicienPoche** » 31 Oct 2007, 18:01

Quelqu'un d'autre peut repondre peut etre? Svp

par **yos** » 31 Oct 2007, 22:03

Soit d=PGCD(a,b).
PGCD(na,nb)=nau+nbv=n(au+bv).
Par conséquent n(au+bv)|na, donc au+bv|a . De même au+bv|b.
Donc au+bv|d et donc au+bv=d.

Gcd

gcd

Qui est en ligne