Euclide étendu par le schéma d'Ouragh
Discussion fermée
Affichage des résultats 1 à 27 sur 27

Euclide étendu par le schéma d'Ouragh



  1. #1
    OY1951

    Euclide étendu par le schéma d'Ouragh


    ------

    Bonjour,

    Comme cela a été convenu dans la page de discussion "Congruence linéaire" ,
    page ouverte par Maxime10, je vais présenter les bases théoriques du schéma
    d'OURAGH. En fait je rappelle le problème auquel ce schéma s'adapte et allégera
    (comme chacun pourra le vérifier!!) le format et le volume des calculs inhérents
    à ce problème:

    " Détermination d'une solution particulière d'une équation diophantienne linéaire de
    la forme Ax+By=C"
    avec
    1er cas : A,B,C sont des entiers relatifs donnés et x,y des entiers relatifs inconnus.
    2ème cas: A,B,C sont des polynômes donnés et x,y des polynômes inconnus.

    Dans ma démarche je passerai sous silence l'existence des solutions de telle ou telle
    équation et qui se résume à ce que C soit divisible par PGCD(A,B).

    Chacun connait l'immortel théorème d'Euclide relatif à une division euclidienne antre
    deux réels A et B et que l'on traduit par l'identité :
    A = B Q + R
    A=dividende . ,.. B = diviseur ..,. Q = quotient .. et R = reste de cette division.

    Pour la détermination du PGCD(A,B) au moyen de l'algorithme d'Euclide cette dernière
    identité sera écrite sous la forme A-BQ-R=0 et cela donnera (avec comme dernier
    reste non nul Rn)

    .... A - B Q1 - R1 =0............................ ...................(1)
    .....B - R1 Q2 - R2 =0..........................(2 )
    .....R1 - R2 Q3 - R3 =0......(3)
    .....R2 - R3 Q4 - R4 =0......(4)
    .....R3 - R4 Q5 - R5=0.......(5)
    .............................. .............................. .............................. .....
    .............................. .............................. .............................. ......
    .....Ri - Ri+1 Qi+2 - Ri+2 =0......(i+2)
    .............................. .............................. .............................. ..........
    ....Rn-4 - Rn-3 Qn-2 - Rn-2 = 0....(n-2)
    ....Rn-3 - Rn-2Qn-1 - Rn-1 =0.....(n-1)

    et la dernière on l'écrit sous la forme

    ....Rn-2 - Rn-1 Qn = Rn .............(n)

    Problème d’électricité je préfère revenir un peu plus tard.

    Cordialement.

    -----
    Dernière modification par OY1951 ; 29/12/2014 à 09h19.

  2. #2
    OY1951

    Re : Euclide étendu par le schéma d'Ouragh

    Bonjour,

    Ainsi je poursuis ma démonstration.
    Multiplions la ième identité par un entier relatif ki (pour
    i variant de 1 à n) et sommons par la suite membres à membre
    toutes les nouvelles identités . On obtient alors après regroupement :

    A k1 + B {-k1 Q1 +k2}+R1 {k3-k2Q2-k1}+R2{k4-k3Q3-k2}+

    ....R3{k5-k4Q4-k3} + R4{k6-k5Q5-k4}+....................
    .............................. .............................. ...................
    + Rn-4{kn-2-kn-3Qn-3-kn-4+ Rn-3{kn-1-kn-2Qn-2-kn-3+ Rn-2{kn-kn-1Qn-1-kn-2 +

    + Rn-1[-kn-1-knQn} = knRn

    Question : Comment choisir les ki (i=1 à n) pour que la dernière
    relation se réduit à Au+Bv=Rn (où j'ai omis de signaler que
    Rn=PGCD(A,B) )
    La réponse est dans ce cas évidente : il suffit d'avoir :

    kn=1 et annuler toutes les parenthèses du premier membre et
    qui sont en produits des différents restes Ri pour i=1 à n-1.
    Ainsi on obtient à l'issue de cette résolution (puisque kn=1)
    le schéma de calcul suivant:

    kn-1=-knQn=-Qn ;
    kn-2=-kn-1Qn-1+kn ;
    kn-3=-kn-2Qn-2+kn-1 ;
    kn-4=-kn-3Qn-3+kn-2 ;
    .............................. ..........................
    k3=-k4Q4+k5 ;
    k2=-k3Q3+k4 ;
    k1=-k42Q2+k3 ;

    et enfin (puisque k1 et k2 sont à présent connus)

    u=k1 et v=-k1Q1+k2 .

    Pour mettre en pratique ce schéma je propose que ces calculs se fassent
    dans un tableau dont l'allure de départ est construit sur la forme des
    " T-divisions euclidiennes comme suite :

    .........A.......B......R1.....R2.....R3.....Rn-3.....Rn-2......Rn-1.....Rn
    .................Q1.....Q2......Q3.............Qn-2.....Qn-1......Qn

    Une fois le dernier reste non nul est atteint on change les signes des
    différents quotients Qi pour avoir

    .........A.......B......R1.....R2.....R3.....Rn-3.....Rn-2......Rn-1.....Rn
    ................-Q1....-Q2.....-Q3............-Qn-2....-Qn-1.....-Qn

    Ceci étant réaliser on exécute le schéma d'OURAGH en ce déplaçant de la droite
    vers la gauche pour obtenir (après avoir fixer kn=1. Les résultats
    apparaîtront sur le tableau final suivant:

    .........A.......B......R1.....R2.....R3.....Rn-3.....Rn-2......Rn-1.....Rn
    ................-Q1....-Q2.....-Q3............-Qn-2....-Qn-1.....-Qn
    .................v.....u=k1....k2.................kn-2.....kn-1......kn=1

    Tel est le schéma qui synthétise l'algorithme d'Euclide étendu : on notera qu'au
    moyen de ce schéma r'une part toutes les "étourderies" qui apparaissent dans les
    différents reports dans l'algorithme étendu sont complètement évitées et d'autre part
    la célérité avec laquelle on arrive à obtenir la solution particulière (u;v) vérifiant
    Au+Bv=PGCD(A,B). Le seul inconvénient qu'on pourra reprocher à ce schéma
    est le fait que lorsqu'on passera à sa programmation sur un outil informatique
    est qu'il exige l'utilisation d'un tableau. Mais est ce que vraiment cela constitue
    un véritable inconvénient sachant que pour gérer des nombres de l'ordre de
    1022 un tableau de 100 éléments (Qi avec i=1 à 100) fait
    largement l'affaire ? En contre partie je laisse à chacun de vérifier que le nombre
    d'opérations totales sont inférieures à tous ceux des différents procédés utilisés
    antérieurement pour le même problème. Je me tiens disposé à toutes les
    remarques concernant ce travail.
    Pour le cas des polynômes le même procédé peut être appliqué. Néanmoins lorsque
    on applique ce schéma à la main le tableau précédent s'adapte mal aux calculs.
    Pour cela je montrerai qu'on a avantage à effectuer les calcule sur un tableau d'OR.

    Cordialement.

  3. #3
    OY1951

    Re : Euclide étendu par le schéma d'Ouragh

    Mille excuse je propose un schéma sans donner d'exemple? Je corrige cela
    par l'exemple suivant
    Déterminer une solution particulière de 1222x+449v=2

    On cherche d'abord le PGCD(1222 , 449)
    ...1222....449.....324.....125 .....74.....51......23......5. ....3.....2.....1=PGCD(1222 , 449)
    ................2.........1... .....2........1.......1....... 2.......4.....1.....1

    Passons au calcul des ki
    ...1222....449.....324.....125 .....74.....51......23......5. ....3.....2.....1=PGCD(1222 , 449)
    ...............-2.......-1........-2......-1.....-1.......-2.....-4...-1....-1
    ........... -479...176.....-127.....49....-29.....20.....-9....2....-1.....1

    On aura donc comme solution particulière (au second membre de l'équation on a un 2)

    u=176*2=352 et v=2*479=-958

    Cordialement.

  4. #4
    sylvainc2

    Re : Euclide étendu par le schéma d'Ouragh

    Cette méthode pour calculer les coefficients de Bézout est déjà connue depuis longtemps. C'est celle qu'on utilise quand on fait un programme sur ordinateur qui utilise la récursivité, je donne comme référence le livre Introduction to algorithms de Cormen,Leiserson, Rivest: voir sur google books, au chapitre 31, page 860:
    http://books.google.ca/books?id=NLng...page&q&f=false

    C'est l'algo appelé Extended-Euclid. À la ligne 4 où il est écrit:


    cette ligne est l'équivalent de votre formulation pour le calcul de la 3e ligne des valeurs k, par exemple kn-2=-kn-1Qn-1+kn.

    La première édition de ce livre a été publiée en 1990, et je suis certain que cet algo existait déjà bien avant cette date, donc ce n'est pas vraiment nouveau.

    D'ailleurs on peut aussi l'écrire sous forme d'un tableau vertical, comme ceci:
    j'utilise votre exemple: 1222u + 449v = pgcd(1222,449)



    On commence par faire les divisions euclidiennes à chaque ligne i: a - qb = r.
    Puis à la dernière ligne, où r=0, on initialise u=0 et v=1 et on remonte en faisant:
    ui-1 = vi
    vi-1 = ui - qi-1 vi

    On voit que la colonne a correspond à la ligne 1 de votre tableau (avec le pgcd rajouté au bout à droite), la colonne q est la ligne 2, et la colonne v est la ligne 3 de votre tableau.

    La démonstration de ces formules est donnée (an anglais) dans le lien du livre sur google books, je vais la répéter ici:
    on note d = pgcd(a,b). À chaque ligne i on veut avoir d = ai ui + bi vi

    Dans l'algo d'Euclide on a:
    ai = bi-1 et
    bi = ri-1 = ai-1 - qi-1 bi-1

    donc:

    d = bi-1 ui + (ai-1 - qi-1 bi-1) vi
    = ai-1 vi + bi-1(ui - qi-1 vi)
    = ai-1 ui-1 + bi-1 vi-1

    C'est pour ça qu'il faut prendre:
    ui-1 = vi
    vi-1 = ui - qi-1 vi

    et qu'à la dernière ligne du tableau on initialise u=0 et v = 1 car le b de cette ligne est le pgcd donc b=a*0 + b*1.

    Enfin, tout ça c'est pour dire que votre méthode est déjà connue.

  5. A voir en vidéo sur Futura
  6. #5
    OY1951

    Re : Euclide étendu par le schéma d'Ouragh

    Bonjour M. Sylvainc2,
    Merci , merci et merci encore pour votre message et je suis très sincère!!!. Il est vrai que je suis déçu
    pour cette partie de la question car je ne peux plus faire valoir la paternité. Il est vrai j'ai mis du temps
    (quelques longues heures!!!) avant de prendre mon courage à deux mains et surtout suivre le bon sens
    qui me dit au fond ma démarche n'est pas complètement ridicule pour toute les raisons suivantes :
    1) ma démarche a toujours était sincère et je n'ai à aucun moment voulu tromper qui que ce soit.
    Pour preuve vous avez cette démarche et vous serrez gré de bien vouloir visionner la vidéo que j'ai mis
    en ligne " http://www.youtube.com/watch?v=D14JvuTpv5U " et dans laquelle mon euphorie était
    apparente à ce moment là.
    2) le tableau que j'ai proposé à le mérite d'alléger l'écriture ( et seulement l'écriture et non le procédé!)
    et contredit même certains auteurs qui affirment que les tableaux pour la détermination du pgcd ne
    peuvent servir dans la remontée de l'algorithme d'Euclide.
    3) En utilisant le même procédé le me permet de poser cette question:
    " en utilisant le même procédé est-ce que quelqu'un

  7. #6
    OY1951

    Re : Euclide étendu par le schéma d'Ouragh

    je poursuit mon intervention précédente

    3) En utilisant le même procédé je me permets de poser cette question:
    " en utilisant le même procédé est-ce que quelqu'un peut nous affirmer que de la solution particulière
    de l'équation ( x^6-x^5+2x^3-x+1) u(x) + (x^3-x^2+1) v(x)=x^5+x^3+1 ) a été faite sur
    tableau (x) par .....(site(s) ; références.... )"
    J'espère que personne ne prendra le risque d'affirmer que cela n'est pas possible car j'affirme que
    je peux le faire et cela en moins de 12mn.
    OUI DANS CE CAS JE NE RISQUE A AUCUN MOMENT DE ME RIDICULISER .

    Enfin je termine en vous remerciant encore une fois M. Sylvainc2.

    Cordialement.
    Dernière modification par OY1951 ; 01/01/2015 à 12h04.

  8. #7
    OY1951

    Re : Euclide étendu par le schéma d'Ouragh

    corrigez s'il vous plait

    "J'espère que personne ne prendra le risque d'affirmer que cela n'est pas possible car j'affirme que
    je peux le faire et cela en moins de 12mn. "

    par

    "J'espère que personne ne prendra le risque d'affirmer que cela n'est pas possible d'exécuter cela
    sur tableaux car j'affirme que je peux le faire et cela en moins de 12mn pour l'exercice proposé."

    Ici le réponse est très importante et les automaticiens seraient vraiment intéressés car peut êtrelorsqu'ils
    devront résoudre de tels exercices à la main ils éviteront (peut être?) les calculs de l'inverse
    de le matrice de Sylvester.

    Cordialement.

  9. #8
    OY1951

    Re : Euclide étendu par le schéma d'Ouragh

    Bonjour,

    voilà cinq jours que se sont écoulés et j'attends avec impatience une réponse.
    J'aurai au moins espéré que certains reconnaissent que le tableau que je propose
    est meilleur que celui exposé dans le lien (et repris par M. Sylvainc2 ): la taille est
    deux fois moindre et pour cause aucun nombre n'est repris puisqu'on n'est pas
    obligé de le faire dans mon tableau ce qui n'est pas le cas dans le tableau à six
    colonnes (regarder par exemple les 324 , 125 , 75 , etc...).

    Malgré cette légère différence ce n'est pas à cela que j'aspire à la paternité de ce
    schéma, mais à la question que j'ai posé : Comment synthétiser l'algorithme d'Euclide
    étendu à travers un tableau qui allégerai les calculs et réduirait les tracasseries qui en
    découlent par une application directe de cet algorithme pour par exemple résoudre
    l'équation

    A(x) u(x) + B(x) v(x) = C(x)

    avec A(x)=x8+3x6+x5-4x2+x+2 ,

    B(x)= x3+2x2+3x+4

    C(x) = pgcd(A(x) , B(x))
    , u(x) et v(x) inconnues.

    A cet instant je suis persuadé que s'il y avait quelque part quelque chose qui ressemble
    à ce que j'avais demandé le 01/01/2015 on me l'aurai signalé déjà.

    Je tiens à signaler que les propositions de résolution de ce type d'équation se résument
    principalement à la méthode des coefficients indéterminés dont Sylvester a synthétisé les
    calculs au moyen de sa matrice .
    ( http://fr.wikipedia.org/wiki/Matrice_de_Sylvester , https://books.google.dz/books?id=Yxx...vester&f=false )

    J'attends donc avec impatience une réponse à ma "requête" (!!?).

    Cordialement .

  10. #9
    Médiat

    Re : Euclide étendu par le schéma d'Ouragh

    Bonjour,

    Je ne comprends pas l'argument :
    Citation Envoyé par OY1951 Voir le message
    le tableau que je propose est meilleur que celui exposé dans le lien (et repris par M. Sylvainc2 ): la taille est deux fois moindre
    Dans votre calcul pour 1222 et 449 vous écrivez 50 nombres, la présentation usuelle de l'algorithme d'Euclide étendu en utilise 44 (ce qui n'est pas significatif dans un sens mais encore moins dans l'autre) :

    Dernière modification par Médiat ; 05/01/2015 à 10h16.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  11. #10
    OY1951

    Re : Euclide étendu par le schéma d'Ouragh

    Bonjour Médiat,

    Et si vous recomptez Monsieur? Le seul tableau à retenir érant

    ..1222....449.....324.....125 .....74.....51......23......5. ....3.....2.....1=PGCD(1222 , 449)
    ...............-2.......-1........-2......-1.....-1.......-2.....-4...-1....-1
    ........... -479...176.....-127.....49....-29.....20.....-9....2....-1.....1

    Et même si cela était vrai ma question ne concernait pas ce tableau car en effet
    j'aurai retiré tout ce que j'avance. A cette étape j'ose espérer une aide de votre part.
    Dites aux uns et aux autres donner lui ce qu'il demande : résolution de

    A(x) u(x) + B(x) v(x) = C(x)

    avec A(x)=x8+3x6+x5-4x2+x+2 ,

    B(x)= x3+2x2+3x+4

    C(x) = pgcd(A(x) , B(x)) , u(x) et v(x) inconnues

    sur un lien datant de plus d'une année où cette résolution de cette équation sur un
    tableau qui synthétise l'algorithme d'Euclide étendu. C'est tout ce que je demande.

    Cordialement.
    Dernière modification par OY1951 ; 05/01/2015 à 11h53.

  12. #11
    OY1951

    Re : Euclide étendu par le schéma d'Ouragh

    Bonjour ,

    Ainsi je reviens et je constate que je n'ai pas de réponse. Je dois dire que je le savais :
    la méthode que M.sylvainc2 pense qu'elle est la même que mon schéma ne peut pas
    fonctionner dans le cas de la résolution d'une équation diophantienne polynomiale linéaire .
    Or on sait que si deux méthodes sont exactement les mêmes alors si l'une peut être utilisée pour
    résoudre tel ou tel problème alors l'autre devrait nécessairement en faire de même.
    Ici ce n'est pas le cas . Mieux encore : soit le système aux congruences suivant

    .............x=(lire "est congru à") 8[mod 19]
    ...............x=7[13]
    ...............x=2[9]
    ...............x=4[5]

    J'affirme que je peux résoudre ce système en un temps record et tel que ceux qui
    suggéreront le THEOREME DES RESTES CHINOIS pour effectuer cette résolution seront
    étonnés avec quel rapidité et surtout avec quelle simplicité cela se fera au moyen de mon
    schéma . Si quelqu'un persiste à dire qu'il n'existe pas de différence entre le schéma d'Ouragh
    et celui signalé par M. sylvainc2 ( peut être soutenu encore par Médiat ?) alors qu'il nous fasse
    une démonstration dans ce sens : résoudre soit l'équation diophantienne polynomiale linéaire ou
    ou le système aux congruences cité ici . Evidemment une réponse de type : il suffit d'utiliser tel
    ou tel logiciel équivaut à dire : je ne sais pas le faire "à la main" . Car en ce qui me concerne j'en
    connais plus d'un de ces logiciel .

    Bien cordialement.
    Dernière modification par OY1951 ; 14/04/2015 à 15h39.

  13. #12
    OY1951

    Re : Euclide étendu par le schéma d'Ouragh

    Bonjour,
    Toujours pas de réponse? ceci étant dit , pour ceux qui préconisent
    le tableau semblables à celui donné par M. sylvainc2 je leur conseille de se
    débarrasser de l'une des deux dernières colonnes. Elle en est pratiquement
    "un pléonasme" dans un tel tableau.

    Bien cordialement.
    Dernière modification par OY1951 ; 16/04/2015 à 23h40.

  14. #13
    OY1951

    Re : Euclide étendu par le schéma d'Ouragh

    Bonjour ,

    En effet par exemple soit à déterminer la solution particulière de

    53x+19y=1

    Je procéderai alors ( en utilisant un tel tableau que je fixerai
    horizontalement au lieu de verticalement et ce pour réduire le
    format de cette page!) comme suite
    1) soit

    .........53...........19...... .15.......4........3.......1
    ........................-2.......-1.......-3......-1
    ..........1............-2........3......-11......14

    d'où y0=9 et on aura 53(x0)+19(14)=1 et donc x0=-5

    2) soit

    .........53...........19...... .15.......4........3.......1
    ........................-2.......-1.......-3......-1
    .........................1.... ...-1........4.......-5

    donc on a bien x0=-5 et en résolvant l'équation on trouve y0=14

    A cette étape on me dira peut être : les deux schémas semblent être
    les mêmes . Ma réponse est non car avec mon schéma la recherche d'une
    solution particulière par exemple de l'équation diophantienne

    245r+175s+60u+17v=1

    peut être établie en 2 ou 3 mn alors qu'avec le tableau préconisé par sylvainc2
    on ne peut pas le faire ou si jamais cela peut se faire alors on comparera les
    deux schémas et tant pis pour moi si j'aurai tort. Alors encore une fois: des réponses?

    Bien cordialement.
    Dernière modification par OY1951 ; 17/04/2015 à 00h08.

  15. #14
    OY1951

    Re : Euclide étendu par le schéma d'Ouragh

    Bonjour ,

    pour le dernier exercice je dois préciser :

    solutions particulières non nulles !!!!!

    Bien cordialement.

  16. #15
    OY1951

    Re : Euclide étendu par le schéma d'Ouragh

    Bonjour ,

    HUM , HUM ,HUMSILENCE ,?
    Oui je ne vais pas faire de bruit , mais je vais au moins donner les solutions des
    exercices que j'ai proposé . Je commence par le dernier: recherche d'une solution
    particulière de l'équation diophantienne

    245r+175s+60u+17v=1

    en utilisant "Euclide étendu par le schéma d'Ouragh " (au passage ici on notera le jeu de mots
    utilisé dans ce titre!!!) On a dans ce cas le tableau suivant

    .245.....175......70......35.. ...60.....35....25....10....5. ...17.....5.....2.....1
    ............-1.......-2........0.......0.....-1.....-1.....-2....0.....0....-3....-2
    .(70)..(-105)....70.....-35.....(21)..-35....21..-14....7...(-2)....7....-2.....1

    Et donc on peut vérifier que

    245(70)+175(-105)+60(21)+17(-2)=1

    est vérifiée. "Moralité" : Pourquoi 5 dans le passé alors que 3 suffisait?

    Passons maintenant au systèmes d'équations au congruences .

    Reprenons le système

    .............x=(lire "est congru à") 8[mod 19]
    ...............x=7[13]
    ...............x=2[9]
    ...............x=4[5]


    On a dans ce cas :

    .............................. .............................. .............................. ......à suivre

    Bien cordialement .
    Dernière modification par OY1951 ; 18/04/2015 à 08h27.

  17. #16
    OY1951

    Re : Euclide étendu par le schéma d'Ouragh

    Re- Bonjour ,

    Il est évident que si aucune condition n'est faite sur la solution
    particulière , il serait préférable de poser par exemple r=s=0
    et donc donner la solution particulière de 60u+17v=1 . On aura alors

    ......60......17......9......8 .....1
    ...............-3......-1.....-1
    .......2.......-7......2......-1....1

    d'où 245(0)+175(0)+60(2)+17(-7)=1

    Cordialement.

  18. #17
    OY1951

    Re : Euclide étendu par le schéma d'Ouragh

    Bonjour,

    Ainsi comme promis je poursuis :On a donc à résoudre (lire "=" congru à"
    et "[19]" modulo 19)

    ...............x=8[19]
    ...............x=7[13]
    ...............x=2[9]
    ...............x=4[5]


    ...9........5..........4...... .13.......45.......13......6.. ...19....585...19....15...4... ..3...1
    ............-1.........-1........0.........0.......-3.....-2......0......0....-30....-1..-3....-1
    -1078..2156...-1078...1078...-308...1078..-308...154...-5...154...-5...4...-1...1

    d'où il vient

    x=(-1078)(2223)(4)+(2156)(1235)(2) +(-308)(855)(7)+(-5)(585)(8) [11115]
    soit

    x=8444[11115]


    (Tous les calculs sont supportés par le tableau établi selon le schéma d'Ouragh
    et ce en moins de 5mn .)


    Passons maintenant à la résolution de l'équation diophantienne polynomiale suivante

    A(x) u(x) + B(x) v(x) = C(x)

    avec A(x)=x8+3x6+x5-4x2+x+2 ,

    B(x)= x3+2x2+3x+4

    C(x) = pgcd(A(x) , B(x)) , u(x) et v(x) inconnues.

    .............................. .............................. ......................... à suivre


    Bien cordialement.
    Dernière modification par OY1951 ; 19/04/2015 à 18h16.

  19. #18
    OY1951

    Re : Euclide étendu par le schéma d'Ouragh

    Bonjour ,

    Je m'excuse auprès des "forumeurs" de tarder à donner la solution du
    dernier exercice que j'ai proposé et ce du fait j'avais omis de donner deux
    exemples qui permettent de renforcer l'idée que mon schéma même si
    certains refuseront d'admettre qu'il est original j'espère que leur(s)
    honnêteté(s) leurs feront dire : "certes pas original mais certainement la
    méthode la plus et mieux synthétique de ce qui est se fait sur ce sujet".
    Pour appuyer ce que j'avance prenons l'exemple de ces 17 pirates et leur
    cuisinier qui devraient partager leur butin en part égales tout en attribuant
    le reste (égale à 3 pièces d'or) à leur cuisinier. Les choses ne se déroulèrent pas
    comme ils le souhaitaient et pour cause 6 des 17 pirates meurent dans
    un combat . Donc le nouveau partage équitable entre les 11 pirates restants
    permet au cuisinier de recevoir comme nouvelle part 4 pièces d'Or. En fait 5
    parmi les 11 pirates restants en vie ont été blessés mortellement et donc
    décèdent à leurs tours : il n'en restait que 6 pirates. Alors après
    partage équitable le cuisinier recevrait 5 pièces d'or. Bien sur tout le monde
    a compris que le cuisinier a pris tout le butin en empoisonnant les 6 pirates
    restants en vie " . Question : quel est le nombre de pièces d'or qui constitue
    ce butin " .
    Cet exemple est repris des centaines de fois et aucune des solutions proposées
    ne ressemblent à celle qui va suivre (que j'obtiens au moyen du schéma d'Ouragh)

    Système à résoudre

    ..............x=3[17]
    ..............x=4[11]
    ..............x=5[6]

    ........11........6......5.... .1.......66......17......15... ...2........1
    .........0........-1.....-1....0........0.......-3.......-1.....-7
    ........31......-62....31..-31.......8......-31......8......-7.......1

    et donc

    .....x=31*11*17*5-62*6*17*4+8*66*3[1122]
    et donc
    ................x=785[1122]


    Un autre exemple : exercice proposé et résolu par la méthode de substitution

    .......5x=7[11]
    .......7x=11[5]
    .......11x=5[7]

    par M. Jean-Marie Monier dans son livre
    "LES MÉTHODES ET EXERCICES DE MATHÉMATIQUES MPSI3
    (Editions DUNOD)"

    et donc la solution est obtenue par le schéma d'Ouragh comme suite

    .......5*5*7x=7*5*7[11*7*5]
    .......7*11*7x=11*11*7[5]
    .......11*5*11x=5*5*11[7]

    d'où il vient

    x=-128*275+144*121*7-245[385)=86523[385]=283[385]

    De même je peux citer des dizaines de forums dans lesquels
    de type d'exercices ont été traités mais aucun et je dis bien
    aucun ne le fait par une méthode qui ressemble au mien. Le seul que
    l'on peut rapprocher au mien (je dois même dire peut être???) est
    le théorème des restes chinois .


    Alors la question suivante s'impose d'elle même : Si mon schéma était connu
    pourquoi tous ceux qui ont traité de type d'exercices ne l'on pas proposé
    un moment ou un autre. Et surtout que l'on me dise pas que M. Jean-Marie
    ne connais pas toutes les méthodes pour résoudre ce type d'exercices .

    Bien cordialement .
    Dernière modification par OY1951 ; 21/04/2015 à 12h57.

  20. #19
    OY1951

    Re : Euclide étendu par le schéma d'Ouragh

    Bonjour,

    Et si quelqu'un pense le contraire de ce que j'affirme jusqu'à présent
    je serais le premier à le remercier s'il nous donne la solution de l'exercice
    " Résoudre A(x) u(x) + B(x) v(x) = C(x)

    avec A(x)=x8+3x6+x5-4x2+x+2 ,

    B(x)= x3+2x2+3x+4

    C(x) = pgcd(A(x) , B(x)) , u(x) et v(x) inconnues"


    et ce en utilisant l'algorithme Extended-Euclid .
    Je suis persuadé que personne ne peut le faire au moyen de cet
    algo
    alors que je peux le faire au moyen du schéma d'Ouragh.

    Je suis certain qu'on lira ce message et s'il y avait déjà une réponse on l'aurait
    déjà fourni. Je prends donc à témoin tous ceux qui liront ce message de ce que
    j'affirme..

    Un indice : u(x) peut être le polynôme de second degré
    (-64x2/7)+(-4608x/49)+(-5440/49).

    Cordialement.
    Samedi le 25/04/2015 pour rappel .

  21. #20
    OY1951

    Re : Euclide étendu par le schéma d'Ouragh

    Bonjour,

    Pas d'importance , *** Remarque inappropriée *** alors
    je donne au moins la solution du PETIT EXERCICE suivant:

    Déterminer le couple de polynômes (u(x),v(x)) tel que

    (x6+2x3+3x-1) u(x) + (x3-x+2) v(x)=-1

    Solution :
    Je lance un défi à vous tous les mathématiciens de donner une référence
    dans laquelle un exercice de même type qui a été résolu selon le même schéma
    ( et sur tableau(x) SVP) que celui qui suit et qui
    supporte tous les calculs et ce jusqu'à la vérification :


    ...-1.....3.....0...*...2......0.. .....0.....1.....*...1...*...1 ...*....1
    ...-1.....1.....1...*...0......1.. .....0.....1.....*...0...*...1 ...*....1
    .......................*...2.. ...-1..*...0....1.....*..-1...*..-1
    ............................1. .....1..*..-1....1.....*...2
    .............................. .....-1..*...1....1
    .............................. .....-1..*...0....1

    Utilisons le schéma d'Ouragh à présent

    .............................. ............1
    .............................. ....0......0.......-1......*....-1......*....-1
    .........0......0......0...... ..1.....-1.......1.......*.....1......* .....0
    .........0.....-2......1.......-2.....1.......-1.....................*....-1
    .............................. .............................. ...............*.....0

    On relève de ce tableau

    ................... u(x)=x2-x+1

    et

    .........v(x)=-x5+x4-2x3+x2-2x



    Vérification

    Calcul de (x6+2x3+3x-1)(-x2+x-1)

    ...0.....0....-1.....3.....0.....2......0.... ...0.....1....*......1

    ..-1.....4....-4.....5....-2....2......1.......-1....1...*.....-1
    .............................. .............................. ......*......1


    Calcul de (x3-x+2) v(x)

    ...0.....0.....0.....0.....-2......1.....-2......1.....-1........*........1
    ...0....-4.....4....-5.....2......-2.....-1.....1......-1.......*........0
    .............................. .............................. .............*........-1
    .............................. .............................. .............*.........2

    et ainsi la vérification est faite

    Cordialement.
    Dernière modification par Médiat ; 27/04/2015 à 10h46.

  22. #21
    OY1951

    Re : Euclide étendu par le schéma d'Ouragh

    Bonjour ,

    Oui on ne peut pas me répondre car j'avais raison (et j'ai toujours raison sur ce
    sujet ! ! ! ) . Alors dans ce cas je vais parler d'autre chose . Soit l'énoncé de l'exercice
    type suivant:
    Trouver l'ensemble des triangles rectangles ayant les même périmètre P et dont les
    cotés de chacun d'eux s'expriment en nombres entiers d'unités de longueur.


    Applications : P=360 m.

    Cordialement.
    Dernière modification par OY1951 ; 25/06/2015 à 09h22.

  23. #22
    Médiat

    Re : Euclide étendu par le schéma d'Ouragh

    Bonjour,
    Citation Envoyé par OY1951 Voir le message
    Oui on ne peut pas me répondre car j'avais raison (et j'ai toujours raison sur ce
    sujet ! ! ! )
    Que dire de plus ? Peut-être que toute discussion est impossible et de toute façon inutile !
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  24. #23
    OY1951

    Re : Euclide étendu par le schéma d'Ouragh

    Bonjour,

    Discussion impossible ??? non je ne pense pas!!. Difficile ??? Peut être je vous l'accorde.
    Discussion "Inutile" ??? Je ne le pense pas . Plutôt je pense que votre intervention est un
    peut semblable à la première : celle qui a été faite avant sur le présent sujet. Dans tous les cas
    je laisserai seuls juges les "Forumeurs" de l'importance du sujet et surtout de rechercher
    sur ce site ou autre site s'ils trouvent trace de ce j'avance. A titre de rappel on y trouvera
    dans plusieurs sites (voir même sur Futura Sciences ) la solution de l'exercice

    ..............x=3[17]
    ..............x=4[11]
    ..............x=5[6]
    et dont la solution que j'ai donné c'est à dire

    ........11........6......5.... .1.......66......17......15... ...2........1
    .........0........-1.....-1....0........0.......-3.......-1.....-7
    ........31......-62....31..-31.......8......-31......8......-7.......1

    et donc

    .....x=31*11*17*5-62*6*17*4+8*66*3[1122]
    et donc
    ................x=785[1122]

    solution obtenue en moins de 5 mn. Oui chacun peut vérifier (là je ne demande à personne
    de témoigner ! ! ! ! ) cela. Merci de m'avoir lu.

    Cordialement

  25. #24
    OY1951

    Re : Euclide étendu par le schéma d'Ouragh

    Bonjour,
    Ah j'allais oublier que parmi cet ensemble de triangles est celui dont les côtés
    sont (90;120;150).

    Cordialement.

  26. #25
    OY1951

    Re : Euclide étendu par le schéma d'Ouragh

    Bonjour,

    Et pourtant il y a bien trois autres triangles rectangles dont le périmètre est P=360 (unités de longueur) !!!

    Cordialement.

  27. #26
    OY1951

    Re : Euclide étendu par le schéma d'Ouragh

    Bonjour,

    Un exercice type se pose par ci et par là et dont l’énoncé peut être résumé comme suite:
    "Déterminer l'inverse d'un entier a modulo l'entier b"

    Il est vrai qu'implicitement j'ai donné la solution de cet exercice mais je redonne (donc
    solution "explicite") au moyen de l'exemple suivant :
    Donner l'inverse du nombre 81 modulo 197

    La solution est obtenue très facilement comme suite :

    ......197.........81.......35. ......11.........2........1
    ....................-2........-2........-3........-5
    ...................(90).....-37.......16........-5.......1

    et donc on a : inverse 81 modulo 197 égal à 90 . Pour la vérification on a

    Reste[(90*81)/197]=1 .

    J'espère que tout "Forumeur" jugera honnêtement de l'originalité du schèma d'OURAGH.

    Ah , si je reviens "à l'ensemble des triangles " je peux citer comme second triangle
    par exemple celui dont les côtés sont (72;135;153) !!!!!

    Cordialement.
    Dernière modification par OY1951 ; 26/06/2015 à 13h24.

  28. #27
    Médiat

    Re : Euclide étendu par le schéma d'Ouragh

    Bonjour,

    Les monologues de personnes qui ont "toujours raison sur ce sujet" n'apportent rien à personne : fin du flood !

    Médiat, pour la modération
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

Discussions similaires

  1. Algorithme d'Euclide étendu (TS spé Math)
    Par Jon83 dans le forum Mathématiques du collège et du lycée
    Réponses: 4
    Dernier message: 29/11/2014, 08h45
  2. Inverse modulaire, algorithme d'euclide étendu
    Par Linkounet dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 19/04/2011, 22h31
  3. USB étendu et USB universel
    Par Fistos dans le forum Matériel - Hardware
    Réponses: 0
    Dernier message: 30/04/2010, 17h40
  4. Composé étendu
    Par invite6d981fcb dans le forum Chimie
    Réponses: 9
    Dernier message: 03/11/2009, 19h08
  5. Pic étendu par E²PROM
    Par inviteada8904d dans le forum Électronique
    Réponses: 1
    Dernier message: 04/04/2007, 12h18