Nombres relatifs
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 :
"""Représente un entier relatif comme un couple `(a,b)`
d’entiers naturels positifs."""
"""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 :
= ,
"""Retourne une chaîne représentant l’entier `Z(a,b)`."""
=
, return
"""Teste si l’objet courant est égal à l’objet `m`
en supposant que `m` est de la classe `Z`."""
=
, =
, return + == +
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
- Vérifiez que tout élément de $\mathbf Z$ est de la forme $[(n,0)]$ ou $[(0,n)]$, qu’on appelle forme canonique.
- Ajoutez une méthode
canonique()
à la classeZ
qui renvoie sa forme canonique : par exempleZ(13,22).canonique()
renvoieZ(0,9)
. - Vérifiez que l’application $ι : n\in \mathbf N\mapsto [(n,0)] \in \mathbf Z $ est injective.
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
:
"""Si `a` et `b` sont des entiers naturels positifs, construit le
relatif représenté par le couple `(a,b)`.
Si on ne donne que l’argument `a`, construit l’entier `Z(a,0)`."""
# On ne veut que des entiers positifs :
= ,
- Définissez une addition sur $\mathbf Z$ munissant $\mathbf Z$ d’une structure de groupe abélien, et telle que $ι(m+n)=ι(m)+ι(n)$ ($ι$ est un morphisme de monoïdes). En particulier, elle admet un élément neutre $0_{\mathbf Z}$ (quel est-il?).
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.
- Quel est l’opposé (l’inverse additif) de $[(n,m)]$?
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)
.
- Ajoutez une méthode
__neg__()
à la classeZ
pour que-Z(a,b)
retourne l’opposé deZ(a,b)
. Déduisez-en une méthode__sub__()
. - Définissez une multiplication sur $\mathbf Z$ enrichissant la structure additive de $\mathbf Z$ en une structure d’anneau commutatif, et telle que $ι(m×n)=ι(m)×ι(n)$ ($ι$ est un morphisme de semi-anneaux).
Encore une fois, en Python, on peut surcharger l’opérateur *
en définissant
la méthode __mul__()
:
a * b == a.__mul__(b)
.
- Quels sont les éléments inversibles (pour $×$) de $\mathbf Z$ ?
- Comment définir l’ordre usuel sur $\mathbf Z$ ? et la valeur absolue ?
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__()
.
- Définissez les méthodes précédentes pour la classe
Z
(vous pouvez faire le calcul pour une seule de ces méthodes, et en déduire les autres).
Vu que les entiers de Python sont déjà une représentation des entiers relatifs, le travail précédent est assez inutile (en tout cas en dehors d’un cours sur la construction des entiers relatifs…).
D’ailleurs il est facile d’ajouter
une méthode __int__()
qui réalise la bijection de Z
vers int
:
on a par exemple int(Z(3,5)) == -2
.
- Définissez cette méthode.
À partir de ce point, on se contentera des entiers Python.
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
- Modifiez votre programme de division euclidienne (initialement conçu pour
$\mathbf N$) pour qu’il soit aussi correct sur $\mathbf Z$
(représenté par le type
int
).
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
- Vérifiez l’affirmation précédente.
- Si $n\in\mathbf{N}$, comment calculer l’écriture de $-n$ à partir de celle de $n$ ?
- Modifiez vos programmes
representation()
etvaleur()
pour querepresentation(a,B)
retourne un couple(b,c)
avecb == (a<0)
etc
une liste de coefficients (entiers naturels de typeint
) calculés comme ci-dessus, etvaleur(b,c,B)
calcule la valeur représentée par le bitb
et la liste de coefficientsc
(vous pouvez le faire en supposant quea
est de typeint
ouZ
; même chose pour la valeur de retour devaleur()
). - Étant donnés deux nombres écrits en base
B
, comment calculer une écriture de leur somme ?
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 s’il n’est pas inversible, et 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
- Vérifiez que tout couple $(a,b)$ d’entiers admet un unique PGCD positif ou nul, qu’on note $a\wedge b$, et que les PGCD de $a$ et $b$ sont $a\wedge b$ et $-a\wedge b$.
- Réalisez cette construction en Python.