Algorithme d'Euclide, identité de Bezout, théorème de gauss

par **melimelot** » 29 Oct 2013, 12:02

Bonjour,
alors voilà, j'ai un DM de maths et je suis complètement coincée !

Voici le sujet :
"Léo prend le métro pour aller au travail. A la station Bézout, il doit changer de rame, la correspondance est sur le quai. Il sait que son premier métro (ligne A-durée du trajet : 8 minutes) passe toutes les 7 minutes.
Ce matin, il a pris son premier métro à 6h52, il est arrivé à 7h à la station Bézout et il a du attendre 6 minutes la rame de la ligne B.
Léo voudrait savoir à quelle heure partir entre 6h et 9h pour ne pas attendre la rame de la ligne B à la station Bézout.
On note x le nombre de rames de la ligne A et y le nombre de rame de la ligne B passées à la station Bézout après 7h.

1-Montrer que, pour que l'attente soit nulle à la station Bézout, x et y doivent vérifier l'équation 7x-11y=-5.

2- Déterminer une solution particulière de l'équation.

3- Déterminer l'ensemble des solutions entières de l'équation.

4- Déterminer à quelles heures entre 6 h et 9 h, Léo peut prendre son premier métro pour ne pas attendre à la station Bézout."

J'ai comprise les deux première questions.
Je suis bloqué à la troisième question, voici ce que j'ai fais pour cette question :
Cherchons toutes les solutions. Appelons (Xo;Yo) une solution quelconque.
système : 7Yo - 11Yo = -5
7*15 - 11*10 = -5
On peut en déduire :
7(Xo-15) - 11 (Yo-10) = 0
7 (Xo-15) = 11 (Yo-10)

Théorème de Gauss :
7 divise 11(Yo-10).
7 et 11 sont premiers entre eux.
Donc 7 divise (Yo-10)
C.a.d. qu'il existe k (k appartient à Z) tel que 7k = Yo-10
Donc Yo = 7k+10
Ainsi : 7(Xo-15) = 11 (7k +10 -10)
Xo = 11k +15

Jusqu'ici, pas de problème, mais je suis coincée après :

Cherchons k pour que (Xo,Yo) soient entiers et positifs.
système : 7k +10 >>(supèrieur ou égal) à 0
11k+15 >>0

correspond (système) : 7k >> -10
11k >> -15

correspond (système) : k >> -10/7
k >> -15/11
Je suis bloquée parce que je n'obtient pas ...<< k >>...
Du coup, je ne peux pas obtenir de couples de solutions ?

par **busard_des_roseaux** » 29 Oct 2013, 15:23

melimelot a écrit:J'ai compris les deux première questions.

tu peux expliquer d'où vient le 11y, je ne vois pas.

par **melimelot** » 29 Oct 2013, 15:30

busard_des_roseaux a écrit:tu peux expliquer d'où vient le 11y, je ne vois pas.

11y viens de l'équation 7x-11y=-5.
Je ne comprend pas votre question ? :doh:

par **busard_des_roseaux** » 29 Oct 2013, 15:32

sur la 2ème ligne, les trains passent toutes les 11 minutes ?

par **melimelot** » 29 Oct 2013, 15:41

busard_des_roseaux a écrit:sur la 2ème ligne, les trains passent toutes les 11 minutes ?

A oui, excusez moi j'ai fait une erreur de frape !
Le second (ligne B) passe toutes les 11 minutes ! :triste:

par **busard_des_roseaux** » 29 Oct 2013, 15:52

et pourquoi -5 s'il attend 6 minutes ?

par **melimelot** » 29 Oct 2013, 15:59

busard_des_roseaux a écrit:et pourquoi -5 s'il attend 6 minutes ?

-5 correspond à la durée d'attente - la durée d'arrivée
C'est à dire 11-6 = 5
Et comme ce temps et perdu, on obtiens 7x-11y=-5.
Enfin, c'est ce que j'ai compris personellement :lol3:

par **busard_des_roseaux** » 29 Oct 2013, 16:35

d'accord, j'ai compris, tu égalise 7x avec 11y-5.

11y-7x=5

11=7+4
7=4+3
4=3+1
1=4-3=4-(7-4)=2x4-7=2(11-7)-7=2*11-3*7

10*11-15*7=5
11y-7x=5

11(y-10)=7(x-15)
x=15+11k
y=10+7k

par **melimelot** » 29 Oct 2013, 16:45

Oui, je suis arrivée au même résultats :we:
Ensuite, j'ai cherche un nombre k pour que (Xo ; Yo) soient entiers et positifs.
Système :7k+10 >> (supérieur ou égal) 0
11k+15>>0

Système : 7k>>-10
11k>>-15

Système : k>>-10/7 (environ -1.4)
k>>-15/11 (environ -1.3)

Donc k doit être supérieur à -1
Si k>>-1
Alors 7k>>-7 (multiplication par 7)
Et 7k+10>>0

Ainsi Yo=7k+10 Soit Yo=3
Et Xo=11k+15 soit Xo=4
Donc on obtient une solution qui est (4;3)

Donc, je me retrouve avec deux solutions, mais grâce à mon tableau je vois qu'il y en a 3, comment puis-je trouver la troisième ?

par **melimelot** » 29 Oct 2013, 17:36

Je suis toujours perdue a cet endroit :help:

par **busard_des_roseaux** » 30 Oct 2013, 11:36

re-bonjour,

l'heure a une structure affine,ie, on passe d'un instant

à un instant

en ajoutant une durée

Léo part à l'instant t, ie, 6h52 modulo 7 minutes.

il arrive 8 minutes plus tard, à 6h55, modulo 11 minutes

t=6h52+7k
t+8=6h55 + 11k'

en soustrayant

8=3+11k'-7k
7k-11k'=-5

k=15+11k''
k'=10+7k''

en instants
6h

6h52 + 105 +77k''

9H

en durées

d'où trois solutions k"=

Algorithme d'Euclide, identité de Bezout, théorème de gauss

Algorithme d'Euclide, identité de Bezout, théorème de gauss

Qui est en ligne