Forum de mathématiques - Bibm@th.net

Bob

Invité

PGCD Ts [Résolu]

Bonjour,

Salut à toutes et tous, aprés une nuit d'insomnie me voilà de retour. La cause de cette insomnie le petit exo suivant :

n et p , 2 entiers non nuls tels que n² >p

Il faut montrer que PGCD(n,p) = PGCD (n-p² , p)

je sais pas trop par quel bout prendre ça ...

Au plaisir de vous lire
Votre Bob dévoué

P.S.
J'espère que Yoshi ne s'ennuie pas sans ces élèves merveilleux que nous sommes !

ybebert

Membre

Lieu : Montpellier

Inscription : 30-08-2006

Messages : 123

Re : PGCD Ts [Résolu]

Salut Bob !

Te voilà à nouveau parmi nous !
je pense que tu as voulu écrire n >p²  pour que n-p² reste >0

Sinon je n'ai pas encore trouvé, faut peut-etre utiliser le fait que pgcd(a,b) = pgcd(a-b,b) mais je n'arrive pas à conclure...
J'espère que John, Yoshi ou Fred passeront par là ....

Comment ça marche cette terminale ???
A+

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : PGCD Ts [Résolu]

Bonjour Master Bob,

Dans ce qui suit, je pars du postulat qu'il y a une faute de frappe : je prends n>p² et non n²>^p (je vais continuer à chercher au cas où...)
Si on n'a pas n>p², alors n<=p²..
Si n=p², alors PGCD(n-p²,p)=PGCD(0,p)= p. et PGCD(n,p)=PGCD(p²,p)=PGCD(p²-p²,p)=PGCD(0,p)=p
Mais si n-p²<0, ça cloche...

Ca m'a rappelé la méthode des soustractions successives.
Avec n>p, on peut écrire avec certitude PGCD(n;p)=PGCD(n-p,p)
Avec n>2p, on peut écrire PGCD(n-2p,p)=PGCD(n-p,p)+PGCD(n,p)
...............
Avec n>p², il vient donc PGCD(n-p²,p)=PGCD(n-p,p)=PGCD(n,p)

@+

PS : Doit bien avoir du Bezout, là-dessous...
PS2 : Non, rien de rien, non je ne regrette rien ... (air connu) ;-)

Barbichu

Membre actif

Inscription : 15-12-2007

Messages : 405

Re : PGCD Ts [Résolu]

Hello,
À priori, je ne vois pas grande utilité à l'inégalite imposée.
En effet, quels que soient a et b entiers relatifs : pgcd(a,b) = pgcd(a-b,b)
Ensuite comme le dit yoshi : pgcd(n-p²,p) = pgcd(n-(p-1)p,p) = pgcd(n-(p-2)p,p) = ... = pgcd(n,p)

Si la condition est n²>p, j'imagine que c'est pour la suite
Si c'est n>p², j'imagine que c'est pour assurer la positivité dans la suite
Dans tout les cas, la condition n'est pas utile dans cette question.
++

[edit] modifier c'est bien, ça permet de supprimer ses conneries ;)[/edit]

Dernière modification par Barbichu (16-12-2007 16:51:08)

Bon

Invité

Re : PGCD Ts [Résolu]

Merci à tous mais décidément j'ai du mal avec l'arithmétique (rien que l'orthographe !)

Comment Yoshi peux-tu écrire ça :
Avec n>p², il vient donc PGCD(n-p²,p)=PGCD(n-p,p)=PGCD(n,p)

De même Barbichu
dans pgcd(n-p²,p) = pgcd(n-(p-1)p,p) = pgcd(n-(p-2)p,p) = ... = pgcd(n,p)  il restera toujours des p²

Merci de vos lumières

Au plaisir de vous lire
Votre Bob dévoué

Barbichu

Membre actif

Inscription : 15-12-2007

Messages : 405

Re : PGCD Ts [Résolu]

PS : Doit bien avoir du Bezout, là-dessous...

Comme an + bp = a(n-p²) + (b+ap)p
Si on choisit a et b tq an+bp = pgcd(n,p)
on a pgcd(n,p) dans (n-p²)Z+pZ, doù pgcd(n-p²,p) divise pgcd(n,p)

De même avec a(n-p²) + bp = an + (b-ap)p
d'où pgcd(n,p) divise pgcd(n-p²,p)

D'où l'égalite.

Barbichu

Membre actif

Inscription : 15-12-2007

Messages : 405

Re : PGCD Ts [Résolu]

Merci à tous mais décidément j'ai du mal avec l'arithmétique (rien que l'orthographe !)

Comment Yoshi peux-tu écrire ça :
Avec n>p², il vient donc PGCD(n-p²,p)=PGCD(n-p,p)=PGCD(n,p)

De même Barbichu
dans pgcd(n-p²,p) = pgcd(n-(p-1)p,p) = pgcd(n-(p-2)p,p) = ... = pgcd(n,p)  il restera toujours des p²

Merci de vos lumières

Au plaisir de vous lire
Votre Bob dévoué

Salut,
on écrit simplement p² sous la forme p*p

Je reprends :
on sait que pgcd(a,b) = pgcd(a+b,b)
en prenant a = n - kp  et b = p
on obtient que :
pgcd(n-kp,p) = pgcd(n-kp+p,p) = pgcd(n-(k-1)p,p)   (*)

Maintenant en prenant cette égalite pour k=p, puis k=p-1 ...etc ...
On obtient :
pgcd(n-pp,p)      = pgcd(n-(p-1)p,p) pour k=p
pgcd(n-(p-1)p,p) = pgcd(n-(p-2)p,p) pour k=p-1
pgcd(n-(p-2)p,p) = pgcd(n-(p-3)p,p) pour k=p-2
....................... = .....................  pour ....
pgcd(n-2p,p)      = pgcd(n-p,p)       pour k=2
pgcd(n-p,p)        = pgcd(n,p)         pour k=1

en mettant bout a bout ces égalités on a le résultat voulu.
En espérant que ce soit plus clair cette fois-ci

[edit]
En fait pour être tout à fait rigoureux, il faudrait mettre en place une récurrence.
En conservant les notations ci-dessus, l'hypothèse H_k de récurrence serait :
H_k = " pgcd(n-kp,p) = pgcd(n,p) "
* H_0 est triviale
* H_k se démontre à partir de H_(k-1) en utlisant (*)
[/edit]

Dernière modification par Barbichu (16-12-2007 17:16:38)

Bon

Invité

Re : PGCD Ts [Résolu]

Ok, Barbichu maintenant j'ai compris. C'est le départ qui est pas évident, c.a.d. de poser :
"en prenant a = n - kp  et b = p"

Merci à tous de vos lumières. Mais que c'est dur !!!!

Bon la terminale se passe comme ci, comme ça ... un petit 10,25 de moyenne en math . Un 12 en physique/chimie. Pas terrible quoi...

Encore merci

Au plaisir de vous lire
Votre Bob dévoué

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : PGCD Ts [Résolu]

Bonsoir,

Je m'incline bien bas devant la science de mon éminent "petit camarade" Barbichu...

Ce que j'ai simplement remarqué et je vais prendre un exemple numérique n = 105 et p=10 (ainsi n>p²), c'est cela :
105-10 = 95, 95-10=85 et PGCD(105,10)=PGCD(95,10)=PGCD(85,10)... (c'est l'essence même de la méthode des soustractions) et je me suis demandé combien de fois on pouvait soustraire p à n sans autre info que n > p² sans risque de passer dans le négatif... La réponse est évidente : p fois !
Et soustraire p fois p, c'est soustraire p²...

@+

PS : Ô éminent Barbichu ! Puis-je te remettre en mémoire tes "humanités" passées : "Errare humanum est...".. ? Donc, pas si grave si on tient compte de la suite : "...sed persevare diabolicum !" ;-)

Barbichu

Membre actif

Inscription : 15-12-2007

Messages : 405

Re : PGCD Ts [Résolu]

Mon cher yoshi, je n'avais jamais remarqué un tel penchant pour le latin chez toi, jusque là ...