Les démonstrations : algorithme d'Euclide

Sujets pour toutes les démonstrations en particulier l'algorithme d'Euclide .

bonjour, j'ai un DM a faire et c'est assez urgent voici un des exos a faire:
a et b sont deux entiers tels que a >b.On appelle r le reste de la division euclidienne de par b.

demontrer que si c est un diviseur de a et de b, alors c est un diviseur de r.
demontrer que si c est un diviseur de b et de r,alors c est un diviseur de a .
en deduire que les diviseurs communs de a et b sont les diviseurs communs de b et de r et que PGCD (a;b)=PGCD(b;r) moi et les demonstration sa fait deux!

Bonjour,

Quelle est vraiment la question ?

Je ne sais pas comment mis prendre , pour démontrer ,pour le a) j'aimerais en fait qu'on m'explique comment faire une bonne démonstration.

re.

si c divise a, alors a = ca' ; de même c divise b donc b = cb'

or, la division euclidienne a = bq+r devient ca' = cb'q + r

écris r = c(...) pour prouver cette première assertion a).

ok merci maintenant je comprend un peu mieux cette démonstration.

j'ai écris r =c(bq) sa va?

non : erreur dans le changement de membre et/ou la factorisation.

peut tu m'expliquer surtout que le prof de math n'a pas etudier sa en classe !!

oui

ca' =
cb'q+ r

devient en changeant de membre

ca' -
cb'q= r

d'où par factorisation

r = c(a' - b'q)

ce qui montre que c divise aussi le reste r.

merci, sa va deja mieux et apres pour le 3) j'ai etudier le pgcd j'y arrive bien mais c'est toujours pour démontrer le probleme.

tu as déjà vu en 2 que si c est un diviseur commun du rest r et du diviseur b, alors c est aussi un diviseur du dividende a.

cela veut dire avec 1. que, lorsque a=bq+r, les diviseurs communs au dividende a et au diviseur b sont exactement les diviseurs communs au diviseur b et au reste r.

en particulier pour le pgcd, qui le plus grand d'entre eux.

ainsi dans la recherche du pgcd de a et b, on peut remplacer a par b et b par r, et ainsi de suite (ce qui fait globalement décroître la taille des nombres entiers en jeu et aboutit donc nécessairement...).

merci pour tes explications!

boujour le prof de math il nous a explique un peu en désordre pour eviter qu'on sache tout l'exo et il fait pas la même méthode que toi regarde :
soit x le quotient entier de a par b tel que a=b×x +r
r=a-b×x
c est un diviseur de a donc il existe y un entier tel que a=y×c
c est un divisuer de b donc il existe z un entier tel que b=z×c
ca×cz=c(a-z)
et apres il nous donne pas plus d'explication a nous de continuer j'aimerais que tu m'aide ,merci

salut

c'est très ressemblant pourtant marie ! sauf que ca×cz=c(a-z) est faux !

tu remplaces a=y×c et b=z×c dans r=a-b×x puis tu factorises...

donc la c bon sa va et peut tu aussi m'aider a factorisé? merci

moui
mais je l'ai par exemple fait sur le post Envoyé: 27.09.2008, 10:39

T sur que c sa parce que le prof j'ai peur que si j'ecrit sa il m'enleve des point ,en fait on a jamais vu une factorisation comme sa ,il y a que cette méthode pour factorisé?

c'est la réduction, comme on fait en 4e : 4x + 3x = (4+3)x, non ?

si j'i arrive bien mais pourtant sa fait pas pareille

c'est un peu plus compliqué, mais c'est le même principe. bon je te montre :

r = a-b×x

r = y×
c- z×
c×x =
c(...)

à toi de compléter les ... !

r = y×c - z×c×x = c(z+y) ?

non : c'est r = y×c -
z×c×
x= c(y -
z×x). tu comprends ?

oui et c(y - z×x) est le résulat final?

oui (pardon j'étais distrait) : c'est un multiple de c, et c'est ce qui compte : tu montres comme ça que r est lui-aussi multiple de c.

Puisque c est un diviseur de a et b, il existe x le quotient entier de a par b tel que a=bx +r
C est un diviseur de a donc il existe y un entier tel que a=yc
C est un diviseur de b donc il existe z un entier tel que b=zc
r = a-bx
r = yc – zcx = c (y – zx). Donc c est aussi diviseur de r
sa va comme sa j'ai bien rediger dans le bon ordre?

oui. au début je dirais plutôt :
"Par division euclidienne, il existe x le quotient entier de a par b tel que a=bx +r.
Puisque c est un diviseur de a et b, c est un diviseur de a donc il existe y un entier tel que a=yc "
etc.

merci ,apres dans la question suivante sa me dit de déduire que le pgcd de a et de b = le pgcd de b et de r je fait juste un phrase ? ou je fait un calcul qui le pouve et je fait une conculsion ?

tu dis : on a vu que

1° si c est un diviseur commun de a et de b, alors c est aussi un diviseur de r ; donc c est un diviseur commun de b et de r ;

2° inversement si c est diviseur de r et de b, alors r est diviseur de a et de b.

ceci montre que les diviseurs communs de a et de b sont exactement les mêmes que ceux de b et de r, en particulier pour le pgcd, qui est le plus grand des diviseurs communs.

ok merci