Le pgcd

[mona]

coucou a tous !
juspert que vous allez bien !

j'ai un petit exercice a faire
vous pouvez me dire si j 'ai bon
mercii



consigne
1)Calculer le pgcd de 7200 et7201
ma réponse : pgcd(7200;7201)=1

2) Que peut on dire du PGCD de deux nombres entiers consécutifs?
je peux dire du pgcd de deux nombres entiers consécutifs qu'il est toujours égal a 1

Est ce que c 'est bon?

[Anonyme]

oui vrai

On dit aussi qu'ils sont premiers entre eux

[oscar]

bonjour

Tu dois le prouver

[le_fabien]

bonjour

Tu dois le prouver

Bonjour,
peut être pas au niveau collège. :zen:

[Matt_01]

Ca reste quand même vachement abordable si on sait que PGCD(1;a)=1 et que pgcd(a;b)=pgcd(b-a;b) non ?

[Anonyme]

Ca reste quand même vachement abordable si on sait que PGCD(1;a)=1 et que pgcd(a;b)=pgcd(b-a;b) non ?

faut aussi demontrer pourquoi
pgcd(a;b)=pgcd(b-a;b)
meme en seconde je ne l'ai jamais vu cette relation

[Sve@r]

meme en seconde je ne l'ai jamais vu cette relation

Moi non plus. A mon époque on décomposait les 2 nombres en produits de facteurs premiers et on ne gardait que les facteurs communs mais mon élève l'a vu en 3° (cette année) sous le nom "Algorithme d'Euclide" (ce qui est à la fois légèrement faux car l'algorithme d'Euclide dit que pgcd(a,b)=pgcd(b, a modulo b) et à la fois vrai car le modulo se calcule aussi en faisant des soustractions successives). Mais bon, cela lui a bien été enseigné comme étant un théorème à retenir et à utiliser.

[Anonyme]

Je connais l'algorithme d'euclide mais je ne me souvient pas de l'avoir appris au college ni meme cette annee en effet on faisant la decomposition en facteur premier et ....

oui mais dans cette relation:
pgcd(a;b)=pgcd(b-a;b)

rien ne dit qu'il faut faire des soustractions succesives afin d'arriver au reste
je pense que celle ci est beaucoup plus adequate :

pgcd(a;b)=pgcd(a%b;b)

[Timothé Lefebvre]

Salut,

la relation dont tu parles découle de l'algorithme d'Euclide.

Tu prends la suite d'entiers naturels tel que et le reste de la division euclidienne de a par b.

On tombe sur

J'espère que c'est assez clair.

[Matt_01]

Quand on m'a introduit le pgcd, on utilisait les soustractions (on l'avait admit, même si la demonstration est simple)

[Anonyme]

Salut,

la relation dont tu parles découle de l'algorithme d'Euclide.

Tu prends la suite d'entiers naturels tel que et le reste de la division euclidienne de a par b.

On tombe sur

J'espère que c'est assez clair.

pas vraiment
je ne vois pas comment la relation pgcd(a;b)=pgcd(b-a;b)
decoule de l'algorithme d'euclide

[Timothé Lefebvre]

La démo est la suivante, je vais faire court :

La division euclidienne de a par b s'écrit avec

Si b|a alors et donc on s'arrête à

Si b ne divise pas a alors la division euclidienne de b par

donne : avec

On suppose que , et donc

et

On va tomber sur de l'absurde, tu vas voir pourquoi.

Donc la suite est strictement décroissante ok ?

De plus, ce qui implique que et 4

et donc

Dis-le si tu ne suis pas !

Après, je ne le ferai pas en entier mais par récurrence tu

montres que

Au final on a et là tu vois tout de suite où est l'absurde !

Ceci nous prouve qu'au bout d'un certain nombre de divisions on tombera forcément sur un reste nul.
On pose le dernier reste non nul.

On sait que le PGCD de deux entiers naturels non nuls a et b est égal au PGCD du quotient q et du reste r de la division euclidienne de a par b, ce qui nous donne

(ça se démontre aussi).
Si on applique ça à la suite on tombe bien sur ce que je disais dans mon message précédent.

J'ai oublié de préciser qu'on avait et que donc .

Tu comprends ?

Tu remarques qu'on prouve par la même occasion que l'algorithme d'Euclide nous donne bien le PGCD de a et b.

EDIT : désolé, il est vrai que ça n'a rien à faire au collège.

[Anonyme]

deja la 3eme ligne
b|a ca veut dire quoi ? je suppose b divise a non ?
et dans la meme ligne P represente quoi ?

je trouve cette demonstration trop complique par la suite (au fait c'est quel niveau ?)

En plus j'ai reussi a demontrer l'algorithme d'une autre facon

A=Bq + R
Soit g le PGCD de A et B g divise donc A et B on peut dont ecrire

A= C*g
B= D*g
On aura don
C*g = D*g*q +R
R= g*(C-D*q)

donc g divise aussi le reste R

Donc PGCD(A,B)=PGCD(B,R)
et on repete cette operation jusqu'a obtenir PGCD(Rn,0)=Rn

et pour PGCD(A,B)=PGCD(A-B,B)
on le demontre dde la facon suivante

soit g le PGCD(A,B)

A=g*q1
B=g*q2

A-B= g(q1-q2)

donc g divise aussi A-B
Donc PGCD(A,B)=PGCD(A-B,B)

PS: Je t'ai envoye un Mp hier l'as tu recu ?

[Timothé Lefebvre]

Ah oui je n'ai pas précisé.

Dans la suite , pour n supérieur ou égal à 1 et différent de 0 , est le reste de la division euclidienne de par alors il existe un entier p tel que différent de 0 pour tout ,

Cette démonstration exige des connaissances sur les suites et le raisonnement par récurrence, au programme de première.

b|a veut bien dire b divise a.

Essaye de renvoyer ton MP je viens de faire du ménage dans ma boîte (j'arrivais aux 500 ...).

[Anonyme]

Mp envoye

Est ce que mes 2 demonstration son correctes ?

[iLove]

Enfait cette démonstration s'étudie en terminale S spé Maths normalement...
Sinon la démonstration de 2 nombres entiers consécutifs premiers entre eux ça ne se voit pas au collège mais bon sinon ya plus simple:
Soit n appartient N
On note d=PGCD(n;n+1)
d l n (se lie d divise n)
d l n+1
donc d l (n+1)-n
d l 1
donc d=1

[Sve@r]

Soit n appartient N
On note d=PGCD(n;n+1)
d l n (se lie d divise n)
d l n+1
donc d l (n+1)-n
d l 1
donc d=1

Arf, démo agréable et simple à comprendre, même au collège. :id:

[Matt_01]

Cela revient encore à la même chose : admettre que et implique divise toute combinaison linéaire de et .

Dans ces cas là, je trouve que est plus rapide.
En vérité ca repose exactement sur la même propriété.