[Term]PGCD

[Anonyme]

Je pense que c'est niveau term...
Soit d=pgcd(a,b) si c divise a et b est ce que c divise d?
Ca me paraitrait logique mais je n'arrive pas à m'en persuader.
Qq1 peut m'aider (démo?)
Merci.

[Anonyme]

Le Sat, 13 Sep 2003 18:10:26 +0200,
stef grava à la saucisse et au marteau:

> Je pense que c'est niveau term...
> Soit d=pgcd(a,b) si c divise a et b est ce que c divise d?
> Ca me paraitrait logique mais je n'arrive pas à m'en persuader.
> Qq1 peut m'aider (démo?)

Il existe (u,v) tel que au+bv = d (Bezout)
a = a'*c
b = b'*c
Donc d = c(a'u+b'v)

--
Genji
"Il n'y a pas d'amis, il n'y a que des moments d'amitié."
Jules Renard

[Anonyme]

je croyais que bezout, c'était seulement si a et b premiers entre eux alors
il existe u et v tq au+bv=1...
"Nicolas Le Roux" wrote in message
news:slrnbm6gr9.liu.nicolas@zen.via.ecp.fr...
> Le Sat, 13 Sep 2003 18:10:26 +0200,
> stef grava à la saucisse et au marteau:
>[color=green]
> > Je pense que c'est niveau term...
> > Soit d=pgcd(a,b) si c divise a et b est ce que c divise d?
> > Ca me paraitrait logique mais je n'arrive pas à m'en persuader.
> > Qq1 peut m'aider (démo?)
>
> Il existe (u,v) tel que au+bv = d (Bezout)
> a = a'*c
> b = b'*c
> Donc d = c(a'u+b'v)
>
> --
> Genji
> "Il n'y a pas d'amis, il n'y a que des moments d'amitié."
> Jules Renard[/color]

[Anonyme]

Le Sat, 13 Sep 2003 18:24:06 +0200,
stef grava à la saucisse et au marteau:

> je croyais que bezout, c'était seulement si a et b premiers entre eux alors
> il existe u et v tq au+bv=1...

Non, c'est au+bc = pgcd(a,b)

C'est une conséquence directe de ce que tu as dit:
pgcd(a,b)=c
Soit a' = a/c
b' = b/c
Donc a' et b' sont premiers entre eux.
Donc il existe (u,v) tel que a'u+b'v = 1
Donc au+bv=c

--
Genji
"Il n'y a pas d'amis, il n'y a que des moments d'amitié."
Jules Renard

[Anonyme]

"stef" a écrit

> je croyais que bezout, c'était seulement si a et b premiers entre eux
alors
> il existe u et v tq au+bv=1...

- Si a et b sont des entiers quelconques, il existe u et v tels que
au+bv=pgcd(a,b).

- Si on a la relation au + bv = d, d n'est pas nécessairement le pgcd de
a et b. Tout ce qu'on peut dire, c'est que d est un multiple de ce pgcd.
Par exemple, pour a = 10 et b = 14, on a 2*10 - 1*14 = 6 =
3*pgcd(10,14).

- Mais dans le cas où au + bv = 1, alors 1 est un multiple du pgcd de a
et b, donc ce pgcd est nécessairement lui-même égal à 1, et a et b sont
premiers entre eux.

Voilà. J'espère que c'est plus clair.

Cordialement
Stéphane

[Anonyme]

Stéphane Ménart a écrit
> - Si a et b sont des entiers quelconques,
> il existe u et v tels que au+bv=pgcd(a,b).

et réciproquement ... Autrement dit :
Un entier est la somme d'un multiple de a et d'un
multiple de b ssi c'est un multiple de pgcd(a, b).

Mais la question étant :
> Soit d=pgcd(a,b) si c divise a et b est ce que c divise d?

la réponse est simplement : c | a et a | d => c | d

l'hypothèse c | b est inutile

--
Pierre
pierre-capdevila@wanadoo.fr

[Anonyme]

Le Sun, 14 Sep 2003 14:25:20 +0200,
Pierre Capdevila grava à la saucisse et au marteau:

> Mais la question étant :[color=green]
> > Soit d=pgcd(a,b) si c divise a et b est ce que c divise d?
>
> la réponse est simplement : c | a et a | d => c | d[/color]

Si je puis me permettre, vous êtes allés un peu vite. a ne divise pas d
(sauf si a=d). On a plutôt d|a.

--
Genji
"Il n'y a pas d'amis, il n'y a que des moments d'amitié."
Jules Renard

[Anonyme]

Oups. J'ai confondu PPCM et PGCD.

Merci,

--
Pierre
pierre-capdevila@wanadoo.fr