S5, L3 Maths (MA) – Lionel Vaux Auclair

Nombres relatifs

Cours (Série)
Mise en route
Arithmétique
Nombres relatifs
Anneaux des entiers modulo
Algèbres de polynômes
Corps finis

On construit les relatifs comme quotient des naturels.

Quotients

Une relation d’équivalence sur l’ensemble $X$, c’est une relation binaire $R \subseteq X\times X$ réflexive, symétrique et transitive. On note $[x]_R$ ou simplement $[x]$ la classe d’équivalence de $x\in X$ pour $R$: $[x]=\{ y \in X \mid x \mathrel R y \}$. Le quotient $X/R$ est l’ensemble des classes d’équivalence. La fonction $π_R : x\in X \mapsto [x]\in X/R $ est la surjection canonique dont la propriété essentielle est le :

Théorème de factorisation. Pour toute application $f:X\to Y$ telle que $x\mathrel R y$ implique $f(x)=f(y)$, il existe une unique application $g:X/R\to Y$ telle que $g(\bar x)=f(x)$ pour tout $x\in X$ (c’est-à-dire $f = g\circ π_R$). Par ailleurs, $g$ est injective ssi $x\mathrel R y \iff f(x)=f(y)$.

Autrement dit, définir une fonction sur $X/R$ revient à donner une fonction définie sur $X$ et compatible avec la relation $R$.

Construction des entiers relatifs

On rappelle que pour $m,n\in\mathbf N$, on a $m\le n$ ssi il existe $p\in \mathbf N$ tel que $n=p+m$. Dans ce cas, $p$ est défini de manière unique et on note $p=n-m$, de sorte que $(n-m)+m=n$.

Pour que la soustraction $n-m$ soit toujours définie, on voudrait que l’addition sur les entiers définisse une loi de groupe, c’est-à-dire que chaque entier $m$ admette un opposé, de sorte que $n-m=n+(-m)$ pour tout entier $n$. Dans $\mathbf N$, seul $0$ a un opposé: on va donc étendre le monoïde $\mathbf N$ en le groupe $\mathbf Z$ librement engendré par $\mathbf N$.

Pour construire $\mathbf Z$, l’idée est de considérer les « différences formelles » : on se donne $n-m$ pour tous $n,m\in\mathbf N$, modulo l’égalité attendue, c’est-à-dire $n-m=n'-m'$ quand $n+m'=m+n$. Formellement, on pose $\mathbf Z=\mathbf N^2/D$ avec $(n,m)\mathrel D (n',m')$ ssi $n+m'=n'+m$.

On va refléter cette construction en Python en créant une classe Z comme suit :

class Z:
    """Représente un entier relatif comme un couple `(a,b)` 
    d’entiers naturels positifs."""
    
    def __init__(self,a,b):
        """Si `a` et `b` sont des entiers naturels positifs, construit le
        relatif représenté par le couple `(a,b)`."""
        # On ne veut que des entiers positifs :
        if not(isinstance(a,int) and isinstance(b,int) and a >= 0 and b >= 0):
            raise ValueError("Z() attend deux entiers positifs")
        self.couple = a, b
    
    def __repr__(self):
        """Retourne une chaîne représentant l’entier `Z(a,b)`."""
        a, b  = self.couple
        return "Z({0},{1})".format(a,b)
    
    def __eq__(self,m):
        """Teste si l’objet courant est égal à l’objet `m`
        en supposant que `m` est de la classe `Z`."""
        a0, b0  = self.couple
        a1, b1  = m.couple
        return a0 + b1 == a1 + b0

La méthode __init__() est appelée chaque fois qu’on crée une instance : Z(0,1) renvoie un objet de la classe Z dont l’attribut couple est le couple (0,1); et Z(1.1,0) et Z(-1,0) soulèvent l’exception ValueError parce que 1.1 n’est pas un int, et -1<0.

La méthode __repr__() est utilisée par Python chaque fois qu’on veut afficher la valeur d’un objet (par exemple avec print() ou bien dans le mode interactif. Voir la documentation.

Enfin, la méthode __eq__() est utilisée pour le test d’égalité ==: la valeur du test a == b est la valeur de retour de a.__eq__(b). Voir la documentation.

Exercices

On peut donc considérer que $\mathbf{N}\subseteq\mathbf{Z}$ à cette injection près. On modifie la méthode __init__() de Z pour accepter un unique argument a :

    def __init__(self,a,b=None):
        """Si `a` et `b` sont des entiers naturels positifs, construit le
        relatif représenté par le couple `(a,b)`.
        Si on ne done que l’argument `a`, construit l’entier `Z(a,0)`."""
        if b is None:
            # Réalise l’injection `n↦[(n,0)]` :
            self.__init__(a,0)
            return
        # On ne veut que des entiers positifs :
        if not(isinstance(a,int) and isinstance(b,int) and a >= 0 and b >= 0):
            raise ValueError("Z() attend deux entiers positifs")
        self.couple = a, b

En Python, on peut surcharger l’opérateur + en définissant la méthode __add__() des opérandes : plus précisément, la valeur de l’expression a + b est la valeur retournée par a.__add__(b).

Ajoutez une méthode __add__() à la classe Z pour que Z(a,b)+Z(c,d) retourne la somme définie précédemment.

En Python, on peut aussi surcharger l’opérateur - en définissant les méthodes __neg__() et __sub__(): plus précisément, la valeur de l’expression -a est la valeur retournée par a.__neg__(), et la valeur de a-b est la valeur de a.__sub__(b).

Encore une fois, en Python, on peut surcharger l’opérateur * en définissant la méthode __mul__(): a * b == a.__mul__(b).

Comme pour les opérations, on peut surcharger les opérateurs de comparaison : a < b == a.__lt__(b), a <= b == a.__le__(b), a > b == a.__gt__(b), a >= b == a.__ge__(b). Et pour la valeur absolue, abs(a) == a.__abs__().

Division euclidienne

On a toujours une division euclidienne: pour tous $a\in\mathbf Z$ et $b\in\mathbf Z^\bullet=\mathbf Z\setminus\{0\}$, il existe un unique couple $(q,r)$ d’entiers tels que $a = qb+r$ et $0\le r\lt |b|$ (en particulier $r\in\mathbf N$).

Exercice

Signe et représentation en base quelconque

Tout entier $k\in\mathbf{Z}$ peut s’écrire sous la forme $(-1)^b|k|$ avec $b\in\mathbf{B}=\{0,1\}$ et $|k|\in\mathbf{N}$. La valeur absolue $|k|$ est définie de manière unique par cette propriété. L’application $(b,n)\mapsto (-1)^bn$ est donc une surjection $\mathbf{B}×\mathbf{N}\to\mathbf{Z}$; mais ce n’est pas une injection, car $0=-1×0$. Autrement dit, ce codage n’est pas univoque: le signe de $0$ n’est pas bien défini.

Par contre, on a bien une bijection: \[ \begin{array}{rcl} \mathbf{B}×\mathbf{N}&\to&\mathbf{Z}\\ (b,n) &\mapsto & (-1)^b(n+b) \end{array} \] de réciproque: \[ \begin{array}{rcl} \mathbf{Z} &\to &\mathbf{B}×\mathbf{N}\\ k &\mapsto & (ε(n),|k|-ε(n)) \end{array} \] où $ε(n)=0$ si $n\ge 0$ et $ε(n)=1$ si $n<0$.

Si on fixe $B>1$, alors tout entier $n\in\mathbf{Z}$ tel que $-B^k\le n<B^k$ admet une unique écriture sous la forme \[ n = -ε(n)B^k+ \sum_{i=0}^{k-1} c_i B^i \] avec $ 0\le c_i < B $ pour $ 0\le i< k-1$.

Exercices

Divisibilité, primalité, …

La divisibilité est définie à partir de la multiplication comme sur $\mathbf{N}$. Mais la suite de l’histoire n’est pas la même…

Par exemple, il y a deux éléments minimaux pour la divisibilité: les inversibles $-1$ et $1$. Et les nombres premiers ont maintenant quatre diviseurs: tout nombre $n\in\mathbf{Z}$ est divisible par $1$, $-1$, $n$ et $-n$… Plutôt que de définir les nombres premiers par cette propriété un peu arbitraire, on donne la définition plus générique:

Un nombre $n\in\mathbf{Z}$ est dit premier si pour toute écriture de $n$ comme un produit $ab=n$, au moins un des facteurs, $a$ ou $b$, est inversible.

La décomposition d’un nombre en facteurs premiers existe toujours, mais elle n’est plus unique ! Par exemple, $3×(-2)=(-3)×2$.

De la même manière, au sens de l’ordre de divisibilité, on a en général deux PGCD (et deux PPCM): en pratique, on considère celui des deux qui est positif.

Exercices

Série: Cours
Mise en route
Arithmétique
Nombres relatifs
Anneaux des entiers modulo
Algèbres de polynômes
Corps finis
Sommaire
Quotients
Construction des entiers relatifs
- Exercices
Division euclidienne
- Exercice
Signe et représentation en base quelconque
- Exercices
Divisibilité, primalité, …
- Exercices