Algorithme d'Euclide étendu

Il nous manque une pièce jointe je crois.

Autrement dit, le triplet D, U, V reçoit dans cet ordre ce que renvoie la fonction PGCD appliquée à B et R dans cet ordre.

Ce que tu sembles ne pas avoir compris, Oshine, c'est que la fonction PGCD décrite dans ce livre ne renvoie pas une valeur mais 3 valeurs : D le pgcd des deux polynômes, mais aussi deux polynômes U et V qui sont des coefficients de Bezout tels que UA+VB=D.

Pour connaître U et V, tu dois faire comme l'ordinateur, c'est-à-dire appliquer la fonction PGCD à B et R... et si ça se trouve, il faudra encore l'appliquer à autre chose, etc.
Jusqu'à ce que tu te retrouves dans le cas de base où l'on te donne les valeurs de U et V... puis tu termines les calculs dans l'ordre.

Tu arrives à $U_0$ et $V_0$ quand tu as $B=0$.

@Oshine. Je t'ai souvent conseillé patience, prendre son temps et rigueur, en particulier cet été, mais peut-être ai-je oublié AUSSI de te dire que la magie, dès lors qu'elle est formelle est tout à fait autorisée en maths, dès lors que les hypothèses ne sont pas cachées.

Avant de te dire "je dois mieux maitriser la récursivité", il te faut avoir "le gout de la magie". Et pour ça, pas besoin d'ordinateur.

Sur les entiers, une écriture comme

$f(a,b):=[$
if CasSimple then
ReponseSimple else
$a<b$ then $f(b,a)$ else $f(a,a-b)]$

qui, par snobisme culturel récent dû aux avancées technologiques, est qualifié de "programme informatique"

mérite tout à fait ton respect comme hypothèse mathématique ad hoc

La seule chose que tu ne feras pas, c'est de dire:

"Définition: blabla"

Tu diras plutôt:

"Hypothèse: soit $f$ une fonction telle que blabla"

Par exemple, pour les entiers (je ne spoile pas ton fil en parlant des polynômes et en même temps ça m'évite des efforts), ça prend la forme:

Hypothèse: soit $f: \N^2\to \Z^3$ telle que pour tous entiers $a,b$ :

si $a=b$ alors $f(a,b)=(a,1,0)$ sinon,

si $a=0$ alors $f(a,b)=(b,0,1)$ sinon,

si $a<b$ et $f(b,a) =(d,u,v)$ alors $f(a,b) = (d,v,u)$ sinon,

si $f(a-b,b) = (d,u,v)$ alors $f(a,b) = (d,u,v-u) $

Nous allons démontrer que blabla

Et franchement, la traduction en paradigme informatique, est non seulement "assez triviale", mais surtout UNE TOUTE AUTRE AFFAIRE.

Si tu n'adoptes pas cette "positive attitude", ton cerveau sera sans cesse à hésiter. Faire des maths, ce n'est pas s'interdire des choses, c'est recenser des choses. C'est faire formellement les hypothèses qu'on utilisera ensuite.

Il se trouve que la fonction que je t'ai décrite existe pour des raisons "accidentelles" qui sont que les calculs terminent toujours au bout d'un temps fini à partir de l'application de l'hypothèse faite, ce qui non seulement assure l'unicité de la fonction, mais aussi pour des raisons plus raffinées de fondements, son existence. Or ces derniers points sont systématiquement occultés au point même que tes enseignants, pour une grande part, ne seraient même pas capables de réécrire (pas au cas par cas, mais le principe général).

Brouillon:

[small]$d = u(a-b) + vb = ua + (v-u)b$[/small]

La présentation de l'algo dans le copié-collé plus haut est à ch.er pour moi mais ce n'est qu'un avis personnel.

Ne t'entête pas, je suis sûr que si tu lis doucement et patiemment tu peux comprendre ce que j'ai raconté ci-dessus. Je ne dis pas que TOUT ce que je raconte est compréhensible, mais je pense que si tu n'as compris MON PRESENT propos, c'est bien plus efficace et significatif de te demander ce que tu n'y comprends pas que de faire tourner un exemple simple (ce qui sera stéril en terme d'apport, les gens qui disent que les maths s'apprennent avec des exemples sont ceux qui sachant déjà faire des maths n'ont plus besoin de les apprendre, ils gèrent)

J’ai répondu à la question.

De quel "premier triplet" parles-tu?

Ah pardon, bin c'est le triplet renvoyé par la fonction $f(a,a-b)$!

Un algorithme récursif n'est pas fait pour être exécuté à la main : cela demande en général une mémoire de travail trop grande pour être pratique.

On peut quand même expliquer le principe dans ce cas-ci en numérotant la profondeur de récursion.

On part de $A_0=X^3-2$ et $B_0=2X^2-3$.
Puisque $B_0\neq 0$, on calcule la division euclidienne de $A_0$ par $B_0$ : $A_0=X^3-2=\frac{X}{2}B_0+(\frac{3X}{2}-2)$ et on pose $Q_0=\frac{X}{2}$ et $R_0=\frac{3X}{2}-2$.
On définit alors $D_0$, $U_0$ et $V_0$ comme étant les 3 résultats renvoyés par l'appel de $PGCD(B_0, R_0)$.

On va donc appliquer l'algorithme à nouveau avec $A_1=B_0$ et $B_1=R_0$.
Puisque $B_1\neq 0$, on calcule la division euclidienne de $A_1$ par $B_1$ : $A_1=2X^2-3=\frac{4X}{3}B_1+(\frac{8X}{3}-3)$ et on pose $Q_1=\frac{4X}{3}$ et $R_1=\frac{8X}{3}-3$.
On définit alors $D_1$, $U_1$ et $V_1$ comme étant les 3 résultats renvoyés par l'appel de $PGCD(B_1, R_1)$.

On va donc appliquer l'algorithme à nouveau avec $A_2=B_1$ et $B_2=R_1$.
Puisque $B_2\neq 0$, on calcule la division euclidienne de $A_2$ par $B_2$ : $A_2=\frac{3X}{2}-2=\frac{9}{16}B_2+(\frac{27}{16})$ et on pose $Q_2=\frac{9}{16}$ et $R_2=\frac{27}{16}$.
On définit alors $D_2$, $U_2$ et $V_2$ comme étant les 3 résultats renvoyés par l'appel de $PGCD(B_2, R_2)$.

On va donc appliquer l'algorithme à nouveau avec $A_3=B_2$ et $B_3=R_2$.
Puisque $B_3\neq 0$, on calcule la division euclidienne de $A_3$ par $B_3$ : $A_3=\frac{8X}{3}-3=(\frac{128X}{81}-\frac{48}{27})B_3+0$ et on pose $Q_3=\frac{128X}{81}-\frac{48}{27}$ et $R_3=0$.
On définit alors $D_3$, $U_3$ et $V_3$ comme étant les 3 résultats renvoyés par l'appel de $PGCD(B_3, R_3)$.

On va donc appliquer l'algorithme à nouveau avec $A_4=B_3$ et $B_4=R_3$.
Puisque cette fois-ci $B_4=0$, on calcule le coefficient dominant $\lambda_4=\frac{27}{16}$ de $A_4$.
Ensuite, on renvoie les résultats $D_4=\frac{A_4}{\lambda_4}=1$, $U_4=\frac{1}{\lambda_4}=\frac{16}{27}$ et $V_4=0$.

On revient donc dans l'appel de $PGCD(B_3, R_3)$ et on finit le calcul.
On renvoie donc les résultats $D_3=D_4=1$, $U_3=V_4=0$ et $V_3=U_4-Q_3V_4=\frac{16}{27}$.

On revient donc dans l'appel de $PGCD(B_2, R_2)$ et on finit le calcul.
On renvoie donc les résultats $D_2=D_3=1$, $U_2=V_3=\frac{16}{27}$ et $V_2=U_3-Q_2V_3=-\frac{1}{3}$.

On revient donc dans l'appel de $PGCD(B_1, R_1)$ et on finit le calcul.
On renvoie donc les résultats $D_1=D_2=1$, $U_1=V_2=-\frac{1}{3}$ et $V_1=U_2-Q_1V_2=\frac{4X}{9}+\frac{16}{27}$.

On revient donc dans l'appel de $PGCD(B_0, R_0)$ et on finit le calcul.
On renvoie donc les résultats $D_0=D_1=1$, $U_0=V_1=\frac{4X}{9}+\frac{16}{27}$ et $V_0=U_1-Q_0V_1=-\frac{2X^2}{9}-\frac{8X}{27}-\frac{1}{3}$.

C'est le résultat final.
On peut vérifier à la main que \[U_0A_0+V_0B_0=\left(\frac{4X}{9}+\frac{16}{27}\right) \left(X^3-2\right)+\left(-\frac{2X^2}{9}-\frac{8X}{27}-\frac{1}{3}\right)\left(2X^2-3\right)=1=D_0\]

OS: je pense que tu comprends mais que tu refuses. Tu n'acceptes la simplicité de ce que tu vois.

De mon téléphone

OS: tu veux faire deux choses en même temps. Relis ce que je t'ai raconté et pour peut-être t'aider à un peu plus de recul, dis-moi ce que tu penses de $f$ telle que $\forall x: $

si $x\notin \N$ alors $f(x)=0$
si $x\in \N$ alors $f(x)=1+f(x+1)$

De même avec tes fonctions PGCD : arrête de chercher à comprendre en même temps

- pourquoi ça marche
- ce qu'elles font.

Suppose qu'elles marchent sans te préoccuper de pourquoi (ie suppose qu'elles renvoient un résultat pour toute entrée) et rêve un peu. La question de savoir pourquoi les exécuter aboutit est TOUTE AUTRE.

Je suis convaincu que tu comprends très bien que :

si

$P = BQ + R$ et $D = UQ + VR$

alors

$D = UQ + V(P-BQ) = UQ + VP - VBQ = VP + (U-VB)Q$

Autrement dit que si le père noel te fournit $D,U,V$ pour $(Q,R)$, tu comprends que toi-même, tu récupères $D,V,(U-VB)$ pour $(P,Q)$

mais je n'aurais jamais réussi tout seul.

Ca viendra t'inquiète, si tu prends le gout de rêver (faire des hypothèses (d'existence) s'appelle rêver).