Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 21-09-2017 14:34:49

hgaruo1951
Membre
Inscription : 13-09-2017
Messages : 104

congruences

Bonjour ,

  Comment déterminer l'inverse de 1595 modulo 2584 ?

Cordialement.

Hors ligne

#2 21-09-2017 15:23:16

tibo
Membre expert
Inscription : 23-01-2008
Messages : 1 097

Re : congruences

Bonjour,

Je te donne la méthode générale (de mémoire mais ça fait longtemps que je n'ai pas fait d'arithmétiques).

Chercher l'inverse de $a$ modulo $n$ revient à résoudre l'équation $au+nv=1$.
$u$ sera l'inverse de $a$ modulo $n$.

Dernière modification par tibo (21-09-2017 18:12:39)


A quoi sert une hyperbole?
----- A boire de l'hypersoupe pardi !

Hors ligne

#3 21-09-2017 17:02:49

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 7 457

Re : congruences

Salut,

précision ci dessous

tibo a écrit :

Bonjour,

...]
Chercher l'inverse de $a$ modulo $n$ revient à résoudre l'équation $1595\times u+2584\times v=1$.
$u$ sera l'inverse de $1595$ modulo $2584$.

à la condition que 1595 et 2584 soient premier entre eux (à vérifier) !
Passe par l'algorithme d'Euclide.


De la considération des obstacles vient l’échec, des moyens, la réussite.

Hors ligne

#4 21-09-2017 17:11:21

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 909

Re : congruences

Bonjour,


#!/usr/bin/env python
# -*- coding: cp1252 -*-

from fractions import gcd

a,modulo=1595,2584
pgcd=gcd(max(a,modulo), min(a,modulo))
 
if pgcd != 1:
    print ("Désolé, votre nombre et le modulo ne sont pas premiers entre eux.")
    print ("Sélectionner un autre couple de valeurs.")
else:
    k=modulo//a+1
    mo=1
    while mo != 0:
        k += 1
        mo = (1 + modulo * k) % a
    print ("L'inverse de",a,"modulo",modulo,"est :",((1+modulo*k)//a)%modulo)
 

Sortie

========= RESTART: C:/Python35/Progs persos/v3.x/Inverse_modulaire.py =========
L'inverse de 1595 modulo 2584 est : 2051
>>>

@+


Arx Tarpeia Capitoli proxima...

En ligne

#5 21-09-2017 18:29:58

hgaruo1951
Membre
Inscription : 13-09-2017
Messages : 104

Re : congruences

Salut tout le monde ,

D'abord merci pour les réponse , mais si l'on doit effectuer les calculs à la main
chacun reconnait que ces calculs sont en général ennuyeux et tout élève de terminale
doit faire attention aux étourderies que ces calculs sont souvent à l'origine . Par conséquent
est ce que vous ne pensez pas qu'il serait préférable d'utiliser le schéma d'OURAGH pour
résoudre ce type de problème?

Cordialement.

Hors ligne

#6 22-09-2017 14:40:17

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 7 457

Re : congruences

Salut,

à la main, voilà ce que ça donne.

$989 = 2584 - 1595$

$606=1595-989 =-2584 + 2\times 1595$

$383=989-606=2584-1595-(-2584 + 2\times 1595)=2\times 2584-3\times 1595$

$223=606-383=2\times 1595-2584 - (2\times 2584-3\times 1595)=-3\times 2584+5\times 1595$

$160=383-223 = 2\times 2584-3\times 1595 -(-3\times 2584+5\times 1595)=5\times 2584 - 8\times 1595$

$63=223-160 =-3\times 2584+5\times 1595 -(5\times 2584 - 8\times 1595) = -8\times 2584 +13\times 1595$

$34=160-2\times 63 = 5\times 2584 - 8\times 1595 - 2\times (-8\times 2584 +13\times 1595)=21\times 2584 - 34\times 1595$

$29=63-34 = -8\times 2584 +13\times 1595-(21\times 2584 - 34\times 1595) = -29\times 2584 + 47\times 1595$

$5 = 34-29 = 21\times 2584 - 34\times 1595 - (-29\times 2584 + 47\times 1595) = 50\times 2584 - 81\times 1595 $

$4=29-5\times 5 = -29\times 2584 + 47\times 1595 - 5\times (50\times 2584 - 81\times 1595 )= -279\times 2584  +452\times 1595 $

$1 = 5-4 = 50\times 2584 - 81\times 1595  -(-279\times 2584  +452\times 1595 ) = 329\times 2584 - 533\times 1585$

et bien évidemment  $- 533 = 2051$ dans $Z_{2584}$


De la considération des obstacles vient l’échec, des moyens, la réussite.

Hors ligne

#7 23-09-2017 14:10:25

hgaruo1951
Membre
Inscription : 13-09-2017
Messages : 104

Re : congruences

Bonjour Freddy ,

Je tiens à vous dire que je n'ai aucun doute qu'en à vos connaissances en mathématiques
que je trouve (chaque fois que je vous lis!) excellentes . Ceci étant dit pour le présent problème
je tiens à dire que le schéma d'OURAGH qui est certes un moyen qui synthétise la
méthode d'EUCLIDE étendu . En effet je vous laisse voir par vous même l'utilisation de ce schéma
pour l'exercice de ce cette fenêtre :

2584.......1595......989......606.....383.......223.......160......63......34......29.......5.......4.......1
................-1.......-1........-1........-1.......-1..........-1.......-2......-1.......-1.....-5......-1..........
..............-533......339.....-204.....125......-79.........46.....-33......13......-7.......6......-1......1

et  l'on relève de ce tableau inverse 1595 mod 2584 = -533 mod 2584 = 2051  .

Effectivement que l'on reconnait plusieurs nombres qui apparaissent en utilisant directement l'algorithme
d'EUCLIDE étendu , mais vous constatez que ni les parenthèses ne sont utiles , ni beaucoup de nombres
(par exemple les (2,383,223,8,-29,47,81 pour ne citer que ceux là !!) n'apparaissent pas en utilisant le
SCHEMA D'OURAGH . On me dira certainement qu'il n'y a pas grande différence et pourtant on aura tord
et pour preuve que l'on résout le système
      12x=52 mod83    ;   8x=25 mod 61  ;  11 x =3 mod 29   ; 5x = 2 mod 13   ( le signe "=" se lit " est
congru à " )

au moyen de l'algorithme d'EUCLIDE si cela est possible et surtout facile à résoudre. Par contre au moyen
du schéma d'OURAGH cela  se fera sur un tableau pratiquement de la même taille que le précédent et ce en
4 à 5  minutes .

Si les  "techniques" étaient exactement les mêmes ils devraient avoir  à peu près le même format et devraient
prendre le même temps pour résoudre le dernier système. J'affirme que cela il n'en est rien!!!!!

Cordialment.

Dernière modification par hgaruo1951 (23-09-2017 14:22:53)

Hors ligne

#8 23-09-2017 15:45:42

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 909

Re : congruences

Bonjour,

J'ai déplacé la discussion, elle n'avait rien à faire dans un forum d'entraide...
Ta formulation était biaisée et au vu des différents forums où tu as "sévi", j'ajoute : volontairement...
Je n'apprécie pas le procédé.
Et je pense que freddy te remerciera pour le magistral cours que tu lui a et nous a fait...
Je précise que je ne serai pas aussi patient qu'ailleurs si ce flux part en flood...
Au fait info pour info (cf ton mn sur futura-sciences et ailleurs) :

Le symbole de la minute est min, depuis 1975.
Le symbole mn n'a été d'usage officiel qu'entre 1948 et cette date.
Décret n° 75-1200 du 23 déc. 1975 relatif aux unités de mesure et au contrôle des instruments de mesure.

Source : http://sgalex.free.fr/typo-maths_fr.pdf
1975 !!! Ça ne date pas d'aujourd'hui...
Je précise que c'est un point qui m'agace tout particulièrement...
Par ex, dès que je passe devant une agence immobilière, j'entre et leur fais la remarque ^_^

Donc pour éclairer tout le monde et pour t'éviter de te répéter :
http://forums.futura-sciences.com/mathe … uragh.html
http://www.les-mathematiques.net/phorum … 801,654014
https://www.maths-forum.com/lycee/equat … 58832.html
http://forum.prepas.org/viewtopic.php?f=3&t=28417

      Yoshi
- Modérateur -


Arx Tarpeia Capitoli proxima...

En ligne

#9 23-09-2017 21:31:21

hgaruo1951
Membre
Inscription : 13-09-2017
Messages : 104

Re : congruences

Bonjour ,
Merci pour tous les liens que vous rapportez et si je peut me permettre j'ajouterai les suivants et
j'espère y arriver :

a) cliquez ici ,
b) cliquer ici
c) cliquer ici

Hors ligne

#10 25-09-2017 09:47:54

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 909

Re : congruences

Bonjour,

Ici, on peut discuter de ton procédé
inverse de [tex]143 \mod 7 \equiv 5[/tex] ?
[tex]143x+7y=1[/tex]
J'emploie ton schéma :
143 ...  7  ...   3  ...  1
        -20  ... - 2
         41       -2       1
Sur la 3e ligne où est le 5 ? Qu'est-ce qui est incorrect ?
Je le trouve comme ça
143(-2)+7(41)=1
Ensemble des solutions
[tex]x=7k-2\\
y =-143k+41[/tex]
Je cherche k [tex](\in\, \mathbb{Z}[/tex]) pour avoir x<7
7k-2<7
7k<9
k<9/7 d'où k = 1
x=7-2=5

Autre essai
inverse de [tex]77 \mod 13 \equiv 12[/tex] ?
[tex]77x+13y=1[/tex]
77 .. 13 ... 12 ... 1
        -5      -1
         6       -1       1
Sur la 3e ligne où est le 12 ?
[tex]x=13k-1\\
y=-77k+6[/tex]
13k-1<13
d'où k=1
et x=12

C'est comme ça que tu fais ?

@+


Arx Tarpeia Capitoli proxima...

En ligne

#11 25-09-2017 11:30:53

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 7 457

Re : congruences

Salut,

c'était donc de l'autopromotion, cachée derrière de fausses naïves demandes d'aide et un peu de flatterie au passage.
C'est fatiguant !

Dernière modification par freddy (25-09-2017 15:27:08)


De la considération des obstacles vient l’échec, des moyens, la réussite.

Hors ligne

#12 25-09-2017 11:52:40

hgaruo1951
Membre
Inscription : 13-09-2017
Messages : 104

Re : congruences

Bonjour ,

Non ce n'est pas comme cela  que doit être exécuté le schéma . Alors puisque vous posez
le problème je vous laisse chercher d'abord votre erreur et je vous corrigerai par la suite
(ceci dit je suis persuadé que vous aller trouver l'erreur!!!!!!!!!

Cordialement.

Hors ligne

#13 25-09-2017 11:58:30

hgaruo1951
Membre
Inscription : 13-09-2017
Messages : 104

Re : congruences

Re ,

Pour ne pas vous perdre dans tels ou tels considérations je vous affirme que les tableaux
que vous avez obtenus sont corrects et la solution est même évidente !!!!!!!

Cordialement;

Hors ligne

#14 25-09-2017 12:04:11

hgaruo1951
Membre
Inscription : 13-09-2017
Messages : 104

Re : congruences

Re,

     "  fausses naïves demandes d'aide et un peu de flatterie au passage. "


Et si j'ai raison de tels propos venant d'un maître sont vraiment regrettables ;

Hors ligne

#15 25-09-2017 13:52:30

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 909

Re : congruences

Bonjour,

Pour ne pas vous perdre dans tels ou tels considérations je vous affirme que les tableaux
que vous avez obtenus sont corrects et la solution est même évidente !!!!!!!

1.  J'aimerais que tu justifies  la raison théorique pour laquelle tu multiplies tous les quotients de la ne ligne par -1,
2.  J'aimerais que tu justifies  la raison théorique pour laquelle tu multiplies ensuite chaque nombre de la 3e ligne par le quotient de la 2e ligne qui le précède en diagonale et que tu ajoutes le résultat précédent de la 3e ligne...
     Autre essai avec 91x+11y = 1
91 ... 11 ... 3 ...  2 ... 1
        -8 ... -3 ... -1
       -33 ...  4 ... -1 ... 1 ...  0
x= 11k +4
y=-91k-33

11-4 =7
13-1=12
7-2 = 5...
3. Alors, quelle évidence ?
Je ne te demande pas de jouer aux devinettes ni de l'aide, je cherche à comprendre ta méthode : ce qui prouve que tes videos sont à revoir...
Concernant les calculs ci-dessus, il faudrait que je fasse d'autres tests  pour vérifier qu'ils ont un sens.
Ou tu as le désir d'expliquer ta méthode ou tu préfères prêcher ex cathedra...
A toi de voir...
Ça ne m'empêchera pas de dormir
D'ores et déjà, sans aller plus loin, ils ne me plaisent pas : parce que je fais abstraction du signe du 2e nombre sans pouvoir le justifier.

Vois-tu, lorsque j'étais élève de 4e (il y a un temps certain déjà), on m'a appris à extraire une racine carrée avec crayon et papier, sans justifier le procédé (ou alors j'ai oublié !)...
J'ai informatisé ce procédé (il y a bien d'autres méthodes) mais je m'en attribue pas la paternité...

freddy a écrit :

Fausses naïves demandes d'aide

Oty1951 alias hgaruo1951, tu t'insurges ?
Alors, questions :
* La présente discussion, avant d'être déplacée, n'était-elle pas dans le sous-Forum Entraide Collège/Lycée ?
   Oui ou Non ?
* Dans un forum d'Entraide, ne nient-on pas demander de l'aide ?
   Oui ou Non ?
* Quand j'y lis :  Comment déterminer l'inverse de 1595 modulo 2584 ? ne suis-je donc pas fondé à y voir une demande d'aide ?
   Oui ou Non ?
* Quand tu lis nos réponses à tibo, freddy et moi, ne vois-tu pas que c'est ainsi que nous avons interprété ta question ?
   Oui ou Non ?
* Quand on lit ta réponse : Par conséquent est ce que vous ne pensez pas qu'il serait préférable d'utiliser le schéma d'OURAGH pour résoudre ce type de problème?, on ne s'aperçoit pas encore de notre erreur d'interprétation. Pourquoi ?
   Poser une question, c'est y répondre : parce que aucun de nous trois avait déjà entendu de ce fameux schéma..
   Oui ou Non ?
* Tu t'attendais à quoi ? Qu'on connaisse le célébrissime schéma d'Ouragh ? Tu ne peux pas être naïf à ce point... Bien sûr que non...
   Conclusion, la façon d'ouvrir la discussion était un procédé te permettant de pouvoir dire après : vous êtes très forts, mais moi, je fais mieux que vous avec le schéma d'Ouragh, sans dire qu'il se trouve qu'Ouragh... c'est toi !!!
    Comment qualifier ce genre de procédé ?
* Je n'ai découvert la fausse demande d'aide et l'erreur d'interprétation qu'en allant fouiller sur Internet... Voilà pourquoi j'ai parlé de présentation volontairement biaisée. Peux-tu comprendre alors que nous ne soyons pas contents ?
* Pourquoi freddy a-t-il ajouté  c'est fatigant ?... Parce que tu n'es pas le premier génie méconnu, candidat à la médaille Fields, à hanter ce forum, après ne plus pouvoir s'exprimer sur les autres...
Le fais-tu exprès d'essayer de t'aliéner le capital sympathie dont tu bénéficies en arrivant sur un foirum ?
Non ? Dommage, c'est pourtant ce qui arrive.  Change de discours et joue cartes sur tables...

Quant à tes citations moralisatrices, tu peux les remettre dans ta poche...
Nous sommes ici sur un forum de Mathématiques officielles, utilisant les mathématiques officielles celles qui sont enseignées, et nous n'avons pas en sortir dans le cadre de l'Entraide, c'est peut-être regrettable mais c'est comme ça...
Je ne suis n'était qu'un exécutant, je n'étais pas payé pour enseigner des méthodes exotiques (même si j'en ai), et encore moins en les baptisant de mon nom de famlile, ce qui aurait fait que j'aurais parlé de moi à la 3e personne : quelle manifestation de fatuité cela aurait été....
Comprends-tu ?

freddy a écrit :

et un peu de flatterie au passage.

Je lis pourtant  comme freddy :

Je tiens à vous dire que je n'ai aucun doute qu'en à vos connaissances en mathématiques
que je trouve (chaque fois que je vous lis!) excellentes

Cette procédure stylistique a été employée dans les autres forums aussi et toujours suivies de : MAIS...
Si tu ne peux pas te satisfaire de dette explication de texte, tu peux aller voir ailleurs si l'herbe y est plus verte : nous te retenons pas.

Ma suggestion de t'adresser à Cédric Villani était sans arrière pensée..

@+ peut-être


Arx Tarpeia Capitoli proxima...

En ligne

#16 25-09-2017 16:56:01

hgaruo1951
Membre
Inscription : 13-09-2017
Messages : 104

Re : congruences

Re,

Tout d'abord j'espère que le présent texte apparaîtra et que vous ne lui ferrez pas subir
la même suppression que celui que j'ai précédemment envoyé et qui avait suivi votre suggestion.
Mes citations peuvent servir autrui je le pense et je suis certain. Ceci dit j'affirme aux uns et aux autres
que je peux justifier tout ce que j'ai écrit sur le sujet. Oui vous avez parfaitement raison le schéma que
j'utilise porte mon nom comme , d'ailleurs ,  vous l'avez certainement remarquer mon pseudo sur ce site.
Je le nie pas.
Quand aux

"tu peux les remettre dans ta poche.."  ,   "tu peux aller voir ailleurs si l'herbe y est plus verte"

Je préfère suivre (oui encore une citation! ) le proverbe qui dit
" C'est mal avec le mal mais c'est pire sans mal".

Ah j'allais oublié pour le dernier exercice que vous n'avez pas résolu comme il se doit
je vous donne  ( à vous et surtout aux "forumeurs" ) la solution :

.....91.........11.......3......2........1
......0..........-8.....-3.....-1..........
......4.........-33......4.....-1.......1

et donc l'inverse de 91 mod 11=4   (et donc non pas 7.)
Si au lieu d'un nombre positif sous le "91" on avait obtenu un nombre négatif h
il suffit de faire 11+(h) pour avoir l'inverse.

Si votre question , au départ était
" J'aimerais que tu justifies  la raison théorique pour laquelle tu multiplies ensuite chaque nombre de la 3e ligne par le quotient de la 2e ligne qui le précède en diagonale et que tu ajoutes le résultat précédent de la 3e ligne..."

je vous assure que j'aurai répondu positivement sans aucune hésitation et je ne pouvais pas me lancer dans cette
voie ne sachant pas que si dans le site on connaissais cela ou non . Bon je vous est lu et je vais voir ailleurs
là ou les mathématiques peuvent pousser sans problèmes ou il n'y aurai aucune herbe .

Cordialement.

Hors ligne

#17 25-09-2017 17:00:48

hgaruo1951
Membre
Inscription : 13-09-2017
Messages : 104

Re : congruences

RE ,

Pour indication seulement (et qui n'a aucun lien avec le sujet) le nom d'OURAGH est celui avec lequel
Saint Augustin est né.

Cordielemnt.

Hors ligne

#18 25-09-2017 18:11:27

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 909

Re : congruences

Re,

Bon je vous est lu et je vais voir ailleurs là ou les mathématiques peuvent pousser sans problèmes ou il n'y aurai aucune herbe .

Bonne chance et tu en auras besoin vu le nombre de sites que tu as visités et où ça a mal fini !
Encore une fois comme ailleurs, tu t'es bien gardé de justifier pas à pas tes calculs (pour les deux premières lignes c'était évidemment inutile)
Tu as besoin de reconnaissance, il me semble : sur un forum d'entraide, c'est très difficile, parce qu'on ne peut pas (on ne doit pas : obligation morale) aider les demandeurs avec des méthodes "exotiques" : tu ne peux pas te mettre ça dans la tête ?
Je te réitère ma suggestion te t'adresser au célèbre mathématicien français Cédric Villani.
Même si maintenant, il a un engagement politique, il aura bien une petite place pour jeter un œil sur le schéma dont tu dis qu'il est tien et novateur ce qui n'est pas l'avis de beaucoup sur les autres forums.
S'il est vraiment original et qu'il mérite d'être diffusé, lui te le dira...
Le feras-tu ou pas, cela te regarde !

Le problème n'est ni l'herbe (elle un rôle à jouer), ni les mathématiques, mais celui des individus qui se voient plus beaux qu'ils ne sont...

Alors moi aussi, je terminerai par deux citations :
1. Mon père me disait : on ne peut pas faire boire un âne qui n'a pas soif !
2. La sagesse populaire dit : il n'est pire sourd que celui qui ne veut pas entendre ...

Puisses-tu obtenir la reconnaissance de ton schéma dont j'admets sans problème qu'il fonctionne... sur les exemples testés.
J'ai deux méthodes de calcul de l'inverse de a modulo b (elles ne sont pas de moi) : toutes deux font un nombre de calculs assez conséquents...
Je vais informatiser le schéma que tu as présenté : ça devrait aller "beaucoup plus vite" (1/100e de seconde au lieu de 1/10e ?).

@+

[Edit] Je suis allé lire les biographies de Saint Augustin disponibles sur le web : j'ignorais...


Arx Tarpeia Capitoli proxima...

En ligne

#19 27-09-2017 09:41:27

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 7 457

Re : congruences

Salut,

je viens de voir la première vidéo, c'est exactement le genre de pédagogie à quat 'sous que j'exécrais quand j'étais petit : faites comme je dis, ne cherchez surtout pas à comprendre comment je fais. Tout cela du haut d'une science supposée et non démontrée.
Je répète : fatiguant.


De la considération des obstacles vient l’échec, des moyens, la réussite.

Hors ligne

#20 27-09-2017 11:51:58

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 909

Re : congruences

Re,

Notre ami Ouragh est parti trop vite : j'aurais eu maintenant des tas de questions à lui poser.
Il aurait pu dire : << ok, vous avez raison, même s'il est plus simple et plus rapide, mon schéma  ne fait pas partie des méthodes officielles et inciter des élèves à l'utiliser serait les mettre en difficulté par rapport aux programmes officiels. >>
On aurait alors continuer à débattre dans le cadre de ce Café mathématique.
Il a préféré partir...

En tentant de programmer son tableau, j'ai pu me rendre compte de ce que :
Chercher l'inverse de 143 modulo 7 ou l'inverse de 7 modulo 143 donnait lieu au même tableau :
143 ... 7 ...  3 ...1
0     -20 ...-2
         41   -2     1
Question posée : je ne trouve pas le 5. qui est l'inverse cherché ?
Il avait répondu pour :
91 ... 11 ... 3 ...  2 ... 1
  0      -8 ...-3 ... -1
        -33     4     -1 ... 1
que c'était "évident" : -33*0 + 4 = 4...

Si j'applique la même méthode à 143, j'obtiens -2 soit 5. C'est juste...

Mais dans le cas de son tableau :
2584.......1595......989......606.....383.......223.......160......63......34......29.......5.......4.......1
................-1.......-1........-1........-1.......-1..........-1.......-2......-1.......-1.....-5......-1..........
..............-533.....339.....-204.....125....-79.........46.....-33......13......-7.......6......-1......1
je remarque que 339 est faux, c'est 329...
Ensuite -533*0+329 = 329 n'est pas le bon résultat, puisque c'est 2501...
Et si on cherche l'inverse de 7 modulo 143 ? Là c'est bien 41.
Hmmmm... Alors j'ai vérifié pour l'inverse de 2584 modulo 1595 : c'est effectivement 329.
Pas si "évident" que cela quand même...

Il y a donc deux réponses différentes selon selon que le nombre dont on cherche l'inverse est supérieur ou inférieur au modulo...
Pourquoi donc ? Où est la justification théorique ?

Mon script :

#!/usr/bin/env python
# -*- coding: UTF-8 -*-

def affiche_schema(lg,Liste):
    for nb in Liste:
        print(" "*(lg-len(str(nb))),nb,end="")
    print()

def calcul_inverse(x,modulo):
    a,b,r=max(x,modulo),min(x,modulo),0
    Dividendes_diviseurs_restes,Opp_Quotients,Fin=[a,b],[0],[0]
    while r!=1:
        a,q,r=b,a//b,a%b
        b=r
        Dividendes_diviseurs_restes.append(r)
        Opp_Quotients.append(-q)

    c,n=0,len(Dividendes_diviseurs_restes)
    Fin=[0 for ii in range(n+1)]
    Fin[-2]=1
    for ii in range(n-1,1,-1):
        Fin[ii-1]=Fin[ii]*(Opp_Quotients[i-1])+c
        c=Fin[ii]
    if x<modulo:
        inv_mod = Fin[1]
    else:
        inv_mod=Fin[2]
    if inv_mod<0:
        inv_mod=inv_mod%modulo
       
    lg=max(len(str(x)),len(str(modulo)))
    affiche_schema(lg,Dividendes_diviseurs_restes)
    affiche_schema(lg,Opp_Quotients)
    affiche_schema(lg,Fin)      
    return inv_mod

print("     *************************************************")
print("     *  Calcul de l'inverse d'un nombre x modulo n   *")
print("     *  avec le schéma présenté par Youssef Ouragh   *")
print("     *************************************************\n\n")      
       
x,modulo=1595,2584
print ("\nL'inverse de",x,"modulo",modulo,"est :",calcul_inverse(x,modulo))

Sortie :


     *************************************************
     *  Calcul de l'inverse d'un nombre x modulo n   *
     *  avec le schéma présenté par Youssef Ouragh   *
     *************************************************


 2584 1595  989  606  383  223  160   63   34   29    5    4    1
    0   -1   -1   -1   -1   -1   -1   -2   -1   -1   -5   -1
    0 -533  329 -204  125  -79   46  -33   13   -7    6   -1    1    0

L'inverse de 1595 modulo 2584 est : 2051

ou encore


 2584 1595  989  606  383  223  160   63   34   29    5    4    1
    0   -1   -1   -1   -1   -1   -1   -2   -1   -1   -5   -1
    0 -533  329 -204  125  -79   46  -33   13   -7    6   -1    1    0

L'inverse de 2584 modulo 1595 est : 329

Si par hasard, quelqu'un trouvait une erreur, merci de la signaler.

@+


Arx Tarpeia Capitoli proxima...

En ligne

#21 27-09-2017 12:36:59

hgaruo1951
Membre
Inscription : 13-09-2017
Messages : 104

Re : congruences

Bonjour ,

Vous m'obligez donc à vous répondre : non monsieur vous commettez encore
une erreur il suffit de faire  2584+(-533) et vous avez le résultat . je vous laisse
approfondir la question pour ne plus faire de telles erreurs. Quant à la programmation
de mon schéma je prie de me croire que j'ai une programme que vous pouvez le
vérifier ici.

Cordialement.

N.B:  même si vous dites " notre ami " de façon il est (presque!!) claire  ironiquement
c'est tout de même beaucoup mieux que certains de vos interventions précédentes.

Dernière modification par hgaruo1951 (27-09-2017 12:41:00)

Hors ligne

#22 27-09-2017 12:38:10

hgaruo1951
Membre
Inscription : 13-09-2017
Messages : 104

Re : congruences

Re ,

tout le monde à compris que je voulais écrire 2584

cliquer ici

Cordialement.

Dernière modification par hgaruo1951 (27-09-2017 12:42:50)

Hors ligne

#23 27-09-2017 14:26:15

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 909

Re : congruences

Re,

même vous si vous dites " notre ami " de façon il est (presque!!) claire  ironiquement
c'est tout de même que certains de vos interventions précédentes.

Pas du tout, c'est une formulation courante.
Je ne me suis jamais permis de manquer de respect à qui que ce soit.
J'ai suivi ton lien ci-dessus : il m'envoie vers la page http://www.bibmath.net/forums/help.php#bbcode
Je ne vois pas ton programme.
J'ai quand même dû modifier le mien, à cause du couple (x,modulo)=(333,129) :

#!/usr/bin/env python
# -*- coding: UTF-8 -*-

from fractions import gcd

def affiche_schema(lg,Liste):
    for nb in Liste:
        print(" "*(lg-len(str(nb)))+str(nb),end="")
    print()

def calcul_inverse(x,modulo):
    a,b,r=max(x,modulo),min(x,modulo),0
    Dividendes_diviseurs_restes,Opp_Quotients,Fin=[a,b],[0],[0]
    while r!=1:
        a,q,r=b,a//b,a%b
        b=r
        Dividendes_diviseurs_restes.append(r)
        Opp_Quotients.append(-q)

    c,n=0,len(Dividendes_diviseurs_restes)
    Fin=[0 for ii in range(n+1)]
    Fin[-2]=1
    for ii in range(n-1,1,-1):
        Fin[ii-1]=Fin[ii]*(Opp_Quotients[ii-1])+c
        c=Fin[ii]
    if x<modulo:
        inv_mod = Fin[1]
    else:
        inv_mod=Fin[2]
    if inv_mod<0:
        inv_mod=inv_mod%modulo
       
    lg=max(len(str(x)),len(str(modulo)))
    affiche_schema(lg,Dividendes_diviseurs_restes)
    affiche_schema(lg,Opp_Quotients)
    affiche_schema(lg,Fin)      
    return inv_mod

print("     *************************************************")
print("     *  Calcul de l'inverse d'un nombre x modulo n   *")
print("     *  avec le schéma présenté par Youssef Ouragh   *")
print("     *************************************************\n\n")      
       
x,modulo=10946,6765
if gcd(x,modulo) != 1:
    print ("Désolé, votre nombre et le modulo ne sont pas premiers entre eux.")
    print ("Sélectionner un autre couple de valeurs.")
else:
    print ("\nL'inverse de",x,"modulo",modulo,"est :",calcul_inverse(x,modulo))

Sortie :


     *************************************************
     *  Calcul de l'inverse d'un nombre x modulo n   *
     *  avec le schéma présenté par Youssef Ouragh   *
     *************************************************


10946 6765 4181 2584 1597  987  610  377  233  144   89   55   34   21   13    8    5    3    2    1
    0   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1
    0 4181-2584 1597 -987  610 -377  233 -144   89  -55   34  -21   13   -8    5   -3    2   -1    1    0

L'inverse de 10946 modulo 6765 est : 4181
hgaruo1951 a écrit :

non monsieur vous commettez encore une erreur il suffit de faire  2584+(-533)

Nan, l'erreur est de ton côté : tu n'as pris la peine de lire le code ou pas compris (ce n'est pas grave en soi, mais il ne faut sauter aux conclusions hâtives)
J'établis un tableau avec 3 listes occupant 3 lignes.
Puis j'interprète le résultat
Ici x=1595<modulo=2584, donc je prends le 2 élément de la liste Fin (le 1er élément a pou indice 0) donc -533.
Puis -533 étant négatif, je le ramène dans [tex]\mathbb{N}[/tex] en prenant l'inverse modulo 2584 de -533, ce qui en Python s'écrit -533%2584 = 2051
Toi, tu me proposes 2584+(-533) = 2051 : ça change quoi ?

Si x avait été supérieur au modulo, par ex :
(x,modulo)=(2584,4595)
au lieu de calculer -533*0+329, je prends directement le 3e élément de la liste Fin : Fin[2], soit 329.
Quel que soit le nombre z présent à la place de -533 z*0 =0, ce calcul est donc inutile...
Depuis hier, je n'ait que travailler sur le schéma que tu nous as présenté.
Je ne me suis pas préoccupé de savoir si tu t'en attribues abusivement la paternité ou non, ce n'était pas mon propos...
J'ai texté ce schéma en long en large et en travers avec mon petit programme (que je me suis efforcé de rendre plus lisible en fin de matinée)
Je n'ai pas trouvé de faille : j'ai contrôlé avec un autre programme que j'avais pêché ailleurs, il y a quelques années. résultats conformes.

Par rapport à la méthode classique employé au dessus par freddy :
- je reconnais aisément que c'est bien plus rapide,
- que les "souffrances" dues au calcul sont inexistantes,
je serais de mauvaise foi si je disais le contraire...
Et la personne qui te traite de mégalomane sur l'autre forum est coutumière du fait : il a même traité quelqu'un de "jeune branleur"...
Ce ne sont pas des procédés corrects...

Je t'ai fait des remarques de forme, sur l'utilisation de ce forum : sur l'usage des forums d'entraide où ne peut pas faire n'importe quoi, où se doit d'être dans l'orthodoxie mathématique quand on répond à une demande d'aide...
Pour toute autre digression, le café mathématique est là.
On a déjà eu des génies méconnus (oui, c'est de l'ironie), des intervenants :
- qui ont résolu des conjectures qui résistent depuis des lustres aux meilleurs mathématiciens du monde,
- qui ont résolu la construction sans faille des nombres premiers,
- l'un qui démontrait que [tex]\mathbb{R}[/tex] était dénombrable (au moins 20 pages de discussion avant que je ne la ferme.)
Là-dessus, tu arrives avec un schéma dont tu n'annonces nulle part que tu le revendiques comme tien (je ne me prétends pas compétent pour en juger, je ne m'intéresse qu'aux faits), comme si tu te cachais...
Alors, lorsque je m'en suis rendu compte, j'ai déplacé la présente discussion...
Puis tu as voulu intervenir par une aide véritable mais non orthodoxe : je t'ai dit non et t'ai expliqué pourquoi.
Tu récidives...
Le gardien de l'ordre, ici, c'est moi : c'est à moi, qu'il incombe de veiller à ce que le forum continue à être propre (au sens de non pollué par des interventions qui doivent aller dans la bonne section).
Alors, j'ai réagi et je t'ai dit (en résumé) :
soit tu respectes cet ordre,
soit si ça ne te plaît, d'aller voir ailleurs si l'herbe y était plus verte (qu'ici). Formule courante.

Pourquoi vouloir aller dans un endroit sans herbe ? Tu n'es pas apparenté a Attila, mais de nom (au moins) à Saint Augustin...

Bon, explications de texte du programme.
Fonction calcul inverse.
J'ai commencé par initialiser les 3 listes de nombres.
Je remplis simultanément les 1ere et 2e listes en calculant q et r :
a,q,r=b,a//b,a%b
Le 1er nombre, a, prendra la valeur de b ; q prendra comme valeur celle du quotient entier de a par b (a//b), et r le reste (a%b)
Cela fait je donne alors à b la valeur de r,
je stocke r, à la suite des nombres existants, dans la première liste ainsi que les opposés des quotients dans la 2e liste.
Le test de sortie de la boucle est r=1 (tant que r est différent de 1, faire...)
Là en sortie de boucle, j'ai besoin de connaitre le nombre de valeurs entrées dans la 1ere liste.
j'initialise la 3e liste avec ce nombre de zéros +1 (il faudra que je corrige, j'ai changé d'avis en cours de route) : le dernier 0 ne sert à rien.
J'initialise l'avant dernière valeur à 1 (ce devrait être la dernière en virant le 0 zéro final).
La variable c est le correctif que j'applique au produit. Je lui donne la valeur 0 pour commencer.
Nouvelle boucle avec un nombre connu d'éléments que je parcours en partant de la fin avec des indices décroissants par pas de -1
Je prends Fin[ii], je multiplie par Opp_Quotients[ii-1]et j'ajoute c.
Je remplace le 0 de Fin[ii] par le résultat précédent, et je donne ensuite à c cette valeur Fin[ii].
Je décrémente i de 1 et je recommence.
L'indice "d'arrêt" de ma boucle est 1 : elle s'arrête en fait à 2...
C'est le même phénomène dans l'autre sens avec une boucle for de 0 à n, la dernière valeur utilisée est n-1...
Maintenant, je ne me sers que des 2e et 3e éléments de la liste Fin, soit Fin[1] et Fin[2].
Avec des tests conditionnels dépendant si x<modulo ou x>modulo déjà expliqués plus haut.

J'ai une une procédure (elle ne renvoie rien) affichage qui se charge d'afficher les 3 lignes successives.
J'ai besoin de la longueur du nombre le plus grand pour formatter l'affichage (on peut sûrement s'y prendre autrement que moi, mais j'ai cherché : si la longueur est connue et non stockée dans une variable, je sais faire autrement, là non. et je laiss entre les nombres une espace plus le nombre voulu selon le nombre de chiffres (+le signe- éventuel) du nombre à afficher...

J'ai reproduit strictement la procédure manuelle que tu exposes.

@+

[EDIT]Affichage de lignes trop longues pour le forum : sabotage.
Je vais contourner le problème...
170927040010409856.png

Dernière modification par yoshi (27-09-2017 14:33:22)


Arx Tarpeia Capitoli proxima...

En ligne

#24 27-09-2017 14:32:08

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 7 457

Re : congruences

Re,

je crois que j'ai compris la méthode, il n'y a rien de vraiment révolutionnaire, il s'agit simplement d'écrire différemment ce qu'on fait dans Euclide étendu. Le risque d'erreur n'est pas non plus moindre, ce me semble.


De la considération des obstacles vient l’échec, des moyens, la réussite.

Hors ligne

#25 27-09-2017 17:39:12

hgaruo1951
Membre
Inscription : 13-09-2017
Messages : 104

Re : congruences

Bonjour ,

Je n'ai jamais dit que mon schéma est révolutionnaire. J'ai toujours précisé qu'il en
est un moyen qui permet de synthétiser l'algorithme d'Euclide. Je ne fais que suivre
un autre cas similaire à ma position vis à vis de mon schéma . En effet le meilleur
exemple est celui concernant le schéma de HORNER-RUFFUNI ( autrefois on disait
simplement HORNER!!). Ce dernier schéma , vous le savez certainement n'est autre
chose qu'une méthode synthétique de la division euclidienne. Oui car les nombre
du tableau de RUFFINI on les retrouve dans la division euclidienne  lorsque qu'une telle
division entre deux polynômes se fait sous la potence.

Vous dites , M. Freddy,  que vous avez saisi les opérations de ce schéma et bien je
regrette de vous dire que vous n'avez découvert que le 1/5 ème de ce schéma et
son utilisation peut servir à d'autre fins ce que l'on ne peut faire par la voie classique.

Par exemple je vous affirme qu'avec ma méthode combinée avec la méthode d'OR je peux
résoudre toute équation polynomiale de la forme

     Ai(x) Ui(x)=B(x)  avec  i=1 à n

beaucoup plus facilement que ce que d'autres préconisent.
Cordialement.

Hors ligne

Pied de page des forums