Euclide et compagnie

Euclide et compagnie#

Autour de l’algorithme d’Euclide#

Exercice 1.#

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 que timeit permet de mesurer des temps d’execution.

Exercice 2#

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\) 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.

    1. Que calcule cet algorithme ? Justifier.

    2. Implémenter cet algorithme en sage. Que dire de son temps d’exécution ?

Exercice 3#

On note \(\phi\) le nombre d’or. Simplifier la fraction

\[\frac{\phi^4-\phi+1}{\phi^7-1}\]

sans utiliser de formule explicite pour \(\phi\).

Restes chinois#

Exercice 4.#

Écrire une fonction sage qui, à partir de listes d’entiers y et m, renvoie une solution \(x\) du système de congruences

\[x\equiv y_i\,(\mathrm{mod}\, m_i)\,,\,\, 1\leq i\leq r\,.\]

en supposant que les \(m_i\) sont \(2\) à \(2\) premiers entre eux.

Comparer avec ctr.

Exercice 5.#

Soit \(P = X^6+1\) et \(Q = X^6+X^5+X^4+X^3+X^2+X+1\).

  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]\).

  2. Décrire explicitement l’inverse du morphisme

\[\mathbb Q[X]/(PQ)\to\mathbb Q[X]/(P)\times\mathbb Q[X]/(Q).\]

Exercice 6.#

Déterminer un polynôme \(P\in \mathbb Q[X]\) de degré au plus \(3\) tel que \(P(0)=1\), \(P'(0)=1\), \(P(1)=1\), \(P'(1)=-1\), \(P(-1)=1\) et \(P'(-1)=0\).

Exercice 7. 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\).

  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\).

  2. Soit \(K\) un corps, \(x_1,\dots,x_n\in K\) 2 à 2 distincts et \(P=\prod (X-x_i)\). Vérifier que les

\[e_i = \prod_{i\ne j} \frac{X-x_j}{x_i-x_j} \]

forment un système complet d’idempotents maximal de \(K[X]/(P)\). Faire le lien avec l’interpolation de Lagrange.

  1. Trouver un système complet d’idempotents maximal de l’anneau \(\mathbb{Z}/30\mathbb{Z}\).

Exercice 8. 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

\[ [a_0, a_1, . . . , a_n] = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{\ddots {+\cfrac{1}{a_n}}}}} \]

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

\[ x = \lim_{n\rightarrow +\infty} [a_0,a_1,\dots,a_n] \]

  1. 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.

  2. É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.

  3. Vérifier expérimentalement que \(x=\lim [a_0,\dots,a_n]\) pour une valeur de \(x\) de votre choix.

  4. 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 9. 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\).

  1. É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\).

  2. 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\).

  3. 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

\[ \left| x - \frac{p}{q} \right| \leq \frac{1}{q^2} \]
Contenu