Système

[Anonyme]

bonjour je ne parviens pas à résoudre le système suivant :

6x + 12 y = 12 (modulo 36)
13x + 7y = 5 (modulo 36)

si vous pouviez m'expliquer comment faire pour trouver toutes les solutions
dans Z² et utiliser une méthode générale pour résoudre ce genre de système
Merci d'avance

[Anonyme]

Am 3/02/04 18:48, sagte Mathos (matherminator@hotmail.com) :

> bonjour je ne parviens pas à résoudre le système suivant :
>
> 6x + 12 y = 12 (modulo 36)
> 13x + 7y = 5 (modulo 36)
>
> si vous pouviez m'expliquer comment faire pour trouver toutes les solutions
> dans Z² et utiliser une méthode générale pour résoudre ce genre de système
> Merci d'avance

comment ferait tu dans R ?
multiplie par exemple la première équation par -7 et la seconde par 12...
tu obtiens 126 x = - 24 [36]
ie 22 x = 2 [36]
11 x = 1 [18]

il existe une réponse quasi-triviale (0<x<10), sinon tu résoud ca avec
l'algorithme d'Euclide
ne pas oublier qu'il existe ensuite une infinité de solutions (x + 36k)

le problème c'est qu'après en remplacant tu va t'apercevoir qu'il n'existe
alors pas de y satisfaisant
Dons si je ne me suis pas trompé ce système n'admet pas de solution.

albert

[Anonyme]

Mathos a écrit:
> bonjour je ne parviens pas à résoudre le système suivant :
>
> 6x + 12 y = 12 (modulo 36)
> 13x + 7y = 5 (modulo 36)
>
> si vous pouviez m'expliquer comment faire pour trouver toutes les solutions
> dans Z² et utiliser une méthode générale pour résoudre ce genre de système

Je suppose que x et y doivent être entiers ?

On s'arrange pour faire une opération membre à membre entre les 2
équations pour 'élimner' une des inconnues. Par exemple ici on fera 13
fois la première - 6 fois la seconde, pour arriver à :
(13*12-6*7)*y = 13*12 -5*6 (modulo 36)
ou encore 114 * y = 18 (modulo 36) parce que 156 - 30 = 126 = 108 + 18 =
3* 36 + 18 ; pour avoir cela 114*y doit donner 18 comme reste dans sa
division par 36 ; il faut donc trouver un multiple de 114 qui, divisé
par 36, donne le reste 18 ; en simplifiant autant que je peux, j'arrive
à 6*a+3 multipe de 19, la première solution est 57 pour a = 9 qui
correspond à y=3
Il reste à trouver x (en reportant y=3 dans une des équations initiales)
et à montrer que toutes les solutions sont des multiples de la plus
petite...

> Merci d'avance
de rien
PAUL

[Anonyme]

albert junior a écrit:
> Am 3/02/04 18:48, sagte Mathos (matherminator@hotmail.com) :
>
>[color=green]
>>bonjour je ne parviens pas à résoudre le système suivant :
>>
>>6x + 12 y = 12 (modulo 36)
>>13x + 7y = 5 (modulo 36)
>>
>>si vous pouviez m'expliquer comment faire pour trouver toutes les solutions
>>dans Z² et utiliser une méthode générale pour résoudre ce genre de système
>>Merci d'avance
>
>
> comment ferait tu dans R ?
> multiplie par exemple la première équation par -7 et la seconde par 12...
> tu obtiens 126 x = - 24 [36]
> ie 22 x = 2 [36]
> 11 x = 1 [18][/color]

HUM, je trouves pas ça, moi...

> il existe une réponse quasi-triviale (0 l'algorithme d'Euclide
> ne pas oublier qu'il existe ensuite une infinité de solutions (x + 36k)
>
> le problème c'est qu'après en remplacant tu va t'apercevoir qu'il n'existe
> alors pas de y satisfaisant
> Dons si je ne me suis pas trompé ce système n'admet pas de solution.
>
> albert
>

[Anonyme]

Am 3/02/04 21:27, sagte Paul Delannoy (delannoy@univ-lemans.fr) :
[color=green]
>> comment ferait tu dans R ?
>> multiplie par exemple la première équation par -7 et la seconde par 12...
>> tu obtiens 126 x = - 24 [36]
>> ie 22 x = 2 [36]
>> 11 x = 1 [18]
>
> HUM, je trouves pas ça, moi...
>[/color]
pardon
mais ca me rassure quant à mon résultat final

[Anonyme]

"Mathos" wrote:

>bonjour je ne parviens pas à résoudre le système suivant :
>
>6x + 12 y = 12 (modulo 36)
>13x + 7y = 5 (modulo 36)
>
>si vous pouviez m'expliquer comment faire pour trouver toutes les solutions
>dans Z² et utiliser une méthode générale pour résoudre ce genre de système
>Merci d'avance
>
Diviser la 1ere equation par 6, puis la multiplier par 13, ca donne:
13x + 26y = 26 mod 36
Ensuite soustraire la 2e de la 1ere, ca donne 19y=21 mod 36.
Puisque 19 et 36 sont copremiers, il y a une solution garantie, soit
que tu utilises l'algorithme d'Euclide étendu pour la trouver, ou
encore par essai et erreur à la main tu trouves que y=3 est une
solution.
Ensuite tu substitues ca dans disons la 2e équation, ca donne 13x=20
mod 36, ici encore Euclide étendu, où à la main (c'est un peu plus
long) tu trouves x=32.
Toutes les solutions sont du genre x=32+30k, y=3+6k, k entier.

[Anonyme]

Je vous remercie de votre aide j'ai compris le raisonnement à mener.

"Sylvain Croussette" a écrit dans
le message de news:s020205efgh05csvjjm6d0iesmbj2kemds@4ax.com...
> "Mathos" wrote:
>[color=green]
> >bonjour je ne parviens pas à résoudre le système suivant :
> >
> >6x + 12 y = 12 (modulo 36)
> >13x + 7y = 5 (modulo 36)
> >
> >si vous pouviez m'expliquer comment faire pour trouver toutes les[/color]
solutions[color=green]
> >dans Z² et utiliser une méthode générale pour résoudre ce genre de[/color]
système[color=green]
> >Merci d'avance
> >
> Diviser la 1ere equation par 6, puis la multiplier par 13, ca donne:
> 13x + 26y = 26 mod 36
> Ensuite soustraire la 2e de la 1ere, ca donne 19y=21 mod 36.
> Puisque 19 et 36 sont copremiers, il y a une solution garantie, soit
> que tu utilises l'algorithme d'Euclide étendu pour la trouver, ou
> encore par essai et erreur à la main tu trouves que y=3 est une
> solution.
> Ensuite tu substitues ca dans disons la 2e équation, ca donne 13x=20
> mod 36, ici encore Euclide étendu, où à la main (c'est un peu plus
> long) tu trouves x=32.
> Toutes les solutions sont du genre x=32+30k, y=3+6k, k entier.[/color]

[Anonyme]

je suis désolé mais je m'aperçois que je ne parviens pas a trouver les
solutions de x bien qu'ayant trouvé grâce à votre aide que y= 3 + 6k

si vous pouviez me détailler la fin de la résolution du système je vous en
serais gré.
merci

[Anonyme]

Dans l'article ,
"Mathos" a écrit:

> je suis désolé mais je m'aperçois que je ne parviens pas a trouver les
> solutions de x bien qu'ayant trouvé grâce à votre aide que y= 3 + 6k
>
> si vous pouviez me détailler la fin de la résolution du système je vous en
> serais gré.
> merci
>
>


13x + 7y = 5 (modulo 36).

Disons 13x + 7y = 5 + 36m.

Donc 13x + 7(3 + 6k) = 5 + 36m

13x = 36m - 42k -16. (1)

Or, g.c.d.(13, 36) = 1

= 4*36 - 11*13 (identité de Bezout).

Ainsi on multiplie l'équation (1) par -11:

- 11*13x = - 11*36m + 11*42k + 11*16

Ajouter des multiples de 36:

x = - 6k - 4 (modulo 36).

Enfin nous avons les solutions

x = 36j - 6k - 4

y = 6k + 3

q.q. soient les entiers j, k.

En effet elles satisfont au système original.

Ken Pledger.

[Anonyme]

"Mathos" wrote:

>je suis désolé mais je m'aperçois que je ne parviens pas a trouver les
>solutions de x bien qu'ayant trouvé grâce à votre aide que y= 3 + 6k
>
>si vous pouviez me détailler la fin de la résolution du système je vous en
>serais gré.
>merci
>
Apres avoir trouvé y=3, on substitue dans les équations, ca donne:
6x = 12 mod 36
13x = 20 mod 36
Et là on trouve que x=32 est la solution.

Ensuite pour trouver toutes les solutions, je fais comme ceci: on sait
qu'elles s'écrivent sous la forme x=32 + a*k, y=3+b*k pour k entier.
Ceci est vrai entre autres pour k=1, alors je substitue dans les
équations originales:
6(32+a) + 12(3+b) = 12 mod 36
13(32+a) + 7(3+b) = 5 mod 36
devient
6a+12b=0 mod 36
13a+7b=0 mod 36
On resoud pour b:
78a+156b=0 mod 36
-78a-42b=0 mod 36
Donc 114b=0 mod 36
La premiere solution non triviale est b=6
Substituer:
6a+72=0 mod 36
13a+42=0 mod 36
On trouve a=30.

Donc toutes les solutions ont la forme x=32+30k, y=3+6k, Evidemment
c'est modulo 36. Donc pour k=1 par exemple, x=62 mod 36=26 et y=9.

Si on fait le détail ca donne les paires:
x, y
2 33
8, 27
14, 21
20, 15
26, 9
32, 3

On pourrait aussi écrire les solutions sous la forme
x=2+6k, y=33+30k mod 36.

Il y a peut-etre une facon plus simple de procéder, mais en tout cas
c'est comme ca que je fais.

[Anonyme]

merci beaucoup pour votre aide très utile !!
"Sylvain Croussette" a écrit dans
le message de news:ac02205avusene8rkes5to7rodrekju2g9@4ax.com...
> "Mathos" wrote:
>[color=green]
> >je suis désolé mais je m'aperçois que je ne parviens pas a trouver les
> >solutions de x bien qu'ayant trouvé grâce à votre aide que y= 3 + 6k
> >
> >si vous pouviez me détailler la fin de la résolution du système je vous[/color]
en[color=green]
> >serais gré.
> >merci
> >
> Apres avoir trouvé y=3, on substitue dans les équations, ca donne:
> 6x = 12 mod 36
> 13x = 20 mod 36
> Et là on trouve que x=32 est la solution.
>
> Ensuite pour trouver toutes les solutions, je fais comme ceci: on sait
> qu'elles s'écrivent sous la forme x=32 + a*k, y=3+b*k pour k entier.
> Ceci est vrai entre autres pour k=1, alors je substitue dans les
> équations originales:
> 6(32+a) + 12(3+b) = 12 mod 36
> 13(32+a) + 7(3+b) = 5 mod 36
> devient
> 6a+12b=0 mod 36
> 13a+7b=0 mod 36
> On resoud pour b:
> 78a+156b=0 mod 36
> -78a-42b=0 mod 36
> Donc 114b=0 mod 36
> La premiere solution non triviale est b=6
> Substituer:
> 6a+72=0 mod 36
> 13a+42=0 mod 36
> On trouve a=30.
>
> Donc toutes les solutions ont la forme x=32+30k, y=3+6k, Evidemment
> c'est modulo 36. Donc pour k=1 par exemple, x=62 mod 36=26 et y=9.
>
> Si on fait le détail ca donne les paires:
> x, y
> 2 33
> 8, 27
> 14, 21
> 20, 15
> 26, 9
> 32, 3
>
> On pourrait aussi écrire les solutions sous la forme
> x=2+6k, y=33+30k mod 36.
>
> Il y a peut-etre une facon plus simple de procéder, mais en tout cas
> c'est comme ca que je fais.
>[/color]