ALGORITHMES AVANC ÉS POUR L'ARITHMÉTIQUE

1 - Sur les structures algébriques en général

a) ?

?

def ?

b) ?

?

def ?
?


2 - Divisions euclidiennes

a) Algorithme d'Euclide étendu dans \(\mathbf{Z}\)

?

def ?

b) Un autre exemple de division euclidienne : les entiers de Gauss

Ils forment l'ensemble \(\mathbf{Z}[i]\) des nombres complexes dont la partie réelle et la partie imaginaire sont des entiers. Muni des opérations \(+\) et \(\times\), cet ensemble possède une structure d'anneau. À chaque élément \(z = a + bi\) de \(\mathbf{Z}[i]\) on associe sa norme (rien à voir avec la topologie) \[ \mathrm{N}(z) = z \times \overline{z} = a^2 + b^2 \in \mathbf{Z}, \] dont on va voir immédiatement quelques

Propriétés.

i) La norme est multiplicative, c'est-à-dire pour tous \(z\) et \(z'\) dans \(\mathbf{Z}[i]\) on a \(\mathrm{N}(z \times z') = \mathrm{N}(z) \times \mathrm{N}(z')\).
ii) En particulier, \(z\) est inversible dans l'anneau \(\mathbf{Z}[i]\) si et seulement si sa norme est égale à \(1\).
iii) Le groupe des inversibles de \(\mathbf{Z}[i]\) est \(\mathbf{Z}[i]^\times = \left\{1\,;\,-1\,;\,i\,;\,-i\right\} = \mathbf{U}_4\).



Parlons un peu de factorisation. On dit qu'un élément \(z\) de \(\mathbf{Z}[i]\) est premier s'il n'est pas inversible et si pour toute factorisation \(z = x \times y\), on a \(x\) ou \(y\) inversible.

Propriétés.

i) Si \(\mathrm{N}(z)\) est un nombre premier (dans \(\mathbf{Z}\)), alors \(z\) est premier (dans \(\mathbf{Z}[i]\)).
ii) La réciproque est fausse : par exemple, \(z = 2 + i\) est premier mais sa norme vaut \(\mathrm{N}(z) = 9\).
iii) Un entier (dans \(\mathbf{Z}\)) est premier (dans \(\mathbf{Z}[i]\)) si et seulement s'il est premier (dans \(\mathbf{Z}\)) et congru à (\(2\) ou) \(3\) modulo \(4\).
iv) Un entier de Gauss est premier si et seulement si sa norme est un nombre premier (dans \(\mathbf{Z}\)) congru à (\(2\) ou) \(3\) modulo \(4\).



Soit \(\mathrm{A}\) un anneau. Un stathme est une application \(\mathrm{J} : \mathrm{A} - \left\{0\right\} \rightarrow \left[0\,;\,+\infty\right[\) telle que pour tous \(x\) et \(y\) dans \(\mathrm{A}\), avec \(y \neq 0\), il existe au moins un couple \((q, r)\) d'éléments de \(\mathrm{A}\) tel que \[ x = qy + r \quad\text{et (si $r$ est non nul)}\quad \mathrm{J}(r) < \mathrm{J}(y). \] Un anneau muni d'un stathme est dit euclidien, et les deux exemples les plus célèbres sont \(\mathbf{Z}\) (le stathme est la valeur absolue) et \(\mathbf{K}[\mathrm{X}]\) (le stathme est le degré).

Théorème (division euclidienne chez les entiers de Gauss).

i) La valeur absolue (ou la norme) constitue un stathme sur \(\mathbf{Z}[i]\) : une division euclidienne possible de \(x\) par \(y\) consiste à prendre pour quotient l'élément de \(\mathbf{Z}[i]\) le plus proche, dans \(\mathbf{C}\), de \(x/y\).
ii) Comme tous les anneaux euclidiens, \(\mathbf{Z}[i]\) est un anneau principal : quel que soit l'idéal \(\mathscr{I}\) qu'on considère, il est de la forme \[ \mathscr{I} = \left\langle x \right\rangle \overset{\text{déf.}}{=} \left\{ z \times x \;\middle|\; z \in \mathbf{Z}[i] \right\}, \] c'est-à-dire engendré par un seul élément.
iii) Comme dans tous les anneaux euclidiens, le théorème de Bézout est vrai dans \(\mathbf{Z}[i]\) : deux éléments \(x\) et \(y\) y sont premiers entre eux (i.e. ont pour seuls facteurs communs des éléments inversibles) si et seulement s'il existe deux entiers de Gauss \(u\) et \(v\) tels que \(xu + yv = 1\).
iv) Comme tous les anneaux euclidiens, \(\mathbf{Z}[i]\) est un anneau factoriel : tout élément (autre que zéro) s'écrit sous la forme d'un produit d'éléments premiers \[ z = \prod_{i = 1}^r p_i, \] et cette écriture est unique au sens suivant : si une deuxième telle écriture de \(z\) existe, alors elle possède le même nombre de facteurs, et les éléments premiers \(q_j\) qui y interviennent sont, à l'ordre près, de la forme \(u \times p_i\) avec \(u\) un élément inversible.



def ?
?


3 - Nombres premiers

a) ?

?

def ?

b) ?

?

def ?
?


4 - Problèmes de factorisation

a) ?

?

def ?

b) ?

?

def ?
?