Bonjour,

toute l'astuce est d'exécuter certaines opérations et pas d'autres pour obtenir à chaque fois un 99u + 56v = r
on met les 56 en facteur et les 99 en facteur sans avoir exécuté, et seulement alors on exécute

99 = 56×1 + 43, soit 43 = 99 - 56×1 = (1×99+0×56) - (0×99+1×56)×1 = 1×99 - 1×56,
x = 1, y = -1 sont solutions de 99x + 56y = 43

56 = 43×1 + 13, soit 13 = 56 - 43×1 = (0×99+1×56) - (1×99-1×56)×1 = (0-1)×99 + (1+1)×56,
x = -1, y = 2 sont solutions de 99x + 56y = 13
etc

évidemment c'est beaucoup plus facile si on a programmé ça une fois pour toutes et qu'il n'y a plus qu'à copier-coller ces calculs = le résultat de l'exécution de l'algo...

bonsoir, je ne comprends pas trop ce que vous voulez dire par la desolée mon prbleme cest que par exemple je me retrouve avec un 13 a simplifié ce qui donne 56-43 or il faut alors simplfier 43 puis encore et encore et encore alors que quand mon professeur le fait ou sur les exercices il ny a pas autant detapes ou de nombres ..et du coup je my perds

il ne faut surtout pas simplifier des trucs à tort et à travers mais garder à tout moment des "u×99 + v×56" (avec u et v des valeurs numériques)
sans surtout effectuer l'opération !!

ainsi le "13 à simplifier" c'est ce que je t'ai écrit : (0-1)×99 + (1+1)×56, soit -1×99 + 2×56
et on laisse 13 écrit comme ça
ce sera peut être plus clair à l'étape suivante :

43 = 13×3 + 4, soit 4 = 43 - 13×3 = (1×99-1×56) - (-1×99+2×56)×3

j'ai remplacé "formellement" sans rien simplifier le "43" par ce qu'on avait calculé "1×99 - 1×56", tel quel sans en changer un iota.
et le "13" de 13×3 par ce qui est calculé à l'étape d'avant, tel quel "-1×99 + 2×56" sans en changer un iota.

puis je factorise (je regroupe) tous les termes en "56" et tous les termes en "99" :
(1 + 3×1)×99 - (1 + 3×2)x56 soit 4 = 4×99 - 7×56, x = 4, y = -7 solutions de 99x + 56y = 4
etc

que le prof "en classe" ait choisi des exemples plus courts n'empêche pas que l'on puisse avoir besoin de répéter de nombreuses étapes avant d'achever l'algorithme d'Euclide :
de trouver un reste nul, et donc le reste d'avant = le PGCD, et le calcul précédent de donner les solutions de l'équation
99x + 56y = ce PGCD (qui est ici 1)

cette technique est une disposition des calculs "au fur et à mesure"

on peut aussi terminer l'algorithme "tout nu" sans rien calculer d'autre que les divisions
puis une fois l'algorithme terminé de remonter en partant de la fin :

99 = 56×1 + 43
56 = 43×1 + 13
43 = 13×3 + 4
13 = 4×3 + 1
4 = 1×4 + 0, fini.

puis on "remonte"
1 = 13 - 4×3

4 = 43 - 13×3, je remplace ce "4" dans l'équation précédente :
1 = 13 - (43-13×3)×3
je regroupe les "13" et les "43"
1 = (1+9)×13 - 43×3 = 10×13 - 43×3

13 = 56 - 43×1, que je remplace dans l'équation précédente :
1 = 10×(56 - 43×1) - 43×3 je regroupe les 56 et les 43 :
1 = 10×56 - (10×1 + 3)×43 = 10×56 - 13×43

43 = 99 - 56×1 que je remplace dans l'équation d'avant :
1 = 10×56 - 13×(99 - 56×1) je regroupe :
1 = (10 + 13×1)×56 - 13×99

et finalement
1 = 23×56 - 13×99

Bonjour, tout dabbord merci davoir pris le temps de me repondre

je pense que j'ai appliqué la methode que vous indiquez, par exemple pour pour 37 et 23 en remontant l'olgorithme ca me donnne : 1=5-(9-5)
         1=14-9-(9-(14-9))
         1=14-(23+14-(23-14-(14-(23-14))
         en elevant les parentheses ca me donne :
         1= 37-23-23+37-23-23+37-23+37-23-23+37-23
        23*(-8) et 37*5 cette fois cette le resultat est bon mais comme vous le voyez ca fait beaucoup de chose a remonter remplacer 5 par 114-9 puis 14 par 37-23 etc et cest tres long et il y a beaucoup de chances de faire des erreur de signes etc donc je me demander si il y avait une autre facon ou si c'est bien la bonne ?

voila jespere que je ne mexprime pas trop mal, merci beaucoup

effectivement c'est assez pébnible et le risque d'erreurs de calcul est très élevé
il faut faire ça très "zen" pour s'en sortir.

je ne pense pas qu'il y ait une autre méthode que les deux que j'ai indiquées
celle que j'avais indiquée au début qui fait les calculs au fur et à mesure
et celle que tu as plutôt vue en cours qui remonte à partir de la fin.


sinon on peut "cacher sous le tapis" tous ces calculs en explicitant un algorithme qui fonctionne mais qui, puisque tout est caché, a un fonctionnement "mystérieux"
mais qui en réalité fait très exactement les calculs "au fur et à mesure" que je proposais (la "preuve" et la raison de cet algorithme est donc ces calculs détaillés et "pénibles")
une preuve plus compacte utilise le calcul matriciel.

résoudre ax + by = 1 (trouver x et y, a et b donnés) ainsi "au passage" que le PGCD de a et b :

Posons : r₀ = a, r₁ = b (a > b > 0) sinon on échange et on prend les valeurs absolues, quitte à rechanger les signes à la fin)
P₀ = 0, P₁ = 1 et Q₀ = 1, Q₁ = 0

Puis répéter depuis i = 2
- Division entière de r_i-2 par r_i-1 : r_i-2 = r_i-1q_i + r_i qui définit r_i et q_i
- Calculer P_i = -q_iP_i-1 + P_i-2 et Q_i = -q_iQ_i-1 + Q_i-2
- jusqu'à r_n = 0

p = r_n-1 est le PGCD de a et b (algorithme d'Euclide)
si p = 1 alors x = Q_n-1, y = P_n-1 est une solution de ax + by = 1


disposition pratique de ces calculs avec 99u+56v=1

r      q        P       Q
99              0       1     deux premières lignes d'initialisation
56              1       0
43     1        -1      1     division 99 par 56 quotient q = 1, reste r = 43, puis P = (-1)*1 + 0,  Q = (-1)*0 + 1
13     1        2       -1    idem, P = (-1)*(-1)+1     Q = (-1)*1 + 0
4      3        -7      4     idem, P = (-3)*2 + (-1)   Q = (-3)*(-1) + 1
1      3        23      -13   idem, P = (-3)*(-7) + 2   Q = (-3)*4 +(-1)

daccord merci beaucoup , une derniere petite faveur pouvez vous m'aider sur ca svp https://www.ilemaths.net/sujet-equation-diophantienne-et-congruences-623680.html

Bonjour

En essayant de suivre j'ai trouvé
28u+23v =1  u=-9 ,v =11

salut

une autre facon de faire si tu a vu les congruences ,

28u+23v =1  ici 28=5[23] (1)  et 23=0[23] (2) ensuite on multiplie (1) par u soit 28u=5u[23] et (2) par v

soit 23v=0[23] on effectue une difference mbr à mbr des expressions en gras , il vient :

28u-23v = 5u[23]   soit aussi  1=5u[23] ou encor 5u=1[23] et donc une premiere valeur de u qui convient est u=-9

en effet 5.(-9) = -45 = 23q + 1   et q=-2

PS HS :
en fait il y a aussi une autre méthode qui exploite directement les congruences et le petit théorème de Fermat.
rappel de ce théorème :
si p est un nombre premier et si a n'est pas un multiple de p alors a^p-1 1 [p]

on peut étendre ce théorème à des p non premiers (extension due à Euler) :
si a et b sont premiers entre eux, alors il existe un nombre entier n appelé indicateur d'Euler de b, n = (b), tel que a^(b) 1 [b]
l'exposant n ainsi obtenu n'est pas le plus petit exposant qui a cette propriéte
mais le plus petit est forcément un diviseur de (b)
(b) est en fait par définition le nombre de nombres premiers avec b et < b, 1 inclus.

si b est premier l'indicateur d'Euler est (p) = p-1
sinon on peut calculer facilement (b) à partir de la décomposition en nombres premiers de b

appliquons cela à notre 99u+56v=1
qui exprime que 99u 1 [56]
comme 99 43 [56] cela revient au même de résoudre 43u 1 [56]
on sait que 43⁽⁵⁶⁾ 1 [56]
et par conséquent
(43^(56)-143)u (43^(56)-1)1 [56]
soit "directement" la solution :
u 43^(56)-1 [56]
il ne reste plus qu'à calculer (56) et à élever 43 à la puissance (56)-1 ...
cela semble assez affreux mais non ...
56 = 2³7 et donc (56) = (2³ - 2²)(7 - 1) = 24
(sans démonstration de cette règle de calcul de (b))

la solution est donc u 43²³ [56]
évidemment on ne calcule pas 43²³ ce serait abominablement affreux !
mais on fait les calculs modulo 56, en utilisant une méthode "d'exponentiation rapide"

43² = 1849 1 [56]

un miracle extraordinaire s'est produit ici : les calculs sont terminés !
en effet on avait dit que le théorème garantissait que a^(b) 1 [b] mais que ce n'était pas le plus petit exposant
ici en fait on a déja 43² 1 (2 est bien un diviseur de 24)
et donc on obtient directement 43²³ = (43²)¹¹43 1¹¹43 43 [56]

et la solution u 43 -13 [56]
on reporte ça dans 99u + 56v = 1 pour obtenir v
terminé presque sans calculs (numériques, parce que la "théorie" est tout de même plus compliquée !)
bon on pouvait ici facilement calculer la décomposition en facteurs premiers de 56, et "on a eu du bol" dans le calcul des 43ⁿ

autre exemple 28u+23v = 1(de dpi)

la théorie précédente donne directement la solution
u 28^(23)-1 [23]
comme 23 est premier (23) est simplement 22 et on a à calculer
u 28²¹ 5²¹ [23]
5² = 25 2 [23]
5³ 25 10 [23]
5⁴ (5²)² 2² 4 [23]
5⁷ 5⁴5³ 410 40 17 [23]
5¹⁴ (5⁷)² 17² 289 13 [23]
5²¹ 5¹⁴5⁷ 1317 221 14 -9 [23]

tous les nombres calculés sont < 23² puisqu'on calcule tout modulo 23

cette méthode est-elle vraiment plus pratique que l'algorithme d'Euclide ?? j'en doute fortement !!

Bonjour flight,

certes.
"si tu a vu les congruences" son autre exo montre que oui

ta méthode semble très bien mais elle "déraille" à :

:D:D  @mathafou j'ai pleuré de rire sur ta derniere remarque ..m'enfin c'est vrai!!.. ca fait un peu sorti
du chapeau :D:D

je vais tenter d'eclairer ma demarche

partant de 5u=1[23]   que je peux ecrire sous la forme 5u = 23k + 1  je sors u qui vaut u = (23k+1)/5

et me demande alors pour quelle valeur de k , u est entier relatif , pour ca j'ai examiné les restes possibles

de la division de k par 5 qui peut proposer des restes compris entre 0 et 5

si k=0[5] ---> 23k=0[5] ---> 23k+1=1[5]  ne convient pas
si k=1[5] ---> 23k+1=23+1[5] ---> 23k+1=24[5] ---> 23k+1=4[5]   ne convient pas
si k=2[5] ---> 23k=46[5] ---> 23k+1=47[5] ---> 23k+1=2[5]   ne convient pas
si k=3[5] ---> 23k=69[5] ---> 23k+1=70[5] ---> 23k+1=0[5]    convient !
si k=4[5] ---> 23k=92[5] ---> 23k+1=93[5] ---> 23k+1=3[5]   ne convient pas

donc u revêt la forme  u = (23.(3+5p) + 1)/5 = (115.p + 70)/5.

si p = -1 , u = -9
si p = 0,  u = 14
si p = 1  , u = 37
etc...