Euclide et compagnie#
Autour de l’algorithme d’Euclide#
Référence possible : Algorithmes Efficaces en Calcul Formel (le tout début du chapitre 6). https://hal.science/AECF/
Pour des détails sur la méthode matricielle dans l’algorithme d’Euclide étendu, vous pouvez aller voir Modern Computer Algebra de Gerhard et von zur Gathen (section 3.2)
Exercice 1. Algorithme de d’Euclide.#
Soient \(A\) et \(B\) deux polynômes non nuls. L’algorithme d’Euclide revient à considérer la suite suivante. On considère la suite définie par \(r_0 = A\) et \(r_1 = B\) et tant que \(r_i\neq 0\), \(r_{i+1}\) est le reste de la division euclidienne de \(r_{i-1}\) par \(r_i\).
Montrer qu’il existe \(N\) tel que \(r_{N+1} = 0\) et \(r_N\neq 0\).
Montrer que \(r_{N} = \mathrm{pgcd}(A,B)\).
Que vaut \(r_2\) si \(\deg(A)<\deg(B)\) ? Comment interpréter la première étape de l’algorithme d’Euclide dans ce cas ?
On suppose dans la suite \(\deg(A)\geq \deg(B)\).
En utlilisant la complexité de la division euclidienne vue en cours, borner la complexité du calcul de \(r_i\).
En déduire que la complexité pour obtenir \(\mathrm{pgcd}(a,b)\) est bornée par \((2 \deg(b)+1)(2\deg(a))\).
Rappel. L’algorithme naif de division euclidienne calcule la division euclidienne de \(A\) par \(B\) en au plus \((2\deg(B)+1)(\deg(A)-\deg(B)+1)\) opérations dans le corps de base.
Exercice 2. Algorithme d’Euclide étendu.#
Soient \(a,b\) deux entiers non nuls. On pose \(a_0 = a\), \(b_0=b\) et tant que \(b_n\neq 0\), \(a_{n+1} = b_n\) et \(b_{n+1} = r_n = a_n-q_n b_n\) où \(a_n = b_n q_n +r_n\) est la division euclidienne de \(a_n\) par \(b_n\). Soit \(N\) tel que \(b_{N+1}=0\) et \(b_N\neq 0\).
Déterminer une matrice à coefficients entiers \(Q_{n+1}\) telle que \(\begin{pmatrix} a_{n+1}\\b_{n+1} \end{pmatrix} = Q_{n+1}\begin{pmatrix} a_{n}\\b_{n} \end{pmatrix}\).
Par récurrence, on obtient une matrice à coefficients entiers \(M_{n+1}\) telle que \(\begin{pmatrix} a_{n+1}\\b_{n+1} \end{pmatrix} = M_{n+1}\begin{pmatrix} a_{0}\\b_{0} \end{pmatrix}\).
Comment obtenir une relation de Bézout à partir de \(M_{N+1}\) ?
Cette façon d’obtenir le pgcd et une rélation de Bézout peut se traduire en un algorithme : l’algorithme d’Euclide étendu.
Implémenter l’algorithme d’Euclide étendu pour les entiers positifs. Illustrer le temps d’exécution de votre fonction. Comparer avec
xgcd. On rappelle que//et%permettent de calculer le quotient et le reste d’une division euclidienne et quetimeitpermet de mesurer des temps d’execution.
Commentaires. Même si c’est n’est pas le plus optimal en nombre d’opérations effectuées, je vous conseille d’utiliser des matrices pour écrire votre code.
Exercice 3#
On considère l’algorithme récursif décrit ci-dessous.
Entrées: deux entiers strictement positifs \(a\) et \(b\).
Sortie: \(R(a,b)\).
si \(a=b\), on renvoie \(a\).
si \(a\) et \(b\) sont pairs, on renvoie \(2R(a/2,b/2)\).
si \(a\) et \(b\) n’ont pas la même parité, on renvoie \(R(a/2,b)\) si \(a\) est pair et \(R(a,b/2)\) si \(b\) est pair.
si \(a\) et \(b\) sont impairs, on renvoie \(R(a,(b-a)/2)\) si \(b>a\) et \(R((a-b)/2,b)\) sinon.
Que calcule cet algorithme ? Justifier.
Implémenter cet algorithme en
sage. Que dire de son temps d’exécution ?
Exercice 4. Nombre de division euclidiennes dans l’algorithme d’Euclide.#
On considère la suite de Fibonacci définie par \(F_0= 0\), \(F_1=1\) et \(F_{n+2} = F_{n+1}+F_n\) pour tout \(n\geq 0\).
Montrer que pour tout \(n>1\), \(F_{n+1}\) et \(F_{n+2}\) sont premiers entre eux que que l’algorithme d’Euclide se termine en \(n\) étapes.
Soient \(a\) et \(b\) deux entiers avec \(0<b<a\). Soit \(d\) le pgcd de \(a\) et \(b\). Montrer que si l’algorithme d’Euclide appliqué à \(a\) et \(b\) termine en \(n\) étapes alors \(a\geq d F_{n+2}\) et \(b\geq dF_{n+1}\).
Montrer que le nombre de divisions euclidiennes pour calculer le pgcd de \(a\) et \(b\) est un \(O(\log(b)\).
Indications.
Dérouler algorithme d’Euclide.
Faire une récurrence.
Estimer la taille de \(F_n\).
Quotients#
Exercice 5. Quotient par une relation d’équivalence.#
Soient \(E\) et \(F\) deux ensembles de \(\mathcal R\) une relation d’équivalence sur \(E\). On note \(\pi : E\to E/\mathcal R\) la projection canonique.
Vérifiez que vous savez bien définir une relation d’équivalence et la projection canonique.
On rappelle que \(f : E\to F\) passe au quotient pour \(\mathcal R\) s’il existe \(\overline{f} : E/\mathcal R \to F\) telle que \(f = \overline{f}\circ \pi\).
Montrer le théorème de factorisation : Soit \(\mathcal R\) une relation d’équivalence sur \(E\) et \(f : E\to F\) alors \(f\) passe quotient si et seulement si pour tous \(x,y\in E\), \(x\mathcal R Y\) implique \(f(x) = f(y)\).
On considère \(A\) un anneau commutatif et \(I\) un idéal de \(A\). On peut définir \(A/I\). Quelle est la relation d’équivalence ici ? Comment les opérations d’anneaux sont-elles définies sur le quotient ? Que devient le théorème de factorisation dans ce contexte ?
Exercice 6#
On note \(\phi\) le nombre d’or. Simplifier la fraction
sans utiliser de formule explicite pour \(\phi\).
Restes chinois#
Exercice 7. Énoncé.#
On rappelle (un énoncé) du théorème des restes choinois. Soit \(A\) un anneau principal et \(m_1,\dots m_n\), des éléments de \(A\) deux à deux premiers entre eux. On note \(m = m_1\cdots m_n\). Alors l’application \(\phi : A \to A/(m_1)\times\dots\times A/(m_n)\) est un morphisme d’anneaux surjectif de noyau \((m)\). L’application induite \(A/(m) \to A/(m_1)\times\dots\times A/(m_n)\) est donc un isomorphisme d’anneaux.
Montrer que si \(A = K[X]\) et les \(m_i\) sont des polynômes de degré \(1\) alors la surjectivité est un problème d’interpolation.
En vous inspirant de la construction d’un polynôme d’interpolation, prouver la surjectivité. (Si vous ne voyez pas comment faire, commencez par le cas \(n=2\) et écrivez une relation de Bézout.)
Pour \(n= 2\) et \(A =\mathbb Z\), comparer la complexité de la méthode naive pour trouver un antécédent (on teste toutes les possibilités) et la complexité de la méthode obtenue grâce à la question précédente.
Exercice 8.#
Écrire une fonction sage qui, à partir de listes d’entiers y et m, renvoie une solution \(x\) du système de congruences
en supposant que les \(m_i\) sont \(2\) à \(2\) premiers entre eux.
Comparer avec crt.
Commentaires. Votre fonction doit s’inspirer de la preuve de la surjectivité de l’exercice précédent.
Exercice 9.#
Soit \(P = X^6+1\) et \(Q = X^6+X^5+X^4+X^3+X^2+X+1\).
Donner deux polynômes de \(\mathbb Q[X]\) de degrés les plus petits possibles qui vérifient simultanément: \(R \equiv X^2 \; [P]\) et \(R \equiv X+1 \;[Q]\).
Décrire explicitement l’inverse du morphisme
Exercice 10.#
Déterminer un polynôme \(P\in \mathbb Q[X]\) de degré au plus \(5\) tel que \(P(0)=1\), \(P'(0)=1\), \(P(1)=1\), \(P'(1)=-1\), \(P(-1)=1\) et \(P'(-1)=0\).
Exercice 11. Idempotents (Bonus)#
Soit \(A\) un anneau commutatif. Un élément \(e\in A\) s’appelle un idempotent si \(e^2 = e\). Deux idempotents \(e,f\in A\) sont dits orthogonaux si \(ef=0\).
Un système complet d’idempotents est une famille \(\{e_1,\dots,e_n\}\) d’idempotents, deux à deux orthogonaux, telle que \(\sum_{i=1}^n e_i = 1\).
Si \(A\) est un anneau isomorphe à un produit d’anneaux \(A_1\times\dots\times A_n\), expliquer comment trouver un système complet d’idempotents de \(A\).
Soit \(K\) un corps, \(x_1,\dots,x_n\in K\) 2 à 2 distincts et \(P=\prod (X-x_i)\). Vérifier que les
forment un système complet d’idempotents maximal de \(K[X]/(P)\). Faire le lien avec l’interpolation de Lagrange.
Trouver un système complet d’idempotents maximal de l’anneau \(\mathbb{Z}/30\mathbb{Z}\).
Exercice 12. Fractions continues (Bonus)#
Pour une suite de réels (le plus souvent entiers) \((a_n)_{n\in\mathbb{N}}\), on définit la fraction continue \([a_0, a_1, . . . , a_n]\) par
Soit \(x\in \mathbb R\). Le développement en fractions continue d’un réel \(x\) est défini par récurrence par \(a_n=\lfloor x_n\rfloor\), \(x_0=x\), et tant que \(x_n\) n’est pas entier, \(x_{n+1}=\frac{1}{x_n-a_n}\) (si \(x_n\) est entier, les deux suites s’arrêtent). On démontre que l’on a alors
Soit \(x\in \mathbb R\).
a.Vérifier que \(x=[a_0,a_1,\dots,a_{p-1},x_p]\) pour tout \(p\) tel que la suite est définie.
b.Vérifier que la suite \((x_n)\) est bien définie pour tout \(n\) si et seulement si \(x\) est irrationnel.
Écrire un programme qui étant donné un nombre (rationnel ou flottant) \(x\), calcule les \(n\) premiers termes de la suite \((a_n)\) ci-dessus, si elle est définie.
Vérifier expérimentalement que \(x=\lim [a_0,\dots,a_n]\) pour une valeur de \(x\) de votre choix.
Donner le développement en fraction continue de \(\sqrt{2}\) et de \(\varphi=\frac{1+\sqrt 5}{2}\). Donner les 20 premiers termes du développement en fraction continue de \(\pi\).
Exercice 13. Fractions continues (Bonus)#
Une approximation d’un nombre \(x\) par un nombre rationnel \(\frac{p}{q}\) est bonne si l’on atteint une erreur \(\varepsilon = |x -\frac{p}{q}|\) petite avec un dénominateur \(q\) qui n’est pas trop grand. Le développement en fraction continue permet d’obtenir les meilleures approximations d’un nombre \(x\) en général. Pour un nombre irrationnel \(x\), soit \(u_n = [a_0, a_1, . . . , a_n] = \frac{p_n}{q_n}\) son \(n\)ème développement en fractions continues. Soit \(C_n = |x - \frac{p_n}{q_n}|q_n^2\).
Écrire un programme qui, étant donné un développement en fraction continue \([a_0, a_1, . . . , a_n]\), calcule le numérateur et le dénominateur de \(u_n\).
Pour le nombre d’or \(x=\phi= \frac{1+\sqrt{5}}{2}\) et pour \(x = \pi\), calculer les premières valeurs de \(u_n, p_n, q_n\) et \(C_n\).
Vérifier expérimentalement le théorème d’approximation de Dirichlet : pour un nombre irrationnel \(x\), il existe une infinité de nombres rationnels \(\frac{p}{q}\), tels que