Système d'équations modulaires

ouragh1951

Résoudre le système modulaire
3x_=7[23]
8x_=5[17]
7x_=9[11]
Solution World 
184..51...31...20.....11.....9.....2...1.**.2737..11....9...2...1
.........-3....-1....-1......-1....-1....-4....0.**..0....-248...-1..-4..0
........83..-23...14......-9.....5....-4...1.**....5..-1244...5..-4..1
Et donc 
x=D[-83*7*1244/23 +23*5*1244/17 +5*9/11]*23*17*11
Soit
x_=3713[4301]

NicoLeProf

Je ne sais pas quelle est ta question mais cela revient (en multipliant par les inverses modulaires de $3$ ; $8$ et $7$ modulo $23$ ; $17$ et $11$ respectivement) à résoudre :

$x \equiv 10 \pmod {23}$

$x \equiv 7 \pmod {17}$

$x \equiv 6 \pmod {11}$ .

On applique le théorème des restes chinois et on trouve : $x \equiv 10 \times 187 \times 8+7 \times 253 \times 8 + 6 \times 391 \times 2 \pmod {4301} $ .

On trouve bien : $x \equiv 3713 \pmod {4301}$ .

ouragh1951

Merci pour votre intervention. Néanmoins il est possible comme cela est montré dans cet exercice de passer outre de la transformation du système initial et de résoudre directement sur le tableau. Tous les calculs m'ont pris [moins de] 6 minutes.
Ainsi inutile de faire cette transformation en cherchant les trois inverses et après cela résoudre un nouveau système.
Bu 

NicoLeProf

Peux-tu expliquer ton raisonnement de manière explicite? Comment fais-tu sans chercher les trois inverses (conduisant à un nouveau système)?

ouragh1951

NicoLeProf a dit :

Peux-tu expliquer ton raisonnement de manière explicite? Comment fais-tu sans chercher les trois inverses (conduisant à un nouveau système)?

Pour   3x_=7[23] on aura à chercher l'inverse de 3 modulo23 et cela se fera comme suite
23......3......2.....1
.........-7.....-1
..........8.....-1......1
Et donc cet inverse est 8
Pour  8x_=5[17] on aura comme inverse de 8 modulo 17
17....8....1
.......-8.....
.......-8.....1
Et donc cette inverse est 17-8=9
Pour. 7x_=9[11] on aura pour inverse de 7 modulo 11
11.....7.....4......3.......1
........-1....-1.....-1
........-3.....2.....-1.......1
Et donc cet inverse est   11-3=8
Cordialement.

NicoLeProf

Je ne comprends pas où tu veux en venir :

-> déjà l'inverse de $8$ modulo $17$ n'est pas $9$ comme tu l'écris ci-dessus car $ 8 \times 9 \equiv 4 \pmod {17}$ . L'inverse de $8$ modulo $17$ est $15$ . Calculer des inverses ne me pose pas de problème.

-> Je constate que tu as besoin des inverses de $3$ ; $8$ et $7$ modulo $23$ ; $17$ et $11$ respectivement alors que tu disais avoir une méthode permettant de ne pas les calculer et de trouver directement la solution (ce qui m'intéresse là) ?

ouragh1951

Oui je le sais et comme tu peux me corriger donne moi l'erreur que tu as relevée.  Oui volontairement j'ai glissé cette erreur et voici comment trouver cet inverse 
18....8.......1
........-2.......
........-2......1
Et donc 17-2=15
Oui j'ai utilisé une autre méthode mais ta question précédente concerné les inverses et j'ai donné cela moyennant une petite erreur. Oui monsieur j'ai utilisé le schéma d'Ouragh qui est bien meilleur que l'algorithme d'Euclide étendu. Par conséquent je vous invite à relire mon premier commentaire et vous verrez que ces trois inverses je ne les ai pas calculés. 
Je vous invite à calculer l'inverse de 416 modulo 607 pour voir l'avantage de ce schéma.

ouragh1951

Pour l'inverse de 416 modulo 607 on aura
607
416.......-1.....….-232
191.......-2..........159
34.........-5...........-73
21.........-1............13
13.........-1............-8
8...........-1.............5
5...........-1............-3
3...........-1.............2
2...........-1............-1
1...........................1
Et donc cet inverse est 
607-232=375
Donc 375.

ouragh1951

Voici un autre exemple dont la solution je la donnerai demain (en effet il est un peu tard maintenant)
Résoudre dans Z le système
5x_=12[37]
8x_=9[31]
3x_=5[23]
7x_=2[19]
2x_=11[13]
Je reviendrai demain

Bonne nuit.

NicoLeProf

Non, ma question ne concernait pas les calculs d'inverses ! Ma question concernait la résolution du système que tu as donné au départ sans calculer les inverses de $3$ ; $8$ et $7$ modulo $23$ ; $17$ et $11$ .

Ta méthode avec des pointillés : $...$ n'est pas très explicite sur le plan pédagogique... 

ouragh1951

Les pointillés comme vous le signalez c'est tout juste pour éviter un '' mouvement '' désagréable des nombres les uns vers les autres et surtout à défaut pour moi de tracer un tableau à N colonnes et à trois lignes (ou verticalement un tableau à n lignes et trois colonnes). Certes sur le plan pédagogique cela n'est point complet et j'ai agi comme celui qui résout une méthode qui l'a maîtrise. Donc j'ai donné le résultat pour que chacun sache que résoudre ce type d'exercices il y a bien mieux que l'utilisation du théorème des restes chinois qui certes ce dernier précise surtout les conditions d'existence de solutions de tels exercices. Je vous laisse le soin de vérifier l'exactitude de ce que je viens dire et ce au vu de la solution de l'exercice à cinq équations que j'ai proposé dans mon dernier commentaire.

NicoLeProf

Je te remercie pour ta réponse. Je reformule simplement ma question : peux-tu expliquer la première ligne : $184..51...31...20.....11.....9.....2...1.**.2737..11....9...2...1$  de ton premier message. D'où sortent ces nombres? Que fais-tu?

Je t'en serais très reconnaissant : j'adore l'arithmétique et je veux juste apprendre des choses !

ouragh1951

Je reprends le système
3x_=7[23]
8x_=5[17]
7x_=9[11]
Je faisais départ
Le modulo 37 que je multiplie par le coefficient de x de la seconde équation c'est à dire 8 ce qui donne 8*23=184
Et je fais aussi le second modulo 17 que je multiplie par le premier coefficient de x c'est à dire 3 *17=51 et je pose
184....51
J'applique le Théorème d'Euclide 184=51*3+31
Donc on a ici comme quotient 3 et comme reste 21et qui l'on réécrire en forme de T comme suite
181...51....31
..........-3
Ou vous noterez que j'ai changé le signe du quotion qui devient -3 et non 3.
Je poursuis donc avec le même procédé qui traduit une autre forme d'écriture de l'algorithme d'Euclide lors de la recherche du PGCD de deux nombres ainsi vous reconnaîtrez que les deux premières lignes ne sont qu'une forme simplifiée de l'algorithme d'Euclide pour la recherche du PGCD de deux nombres. Ce calcul se termine pour 184 et 51 juste avant l'apparition des deux étoiles.
J'espère que j'ai été claire , sinon précisez votre question pour l'instant avant de poursuivre.

ouragh1951

...comme reste 31... ( et non 21 )

ouragh1951

NicoLeProf a dit :

Je te remercie pour ta réponse. Je reformule simplement ma question : peux-tu expliquer la première ligne : $184..51...31...20.....11.....9.....2...1.**.2737..11....9...2...1$  de ton premier message. D'où sortent ces nombres? Que fais-tu?

Je t'en serais très reconnaissant : j'adore l'arithmétique et je veux juste apprendre des choses !

Vous avez quitté cette discussion.  Alors j'attendrai.

bd2017

Bonjour

C'est complètement nébuleux, incompréhensible. On se demande même si l'auteur du sujet comprend le principe qu'il applique . 

En fait, la seule façon qui permet de  comprendre c'est qu'il a fini dire qu'il applique le principe d'OURAGH.

Sur internet, avec une vidéo, on voit qu'il s'agit simplement de  l'algorithme d'Euclide, disposé différemment. On peut parler d'un schéma. Je ne discute pas de l'efficacité.

De toute façon, je ne vois pas l'intérêt de parler d'une "méthode" sans être capable de l'expliquer correctement.    

ouragh1951

Je vous défi de le démontrer que j'en sois incapable de le faire. Votre seul problème c'est que c'est un africain qui ose donner de leçons à ceux qui croient que la science leur appartient à jamais. Massakines.

ouragh1951

Je n'ai pas parlé de ''principe '' mais de
'' schéma '' et je sais où du moins je le crois qu'il y a une différence. Si une personne me démontre l'existence d'un tel schéma avant 2011 , date à laquelle on y trouve des traces de ma propre main alors je retirerai mes affirmations. Si tel ou tel scientifiqie n'arrive pas à découvrir ma démarche alors que les résultats sont exacts alors le mal il est où.

bd2017

ouragh1951 a dit :

Je vous défi de le démontrer que j'en sois incapable de le faire. Votre seul problème c'est que c'est un africain qui ose donner de leçons à ceux qui croient que la science leur appartient à jamais. Massakines.

Tes propos sont  inacceptables.  Comment pouvais-je savoir si  tu es africain  ou autre ?  D'ailleurs cela ne m'intéresse pas  

Je donne mon  avis  sur un message de quelqu'un qui est anonyme.  Mon avis est ce qu'il est. Mais que la personne soit blanche, noire ou jaune, cela sera ne changera pas ma remarque.

Je réitère donc ma remarque : ton message est incompréhensible, nébuleux.  Quel le but de ton message ? Pourquoi veux tu parler d'un schéma que tu ne sais pas expliquer ? 

gerard0

Pour Nicoleprof et Bd2017, je signale que l'auteur de ce fil est déjà venu prétendre qu'il a trouvé des méthodes nouvelles (dont un algorithme OR prétentieusement nommé d'après ses initiales). Ce qui a été expliqué était élémentaire.

Cordialement. 

NB : à placer en shtam. 

NicoLeProf

ouragh1951 a dit :

Je vous défi de le démontrer que j'en sois incapable de le faire. Votre seul problème c'est que c'est un africain qui ose donner de leçons à ceux qui croient que la science leur appartient à jamais. Massakines.

Attention, du calme... C'est très limite comme message, nous n'avons rien insinué du tout : nous avons seulement dit que tu pourrais faire un effort d'explications sur le plan pédagogique !

J'ai compris la première ligne jusqu'à ** (juste l'algorithme d'Euclide : rien d'exceptionnel).

Peux-tu continuer tes efforts d'explications en me fournissant une explication claire de la suite à savoir : $2737..11....9...2...1$ (d'où sort le $2737$?) et $.........-3....-1....-1......-1....-1....-4....0.**..0....-248...-1..-4..0$ ? (D'où sort le $-3$ ?)

Il n'y a aucune attaque de notre part ni aucune insinuation rassure-toi : nous sommes sur un forum de maths : nous discutons de maths entre gens anonymes, point et quand on peut apprendre des choses, c'est super ! 

lourrran

Ceci me rappelle un sketch de Coluche ... il racontait qu'il insultait tel ou tel chauffeur de taxi, et ensuite, il disait 'Je suis de tel parti', juste pour ternir l'image de ce parti.

JLapin

Bien vu

Fort heureusement, cet abruti ne saurait à lui tout seul discréditer un continent entier !

ouragh1951

Va prendre une carotte , c'est le meilleur conseil que te donne un algérien. Il faut être vraiment un abruti pour y réfléchir comme cela. Incapable de déchiffrer un tableau de quelques lignes qu'un gosse de 13 ans y arriverez et qui se croient plus matheux qu'autrui. Rester dans votre ignorance sur le sujet et je sais que tous abrutis s'en fous. Continuer à dénigrer ce que vous êtes incapables d'expliquer. Abrutis Massakines. En attendant faites un tour chez Amazone ou chez OPU pour essuyez vos larmes.

JLapin

T'es complètement frappé du bulbe. Je t'ai demandé des explications sur la décomposition en éléments simples et tu n'as rien expliqué du tout.

Mais c'est très réjouissant de te lire en tout cas ! Mine de rien, tu sembles savoir faire un peu de maths et tes insultes sont plutôt originales.

Vive l'Algérie Massakines !

Vassillia

Bonjour,

Non, ce n'est pas vraiment réjouissant de voir des gens s'insulter.

Puisque ouragh1951 pense avoir trouvé une méthode miraculeuse, une petite délocalisation dans shtam me parait pertinente voire une fermeture du fil qui me parait difficilement sauvable à ce stade, non ?

NicoLeProf

Mais what??? Je ne t'ai pas agressé ouragh, je te demande seulement des explications sur ta méthode?!

Je suis atterré par l'agressivité de tes remarques dans tes commentaires qui est totalement contraire à l'esprit bienveillant de ce forum et à la charte...

Ainsi, je signale tes commentaires à la modération en espérant, a minima, un ban temporaire qui te permettra de te calmer et de te remettre en question.

Cordialement.

Rescassol

Bonjour,

Que signifie "Massakines" ? Qu'est ce que OPU ?
A part ça, il n'y a pas de mathématiques dans ce fil.

Cordialement,
Rescassol

bd2017

OPU  Ordonnance de Protection d'Urgence.

Edit:  Chercher le rapport avec Amazone!

ouragh1951

Ce n'est pas moi qui a cité ' le mot abruti' et je ne fais que repondres à certains abrutis. Avant cela je n'ai fait que dire que ma méthode est bien meilleure que celle qu'ils pourront exhibée. Pour les explications j'étais près de donner certaines explications dont les grandes lignes je les donné dans deux publications de plus de 150 pages. D'ailleurs ils croient que la personne qui est devant eux est un enfant gâté et il ne sait pas ce qu'il dit. Sachez messieurs que j'ai plus de soixantes dix ans et qui retraité depuis plus de deux ans . De plus je suis l'auteur de plusieurs manuels universitaires. Tapez sur le net ' Ouragh youssef'' et vous aurez une réponse sur ma personne. En attendant je dis aux uns et autres les décompositions en éléments simples des fractions rationnelles de types par exemple 
A(x)=(x-1)/{x⁵(x²-x+1)²} 
Peuvent se faire facilement au moyens de la méthode d'OR en un temps très court ( 3 ou au plus 4 minutes) et de plus le format sera très réduit. 
De même la résolution des systèmes modulaires (linéaires ) se font très simplement par le schéma d'Ouragh et les difficultés que l'on rencontre en appliquant l'algorithme d'Euclide étendu sont pratiquement réduits à zéros. Je sais que la majorité des oreilles se marrent maintenant mais cela ne leur est pas destiné car je sais que d'honnêtes personnes sont présentes sur le présent site et je leur présente toutes mes excuses et leurs dis revoir tous les commentaires dans leur apparition et il verront que je ne fait que répondre à certaines imbicilités que certains ont écrits.
Que ces dernières personnes me pardonnent de me retirer et je pourrai peut être révenir si certains yate rabaou.

Vassillia

OPU = Office des Publications Universitaires https://fr.wikipedia.org/wiki/Office_des_publications_universitaires

Miskine au singulier et masakin au pluriel sont des mots venant de l'arable pour signifier le(s) pauvre(s), c'est souvent utilisé pour montrer sa pitié envers son interlocuteur.

Désolée ouragh1951 mais c'était à toi de présenter ta méthode de sorte à intéresser les lecteurs et à faire preuve de pédagogie de manière à ce qu'ils la comprennent à supposer qu'elle soit aussi performante que tu le prétends. Dire "ma méthode est bien meilleure" sans avoir fait cette étape initiale n'est pas un comportement de scientifique. En ce qui me concerne, tu es tout pardonné pour ton retrait et je te souhaite une bonne continuation ailleurs.

Heuristique

Bonjour,

Il y a 2 manières simples de prouver que ta méthode est meilleure que celle via l'algorithme d'Euclide.

L'algorithme d'Euclide est polynomial, disons quadratique pour faire simple (approximation où je ne tiens pas compte du logarithme dans la transformée de Fourier rapide). Quelle est la complexité théorique de ton algorithme ? Si tu prouves une complexité linéaire ou quasi-linéaire, cela serait une bonne preuve de la supériorité de ton algorithme.

Si tu n'aimes pas la complexité, tu peux toujours programmer ton principe et vérifier que tu vas plus vite que la méthode usuelle pour résoudre des systèmes. Si ton algorithme est simple, cela ne devrait pas te poser de problème. Coder Euclide non plus d'ailleurs. Notons toutefois qu'un programme n'est pas une preuve, sauf s'il a été lui-même prouvé.

Julia Paule

En somme, Ouragh a lancé ce fil pour se faire de la publicité (pour ses livres !). C'est sûr qu'il ne va pas dévoiler sa méthode !

Son algorithme est un peu mieux expliqué ici : https://www.bibmath.net/forums/viewtopic.php?id=9790

Cela utilise l'algorithme d'Euclide étendu en omettant les termes inutiles (il fait les divisions euclidiennes puis il les remonte classiquement en ne mettant que les termes strictement utiles, je n'ai pas approfondi).

En effet, je présume qu'il fait, d'abord sur 2 équations puis avec la 3ème équation, sans calculer les inverses au départ, il en calcule un seul à la fin, pour le système d'équations :

$ax \equiv b \pmod n$

$cx \equiv d \pmod m$

se résout pour $m$ et $n$ premiers entre eux en multipliant la 1ère équation par $m$ et la 2ème par $n$ : $(ma+nc)x \equiv (mb+nd) \pmod {mn}$,

et on cherche l'inverse de $ma+nc$ modulo $mn$, pour obtenir $x$ selon ce modulo.

Je n'ai pas vérifié, mais si c'est ça, rien que du très classique.

EDIT : je fais avec les 2 premières :

$3x \equiv 7 \pmod {23}$

$8x \equiv 5 \pmod {17}$.

Cela donne $(3*17+8*23)x \equiv 7*17+5*23 \pmod {23}$.

Dans sa 1ère ligne, il cherche les coefficients de Bézout de $184=23*8$ et de $51=3*17$, il obtient : $-23*184+83*51=1$, qu'il applique selon $x$ aux 2 équations et il obtient $x$ modulo $23*17$ qu'il met dans la 3ème équation.

Je n'ai pas le courage (ni le temps) de continuer.

raoul.S

Depuis 2011...

Julia Paule

Bref, tout a déjà été dit, on perd notre temps, et on entretient le fil pour sa publicité. Je m'en doutais. 
Ce que je trouve bizarre surtout, c'est que ses livres, aussi pauvres en contenu, aient été publiés.

raoul.S

Julia Paule a dit : 

Ce que je trouve bizarre surtout, c'est que ses livres, aussi pauvres en contenu, aient été publiés.

Son livre a été publié par les Éditions Universitaires Européennes et est disponible sur Amazon.
Voici quelques mises en gardes contre ces éditeurs : 
- https://www.bibl.ulaval.ca/services/redaction-et-citation/redaction-de-memoires-et-de-theses/mise-en-garde-editions-universitaires-europeennes-et-presses-academiques-francophones
- https://www.unige.ch/biblio/fr/openaccess/publier/eviter-editeurs-predateurs/#:~:text=Entre les éditeurs,aucun travail éditorial.

Julia Paule

Merci beaucoup @raoul.S, je n'avais pas vu. Il vaut mieux être prévenu avant, quand on s'apprête à acheter ce genre de livres !

Mais cela reste incompréhensible, vu le nombre de fautes d'orthographe et de français commises par l'auteur dans ce fil, et aussi le fait qu'il a pu tenir 72 pages sur cette seule idée.

raoul.S

Oui, je cite un passage : Les deux éditeurs académiques cités en titre offrent un service d'édition minimal, sans accompagnement ni révision par les pairs, et laissent à l'auteur la responsabilité de mettre en page leur manuscrit.

Voilà, je n'ose imaginer les dégâts...