Euclide et compagnie#

Autour de l’algorithme d’Euclide#

1.#

Implémenter l’algorithme d’Euclide pour les entiers positifs. Illustrer le temps d’exécution de votre fonction. Comparer avec gcd. 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.

2#

  1. Écrire l’algorithme d’Euclide étendu pour les entiers positifs. La commande xgcd permet de calculer une relation de Bézout avec sage, vous pourrez l’utiliser dans la suite du TP.

  2. Écrire une procédure inverse_mod(a,m) permettant de calculer l’inverse d’un entier \(a\) premier avec un entier \(m\geq 2\) donné. Si \(a\) n’est pas premier avec \(m\), on utilisera la commande

raise ValueError("Le nombre \{\} n'est pas inversible modulo \{\}".format(a,m))

où la méthode format appliquée à une chaîne de caractères remplace les \{\} par la valeur des expressions données comme arguments (ici $a$ et $m$). Comparer la réponse à la commande inverse_mod(2,4) avec la réponse habituelle de sage en cas d'erreur.

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\) n’ont pas la m^eme parit’e, 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 ?

4#

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

Anneaux \(\mathbb Z/n\mathbb Z \)#

5#

  1. Écrire une fonction fermat(p) qui vérifie le petit théorème de Fermat : « si \(p\) est premier alors \(a^p\equiv a\,(\mathrm{mod}\, p)\) pour tout entier \(a\) » pour un nombre premier \(p\) donné.

  2. Vérifier le théorème pour les premiers \(p\leq 11\).

  3. Le nombre \(561\) est-il premier? A-t-on \(a^{561}\equiv a\,(\mathrm{mod}\, 561)\) pour tout entier \(a\) ? Que peut-on en conclure ?

6#

Le groupe \(\left(\mathbb Z/n\mathbb Z\right)^\times\) est-il toujours cyclique ? On sait que le groupe \(\left(\mathbb Z/p\mathbb Z\right)^\times\) est cyclique pour \(p\) premier. Illustrer cette propriété avec sage et développer (par exemple, en déterminant tous les générateurs et en expliquant comment ils se déduisent les uns des autres).

Restes chinois#

7#

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

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

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

8#

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

9#

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

10#

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\) 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. Ecrire un programme qui étant donné un nombre premier \(p\) et \(n\) éléments distincts \((x_1,...,x_n)\) de \(\mathbb{F_p}\) renvoie un système complet d’idempotents maximal \(e_1,\dots,e_n\) de

    \[\frac{\mathbb{F}_p[X]}{\prod_{i=1}^n(X-x_i)}\]

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