[spé] PGCD

par **Anonyme** » 14 Déc 2010, 20:30

Bonjour,

J'ai un gros trou concernant le PGCD.
Bon, donc on a une équation diophantienne, du type ax + by = c. On sait que PGCD (a,b) = 1 et on veut montrer que PGCD (x,y) = 1 ou c.
Je ne vois pas du tout comment faire... Je pensais dire que PGCD (ax,by) = 1 ou c mais faut-il encore le démontrer. :) Pourriez-vous me mettre sur la bonne piste svp ?

Merci d'avance :)

par **Anonyme** » 14 Déc 2010, 21:09

En fait, c'est facile. Problème résolu :)

par **sad13** » 14 Déc 2010, 21:14

Autant l'écrire pour faire profiter tes collègues sinon le post aura été ouvert " à blanc" merci et bonne soirée

par **Anonyme** » 14 Déc 2010, 21:21

Alors on a le théorème de Bézout, ce qui nous permet de trouver un couple (x,y) tel que ax+by = 1
Ensuite, on multiplie chaque membre de ce couple par c, et on résout ax+by = c...
Il suffit de montrer qu'un des deux membres du couple de l'ensemble des solutions ne soit pas divisible par c, et dans ce cas-là, PGCD (x,y) = 1 ou PGCD (x,y) = c. :)

par **sad13** » 14 Déc 2010, 21:26

que ax+by = 1
Ensuite, on multiplie chaque membre de ce couple par c, et on résout ax+by = c...

plutot axc+byc=c tu veux dire

par **Anonyme** » 14 Déc 2010, 21:27

Heu je pensais aX+bY = c (avec implicitement X=cx et Y=cy)

par **sad13** » 14 Déc 2010, 21:41

ok nickel t en Term S spé?

par **Anonyme** » 14 Déc 2010, 21:42

Oui... :we:

par **benekire2** » 14 Déc 2010, 21:45

Tient, rapidement ( traité dans le forum il y a peu , mais marrant) soit a et b deux entiers positifs. E={ua+vb(u,v)N²} donne moi une CNS pour que N\E soit fini :++:

par **Anonyme** » 14 Déc 2010, 21:47

Alors là aucune idée car je ne sais ni ce qu'est CNS et N\E... :D

par **sad13** » 14 Déc 2010, 21:47

N\E c'est le complémentaire de E? ou N quotienté par E ?

par **benekire2** » 14 Déc 2010, 21:53

sad13 a écrit:N\E c'est le complémentaire de E? ou N quotienté par E ?

Simplement N ( entiers naturels) sans la partie E.

Sinon, une CNS, c'est une "condition nécessaire et suffisante" ( tu comprends pourquoi j'abrège :ptdr: )

par **Anonyme** » 14 Déc 2010, 21:56

Bon, alors il est nécessaire que E soit infini. Mais c'est pas suffisant étant donné que tout ensemble infini peut se subdiviser en deux ensembles infinis... (ex : 2N et N\2N)
Je dirais que u=1 ou v=1 ?

par **sad13** » 14 Déc 2010, 22:15

Ok merci, excellente question

par **benekire2** » 14 Déc 2010, 22:22

Aaaie a écrit:Bon, alors il est nécessaire que E soit infini. Mais c'est pas suffisant étant donné que tout ensemble infini peut se subdiviser en deux ensembles infinis... (ex : 2N et N\2N)
Je dirais que u=1 ou v=1 ?

Excuse moi , j'ai encore mal posé la question, c'est donner une CNS sur (a,b) pour que N\E soit fini.

Indice >>> Intéresse toi d'abord et surtout a E, en fait, essaye avec genre (a,b)=(2,4) et regarde ce que tu en pense ... alors ?

par **Anonyme** » 14 Déc 2010, 22:27

Ah d'accord, sur (a,b).
Donc pour (a,b)=(2,4) : E={2u+4v(u,v)N²}
E = {2(u+2v)(u,v)N²}

Dans ce cas-ci, E est fini mais N\E l'est aussi...

par **sad13** » 15 Déc 2010, 19:10

la réponse svp

par **Euler07** » 15 Déc 2010, 19:14

sad13 a écrit:la réponse svp

Un peu de patience :hum:

par **Anonyme** » 15 Déc 2010, 19:14

J'adore comment Sad13 supervise... :D

par **sad13** » 15 Déc 2010, 19:29

lol supervise? non mais je suis de nature impatient et voilà

[spé] PGCD

[spé] PGCD

Qui est en ligne