L'arithmétique est l'étude des nombres entiers $${\mathbb N}=\{0,1,2,3,4,\ldots\}$$ $${\mathbb Z}=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$$
La propriété fondamentale est la division euclidienne : Étant donnés deux entiers $a\in{\mathbb Z}$ et $b>0$, il existe un unique couple d'entiers $(q,r)$ (quotient et reste) tel que $$a =bq+r\quad {\rm avec}\ 0\le r<b.$$
Lorsque le reste $r$ est nul, on dit que $b$ divise $a$ ou que $a$ est multiple de $b$, et on écrit $b|a$.
Un entier $>1$ qui n'a pas de diviseurs non-triviaux, c'est à dire autres que 1 et lui-même est dit premier. Par exemple, $2,3,5,7,11,13,17,19,23$ sont premiers.
Le p.g.c.d. de deux entiers $a$ et $b$ est le plus grand entier positif qui divise à la fois $a$ et $b$. On le note $d=a\wedge b$. Par exemple $(-12)\wedge 18=6$.
Le plus petit entier positif divisible à la fois par $a$ et $b$ est appelé p.p.c.m. de $a$ et $b$. On le note $m=a\vee b$. On a $$a\vee b=\frac{ab}{a\wedge b}$$
Pour calculer $a\wedge b$, (avec $a\ge b$) on écrit la division euclidienne $a=bq+r$. Alors $r=a-bq$ est divisible par tout entier divisant à la fois $a$ et $b$ donc par le p.g.c.d. de $a$ et $b$, et tout entier divisant $r$ et $b$ divise aussi $a$. Donc, $$a\wedge b = b\wedge r$$ Comme $r<b$, $(b,r)<(a,b)$ et on itère le procédé jusqu'à arriver à un reste nul. Alors, $d\wedge 0=d$ et on a fini.
# division euclidienne : q=a//b, r=a%b
print("Pour a=27, b=5, q=%d, r=%d" % (27//5, 27%5))
print("Pour a=-27, b=5, q=%d, r=%d" % (-27//5, -27%5))
# pgcd récursif
def gcd(a,b):
if b==0: return a
return gcd(b,a%b)
gcd(192,36)
gcd(36,192)
gcd(-36,192)
gcd(192,-36)
On voit qu'il faut faire attention aux signes. On évitera aussi la récursivité, car on va travailler sur des entiers très longs.
def gcd(a,b):
a,b = abs(a), abs(b) # valeur absolue
r = a%b
while r:
a,b=b,r
r = a%b
return b
Dans la version itérative, on calcule donc une suite de quotients et de restes qu'il est commode de numéroter ainsi. On pose $a_{-1}=a$, $a_0=b$, $q_0=q$, $a_1=r$, et les itérations calculent $$a_{-1}=a_0q_0+a_1$$ $$a_0=a_1q_1+a_2$$ $$\cdots=\cdots$$ $$a_{k-1}=a_kq_k+a_{k+1}$$ et si le premier reste nul est $a_{k+1}$, alors le p.g.c.d. est $d=a_k$.
Ceci implique qu'à chaque étape, on peut calculer des entiers $u_i,v_i$ tels que $a_i=u_ia+v_ib$ En effet, au départ, $a_{-1}=1a+0b$, $a_0=0a+1b$, et par récurrence, comme $a_{i-2}=a_{i-1}q_{i-1}+a_i$, on peut écrire $$a_i = (u_{i-2}a+v_{i-2}b) - q_{i-1}(u_{i-1}a+v_{i-1}b) = (u_{i-2}-q_{i-1}u_{i-1})a+(v_{i-2}-q_{i-1}v_{i-1})b$$ de sorte que $$u_i = u_{i-2}-q_{i-1}u_{i-1}$$ $$v_i = v_{i-2}-q_{i-1}v_{i-1}$$ Les deux suites $u_i$ et $v_i$ vérifient la même récurrence d'ordre 2, avec des conditions initiales différentes $${u_{-1}\choose v_{-1}}={1\choose 0}$$ $${u_0\choose v_0}={0\choose 1}$$
Si le p.g.c.d. est $a_k$, on aura donc $d=u_ka+v_kb$.
Cette propriété, connue sous le nom de théorème de Bézout, sera très importante dans la suite :
Si $a\wedge b=d$, il existe deux entiers $u$ et $v$ tels que $d=ua+vb$, et l'agorithme ci-dessus, appelé algorithme d'Euclide étendu, permet de les calculer.
Voir ici pour des explications complémentaires.
On programmera cet algorithme en TD. Voilà à quoi devrait ressembler le résultat (le fichier ent3.py sera fourni au TD suivant).
from ent3 import *
xgcd(36,196)
11*36-2*196
xgcd(1234567891011121314151617181455221577849202122232425,32323255555555555555555514793232323232323232)
On dit que $a$ est congru à $b$ modulo $n$ si $a$ et $b$ ont même reste dans la division par $n$, ou encore si $a-b$ est divisible par $n$.
On écrit $a\equiv b \mod n$ ou $a\equiv b [n]$.
En python, le test est a%n == b%n.
La congruence modulo $n$ est une relation d'équivalence. On peut manipuler les congruences comme des égalités (d'où la notation), car $a\equiv b [n]$ et $a'\equiv b' [n]$ entraîne $a+a'\equiv b+b' [n]$, $aa'\equiv bb' [n]$, etc.
D'où l'idée d'introduire des symboles $\bar a$ ($a\in{\mathbb Z}$) qui vérifient $$\bar a = \bar b\ \Leftrightarrow \ a\equiv b [n]$$
L'addition et la multiplication modulo $n$ possèdent clairement les mêmes propriétés d'associativité et de ditributivité que leurs versions usuelles. On dit que l'ensemble $${\mathbb Z}/n{\mathbb Z}=\{\bar 0,\bar 1, \ldots,\overline{n-1}\},$$ muni de ces opérations, est un anneau commutatif unitaire.
Voici la table d'addition modulo 12, familière grâce aux horloges à cadran.
def tabadd(n):
print(' + |', end=' ')
for y in range(n):
print ("%2d "% (y % n),end=' ')
print()
print('-'*(4*n+3))
for x in range(n):
print('%2d |'%x, end= ' ')
for y in range(n):
print ("%2d "% ((x+y) % n),end=' ')
print()
tabadd(12)
La table de multiplication est peut-être moins familière. Elle possède quelques propriétés étranges.
def tabmul(n):
print(' * |', end=' ')
for y in range(1,n):
print ("%2d "% (y % n),end=' ')
print()
print('-'*(4*n-1))
for x in range(1,n):
print('%2d |'%x, end= ' ')
for y in range(1,n):
print ("%2d "% ((x*y) % n),end=' ')
print()
tabmul(12)
On constate qu'à la différence de la table d'addition, toutes les lignes ou colonnes ne sont pas des permutations les unes des autres. Dans la table d'addition, chaque ligne contient l'élément neutre 0, $({\mathbb Z}/n{\mathbb Z},+)$ est un groupe.
Par contre, modulo 12, certains éléments n'ont pas d'inverse, et sont des diviseurs de zéro. Par exemple, 2 n'a pas d'inverse, et $\bar 2\times \bar 6 = \bar 0$.
En fait, un diviseur de 0 ne peut jamais être inversible : si on suppose $ab=0$ et $a'a=1$, alors $a'ab=(a'a)b=(1)b=b$ par associativité, et d'un autre côté, $a'ab = a'(ab)=a'0=0$. Donc $b=0$, et $a$ n'est pas un diviseur de 0.
Un corps est un anneau dans lequel tout élément non nul est inversible. Par exemple, ${\mathbb R}$ est un corps, mais ${\mathbb Z}$ n'en est pas un, car par exemple, 2 n'est pas inversible ($\frac12$ n'est pas un entier).
Un anneau unitaire fini sans diviseurs de 0 est toujours un corps : si $a_1=1,\ldots, a_n$ sont ses éléments non nuls, multiplions les tous par l'un d'entre eux $a_i$. Alors, les $n$ éléments $a_1a_i,\ldots,a_na_i$ sont tous différents, car si on avait $a_ja_i=a_ka_i$, on aurait aussi $(a_j-a_k)a_i=0$ et donc des divseurs de zéro. Donc, l'un de ces éléments est égal à 1, et $a_i$ possède donc un inverse.
Dans ${\mathbb Z}/n{\mathbb Z}$, un élément $\bar a$ est inversible si et seulement si $a\wedge n=1$. En effet, si $a$ et $n$ ont un diviseur commun non trivial $d$, $a=da'$, $n=dn'$, alors $\bar a\bar n'=\bar 0$, bien que $\bar a$ et $\bar n'$ soient non nuls.
Inversement, si $a$ est premier avec $n$, $d=a\wedge n=1$, et le théorème de Bézout nous fournit $u$ et $v$ tels que $1=au+vn$. Donc, dans ${\mathbb Z}/n{\mathbb Z}$, $\bar 1 = \bar a\bar u$, et $\bar a$ est inversible.
Le théorème de Bézout fournit donc aussi un algorithme pour calculer les inverses.
def inversemod(x,n):
d,u,v = xgcd(x,n)
if d!=1: raise Exception('Element non inversible')
return u if u>0 else n+u
inversemod(5,12)
inversemod(6,12)
# On va devoir calculer modulo de grands nombres premiers
p = 2**607-1
p
inversemod(111111111111111111111111111111111111,p)
(_*111111111111111111111111111111111111)%p
On vient donc de démontrer :
"Lorsque $p$ est un nombre premier, ${\mathbb Z}/p{\mathbb Z}$ est un corps."
Cette propriété est fondamentale. Tout ce qu'on apprend en premier cycle sur les polynômes ou les matrices reste vrai pourvu que les coefficients soient pris dans un corps. L'existence de corps finis tels que les ${\mathbb Z}/p{\mathbb Z}$ permet d'utiliser ces notions en cryptographie ou pour la construction de codes correcteurs d'erreurs.
Il est donc important d'étudier les nombres premiers, et en particulier d'être capable de les reconnaître. L'observation suivante sera fondamentale pour la suite.
Rappelons la formule du binôme de Newton $$(x+y)^n = \sum_{k=0}^n{n\choose k}x^{n-k}y^k,\quad {n\choose k}=\frac{n!}{k!(n-k)!}=\frac{n(n-1)\cdots(n-k+1)}{1\cdot 2\cdots k}$$
Regardons le triangle de Pascal modulo divers entiers.
def binomial(n,k):
if n<k: return 0
if k==0: return 1
return binomial(n-1,k-1)+binomial(n-1,k)
def triangle(n,r):
for m in range(n+1):
print ("%2d" % m, end = ' ')
for k in range(m+1):
print ("%3d" % (binomial(m,k) % r),end = ' ')
print()
# Modulo 2
triangle(15,2)
# Modulo 3
triangle(15,3)
# Modulo 4
triangle(15,4)
# Modulo 5
triangle(15,5)
On observe que lorsque $n$ est premier, apparemment, tous les ${n\choose k}$ sont divisbles par $n$, sauf le premier et le dernier qui valent toujours 1. De fait, la formule avec les factorielles montre que ce nombre, qui est un entier, est le résultat de la simplification d'une fraction dont le numérateur est divisible par $n$, mais pas le dénominateur si on suppose que $n$ est premier. Donc le résultat est divisible par $n$.
Pour $p$ premier, la formule du binôme dans ${\mathbb Z}/p{\mathbb Z}$ devient ainsi $$(\bar x + \bar y)^p = \bar x^p + \bar y^p.$$ On peut itérer : $(\bar x + \bar y+ \bar z)^p = \bar x^p + (\bar y+\bar z)^p$, etc., de sorte qu'en écrivant un entier quelconque $a=1+1+\cdots+1$ ($a$ fois), on a $$\bar a^p = (\bar 1 +\bar 1 + \cdots + \bar 1)^p = \bar 1^p + \bar 1^p + \cdots+\bar 1^p = \bar 1 +\bar 1 + \cdots + \bar 1=\bar a$$
Ainsi, tout élément de ${\mathbb Z}/p{\mathbb Z}$ vérifie $$\bar a^p=\bar a$$ et s'il est inversible, $$\bar a^{p-1}=\bar 1.$$
Cet énoncé constitue le petit théorème de Fermat, qu'on énonce habituellement avec des congruences :
"Si $p$ est premier, tout entier $a$ vérifie $a^p\equiv a\mod p$, et si de plus $a$ est premier avec $p$, alors $a^{p-1}\equiv 1\mod p$."
# Par exemple, 2^607-1 est premier
p
# On écrira une fonction powermod(a,m,p) qui calcule a**m % p
powermod(42,p-1,p)
# Celui ci n'est pas premier
n = 2**647-1
n
# Ce calcule le prouve
powermod(3,n-1,n)
La fonction powermod calcule efficacement $a^m\mod n$ par le procédé suivant (voir ici). On écrit (en pensée) l'exposant $m$ en binaire $m=b_k\cdots b_1b_0$. Les bits $b_i$ sont calculés
au fur est à mesure. Au départ, le résultat intermédiare
res est 1. On calcule $b_0=m\mod 2$. Si $b_0=1$ on multiplie res par $a$ modulo $n$. On divise $m$ par 2, on remplace
$a$ par $a^2\mod n$, et on recommence. Ceci calcule
$$\bar a^m = (\bar a)^{b_0}(\bar a^2)^{b_1})(\bar a^{(2^2)})^{b_2}\cdots (\bar a^{(2^k)})^{b_k}$$
en remarquant que $(x^{(2^i)})^2 = x^{(2^{i+1})}$ (programme de maths de 4ème ...).
On calcule les bits $b_i$ au fur et à mesure. Au départ, $b_0 = m\, {\rm mod}\, 2$ est m % 2 ou m & 1. Si c'est 1,
on multiplie le resultat res par $a$, sinon on ne fait rien. Puis on remplace $a$ par $a^2\,{\rm mod}\,n$
et $m$ par m//2 ou m>>1 et on recommence.
def powermod(a,m,n):
res = 1
while m:
if m & 1: res = (res*a) %n
m >>= 1
a = (a*a) %n
return res
powermod(3,33333,11)
powermod(5,666,2**101-1)
pow(5,666,2**101-1) # la fonction standard de Python
Le théorème de Fermat permet de prouver qu'un nombre $n$ n'est pas premier en exhibant un $a$ tel que $a^{n-1}\not\equiv 1\mod n$. C'est le test de Fermat. On peut montrer que chaque fois qu'on obtient 1, la probabilité que $n$ ne soit pas premier est presque divisée par 4. Malheureusement, il existe des nombres non premiers (les nombres de Carmichael) qui passent tous les tests de Fermat avec $a\wedge n=1$. Ils sont très rares, mais suffisent à faire capoter l'entreprise.
Le test de Miller-Rabin permet de remédier à ce problème. C'est une petite modification du calcul de $a^{n-1}\mod n$ dans laquelle on rajoute un test.
L'idée est que dans un corps, l'équation $x^2-1=0$ ne peut pas avoir plus de deux solutions. Dans les entiers modulo $n$, on a toujours $\bar 1$ et $-\bar 1$, et $x^2-\bar 1=(x-\bar 1)(x+\bar 1)$. Si on en trouve une autre $\bar b$, alors $(\bar b-\bar 1)(b+\bar 1)=\bar b^2-\bar 1=\bar 0$, donc on a des diviseurs de 0 et $n$ n'est pas premier.
Pour cela, on écrit $n-1=2^km$ avec $m$ impair, et on commence par calculer $b=a^m \mod n$. Si $b=1$, on renvoie True (probablement premier). Sinon, on calcule les $b^{(2^i)}\mod n$ et la première fois que le résultat vaut 1, on teste si la valeur précédente était $\equiv -1\mod n$. Si ce n'est pas le cas, on renvoie False (composé). Si on arrive à $b^{(2^k)}$ sans avoir rencontré de racine carrée non triviale de 1, on renvoie True.
Par exemple, 561 est un nombre de Carmichael. Si on calcule $2^{560}\,{\rm mod}\, 561$, on trouve 1. Mais si on décompose le calcul en écrivant $$560 =2^4\cdot 35,\ 2^{560} = (2^{35})^{2^4}$$ et en calculant d'abord $b=2^{35}\,{\rm mod}\, 561 = 263$, puis $b^2,b^4,b^8,b^{16}=2^{560}$, on peut observer que $b^4=67$ et $(b^4)^2=1$. On a donc trouvé une racine carrée de 1 modulo 561 autre que $\pm 1$. Donc 561 n'est pas premier.
factor(560)
b = powermod(2,5*7,561);b
# 2**9 = 512
for i in range(5): print(powermod(b,2**i,561), end=' ')
powermod(67,2,561)
# en voilà un assez grand
c = 1590231231043178376951698401
for a in range(2,12): print (powermod(3,c-1,c), end= ' ')
print (factor(c))
miller_rabin(c)
Il permet de résoudre les système de conguences
$$ \left\{ \begin{matrix} x &\equiv& x_1& [m_1] \\ x &\equiv& x_2& [m_2]\\ \vdots & \cdots &\vdots \\ x&\equiv &x_n&[m_n]\end{matrix}\right.$$lorsque les modules $m_i$ sont deux à deux premiers entre eux.
Pour chaque $i$, il est facile de trouver $a_i$ qui vérifie $a_i\equiv 0\ [m_j]$ pour tous les $j\not=i$. Il suffit de prendre $a_i=\prod_{j\not=i}m_j$. Ce nombre est premier avec $m_i$, donc inversible modulo $m_i$. Calculons les coefficients de Bézout tels que $1=u_ia_i+v_im_i$. Alors, $y_i=u_ia_i$ vérifie $y_i\equiv 1 \ [m_i]$ et $y_i\equiv 0\ [m_j]$ pour $j\not=i$, ce qui entraîne que $$X := y_1x_1+y_2x_2+\cdots y_nx_n$$ est solution du système. Il y en a d'autres : en ajoutant le produit $m=m_1m_2\cdots m_n$ à une solution, on obtient une autre solution, et deux solutions quelconques $x',x''$ diffèrent forcément d'un multiple de de $m$, puisque leur différence est divisible par tous les $m_i$.
La plus petite solution positive du système est donc $$x = y_1x_1+y_2x_2+\cdots y_nx_n \mod m.$$
Exemple Le problème des pirates (posé au CAPES de Maths)
Une bande de 17 pirates possède un trésor constitué de pièces d'or d'égale valeur. Ils projettent de se les partager également, et de donner le reste au cuisinier chinois. Celui-ci recevrait alors 3 pièces. Mais les pirates se querellent, et six d'entre eux sont tués. Un nouveau partage donnerait au cuisinier 4 pièces. Dans un naufrage ultérieur, seuls le trésor, six pirates et le cuisinier sont sauvés, et le partage donnerait alors 5 pièces d'or à ce dernier. Quelle est la fortune minimale que peut espérer le cuisinier s'il décide d'empoisonner le reste des pirates ?
On doit donc résoudre $$ \left\{ \begin{matrix} x &\equiv& 3& [17] \\ x &\equiv& 4& [11] \\ x &\equiv& 5& [6] \\ \end{matrix}\right. $$ On cherche $a_1$ qui vérifie $a_1\equiv 0$ mod $11,6$. On prend $a_1=6\times 11=66$, et on calcule son inverse modulo 17. Comme $66=4\times 17-2\equiv -2$ et $2\times 9=18\equiv 1$, on a (de tête) $(-2)(-9)\equiv 1$, l'inverse cherché est $-9\equiv 8$. On a donc que $y_1=8\times 66 = 528$ est congru à 1 modulo 17 et à 0 modulo 11 et 6.
On prend ensuite $a_2=17\times 6 = 102$ qui est congru à 3 modulo 11. Son inverse est donc 4, et $y_2=4\times 102=408$.
Finalement, $a_3=17\times 11= 187$ est congru à 1 modulo 6 donc $y_3=187$.
La plus petite solution positive sera $$x = 3\times 528 + 4\times 408+5\times 187 \mod 17\times 11\times 6 = 4151 \mod 1122 = 785.$$
Voir ici.
Par exemple, avec $(x_1,x_2,x_3,x_4)=(1,2,3,4)$ et $(m_1,m2,m_3,m4)=(1,13,17,19)$, on trouve $x= 41823$ :
solve_chinese([1,2,3,4], [11,13,17,19])
41823
On connaît déjà quelques exemples de groupes finis : les $({\mathbb Z}/n{\mathbb Z})^\times$, les éléments inversibles de ${\mathbb Z}/n{\mathbb Z}$, forment un groupe dont le nombre d'éléments est noté $\varphi(n)$ (indicateur d'Euler).
Le $\times$ en exposant signifie groupe multiplicatif, il est formé des éléments inversibles.
Par exemple, $$({\mathbb Z}/12{\mathbb Z})^\times=\{1,5,7,11\}.$$
On appelle ordre d'un élément $g$ d'un groupe fini $G$ (noté multiplicativement, d'élement neutre 1), le plus petit entier positif $m$ tel que $g^m=1$.
Il existe : puisque $G$ est fini, la suite $g^k$ des puissances de $g$ contient forcément deux éléments égaux, et si $g^k=g^l$, ($k<l$), alors $g^{l-k}=1$.
On appelle ordre du groupe $G$ son nombre d'éléments.
Ce choix judicieux des définitions permet d'énoncer élégamment le théorème de Lagrange :
Dans un groupe fini, l'ordre de tout élément est un diviseur de l'ordre du groupe.
En effet, prenons un élément $h$ de $G$, d'ordre $m$ dans un groupe d'ordre $n$. Alors, ou bien $m=n$, et c'est fini, ou bien $m<n$. Dans ce cas, on peut trouver un élément $g_1$ qui n'est pas dans l'ensemble $H$ des puissances de $h$. L'ensemble $g_1H=\{g_1,g_1h,\ldots,g_1h^{m-1}\}$ a lui aussi $m$ éléments distincts, dont aucun n'est dans $H$ : si on avait $g_1h^i = h^j$ alors, $g_1=h^{j-i}$ serait dans $H$. Si on ne peut pas trouver $g_2$ qui ne soit ni dans $H$, ni dans $g_1H$, alors, l'ordre $n$ de $G$ est $n=2m$, et on a fini. Sinon, on recommence avec $g_2$, et ainsi de suite, jusqu'à obtenir $G$ comme réunion disjointe d'ensembles $H,g_1H,\ldots,g_{k-1}H$ ayant tous $m$ éléments, et alors, $n=km$.
Voir aussi ici.
Si $G=({\mathbb Z}/p{\mathbb Z})^\times$ avec $p$ premier, $n=p-1$, et donc tout élément vérifie $\bar a^{p-1}=\bar 1$.
Si $G=({\mathbb Z}/n{\mathbb Z})^\times$, d'ordre $\varphi(n)$, tout élément vérifie $\bar a^{\varphi(n)}=\bar 1$.
Autrement dit, tout entier $a$ premier avec $n$ vérifie $a^{\varphi(n)}\equiv 1\,[n]$.
Si $n=p_1^{m_1}\cdots p_r^{m_r}$ est la décomposition de $n$ en facteurs premiers, le théorème des restes chinois montre que $${\mathbb Z}/n{\mathbb Z} \simeq {\mathbb Z}/p_1^{m_1}{\mathbb Z}\times\cdots\times {\mathbb Z}/p_r^{m_r}{\mathbb Z}$$ les opérations s'effectuant composante à composante sur les $r$-uples. Donc, un élément sera inversible si et seulement si ses résidus modulo tous les $p_i^{m_i}$ le sont.
Il suffit donc de savoir calculer $\varphi(p^m)$. Les éléments non inversibles de ${\mathbb Z}/p^m{\mathbb Z}$ sont les entiers $0\le a<p^m$ qui sont divisibles par $p$, c'est à dire $0,p,2p,3p,\ldots,(p^{m-1}-1)p$. Il y en a donc $p^{m-1}$, et $\varphi(p^m)=p^m-p^{m-1}$.
Le produit de ces nombres peut s'écrire $$\varphi(n)=n\prod_{p|n}\left(1-\frac1p\right)$$ (produit sur les diviseurs premiers de $n$).
On peut exprimer cette formule grace à la fonction de Möbius $\mu$ $$\mu(n) = \begin{cases} 1 & \text{si $n=0$}\\ (-1)^r&\text{si $n=p_1\cdots p_r$ est produit de $r$ nombres premiers distincts}\\ 0 & \text{sinon} \end{cases} $$
En développant le produit, on a $$\varphi(n)=\sum_{d|n}\mu(d)\frac nd.$$
Remarquons que $\varphi(n)$ est aussi le nombre d'élements d'ordre (additif) $n$ dans ${\mathbb Z}/n{\mathbb Z}$. En effet, $kx\equiv 0\mod n\Rightarrow n|k$ si et seulement si $x\wedge n =1$. Pour un diviseur $d$ de $n$, $\varphi(d)$ est donc le nombre d'éléments d'ordre $d$ dans ${\mathbb Z}/n{\mathbb Z}$, et on a $$n = \sum_{d|n}\varphi(d).$$
L'équivalence des deux expressions est un cas particulier de la formule d'inversion de Möbius, qui relie deux fonctions $f$ et $g$ sur les entiers positifs
$$ g(n)= \sum_{d|n}f(d)\quad \Leftrightarrow \quad f(n)=\sum_{d|n}\mu(d)g\left(\frac{n}{d}\right).$$