Résultats d’arithmétique¶
Théorèmes fondamentaux sur les groupes¶
Lagrange
Soit \(G\) un groupe fini d’ordre \(n\), alors pour tout \(x\in G\), l’ordre de \(x\) divise \(n\).
Démonstration
Démonstration élémentaire dans le cas abélien : puisque \(G=xG\), \(\prod_{G}y=\prod_{G}(xy)=x^n\prod_G y\) donc \(x^n=1\).
Cauchy
Soit \(G\) un groupe fini de cardinal \(n\). Alors pour tout diviseur premier \(p\) de \(n\), il existe un élément d’ordre \(p\).
Démonstration
Démonstration élémentaire dans le cas abélien : soient \(x_1,\dots x_k\) des générateurs de \(G\), d’ordres respectifs \(n_1,\dots n_k\). Alors on a un morphisme surjectif
donc \(p\mid \card{G}\mid \prod n_i\), d’où \(p\mid n_i\) pour un certain \(i\), d’où l’élément \(x_i^{\frac{n_i}p}\) d’ordre \(p\).
Proposition
Soit \(G\) un groupe abélien fini, il existe \(d_1\mid d_2\dots \mid d_r\) tel que \(G\simeq \prod \Z/d_i\Z\).
Démonstration
Appliquer une réduction de Smith au noyau du morphisme surjectif ci-dessus.
Proposition
Soit \(G\) un groupe cyclique d’ordre \(n\), \(G\) est isomorphe à \(\Z/n\Z\). Pour tout \(d\mid n\), \(G\) possède un unique sous-groupe d’ordre \(d\), qui est cyclique. Les générateurs de \(\Z/n\Z\) sont les classes d’entiers premiers à \(n\).
Puissances¶
Théorème
Soit \(G\) un groupe de cardinal \(n\). Alors pour \(k\in \Z/n\Z\), l’exponentiation
est bijective si et seulement si \(\pgcd(k,n)=1\). Son inverse vaut alors \(e_l\) où \(l=k^{-1}\bmod n\).
Démonstration
L’application ne dépend que de \(k\bmod n\) car \(m^n=1\) (Lagrange). Si \(k\) est inversible, on a en effet \(m^{kl}=m\).
Pour la réciproque on peut utiliser le théorème de Cauchy : si \(p\mid \pgcd(k,n)\), alors il existe \(m\in G\) d’ordre \(p\), et \(m^k=1=1^k\) donc \(e_k\) n’est pas bijective.
Dans le cas où \(k\) n’est pas inversible, on comprend bien le noyau
Proposition
Soit \(G\) un groupe cyclique d’ordre \(n\). Alors le noyau de \(e_k\) est de cardinal \(\pgcd(k,n)\).
Démonstration
Notons \(d\) ce pgcd, \(n\mid xk\) ssi \(\frac nd\mid x\), donc le noyau est \(\frac nd\Z/n\Z \sim \Z/d\Z\). $kx \equiv 0\bmod n \
Exponentielle et logarithme¶
Soit \((G,g)\) la donnée d’un groupe cyclique d’ordre \(n\), muni d’un générateur \(g\).
Alors on appelle exponentielle et logarithme de base \(g\) les isomorphismes inverses l’un de l’autre
et
L’anneau \(\Z/n\Z\)¶
Structure¶
Proposition
Soit \(n\) un entier et \(n=\prod p^{e_p}\) sa factorisation en produit de facteurs premiers, alors on a l’isomorphisme d’anneaux
Il reste à étudier la structure de \((\Z/p^e\Z)^\ast\).
Proposition
Soit \(p\geq 3\) et \(e\geq 1\). Alors \((\Z/p^e\Z)^\times\) est cyclique d’ordre \((p-1)p^{e-1}\).
D’autre part, pour \(p=2\) et \(e\geq 2\), \((\Z/2^e\Z)^\times\simeq \Z/2\Z\times \Z/2^{e-2}\Z\).
Remarque
On ne connaît pas de générateur explicite de \((\Z/p\Z)^\times\), c’est même un problème ouvert (conjecture d’Artin). Toutefois il est très facile d’en déterminer en pratique en tirant au hasard.
Ensuite, \(1+p\) (resp. \(1+4\)) est un générateur du sous-groupe d’ordre \(p^{e-1}\) (resp. \(2^{e-2}\)).
Propriétés¶
On note \(\varphi(n)\) le cardinal de \((\Z/n\Z)^\ast\).
D’après le lemme chinois, \(\varphi(n)=\prod_{p^e\mid n} (p^e-p^{e-1}) = n\prod_{p\mid n}(1-1/p)\).
Théorème
Soit \(n>1\) et \(a\in(\Z/n\Z)^\ast\). Alors \(a^{\varphi(n)}\equiv1\bmod n\).
Lemme
Soit \(n\) un entier impair sans facteur carré. Alors on a équivalence entre
\(n\) n’est pas premier
il existe \(a\) tq \(a\neq\pm1\bmod n\) mais \(a^2=1\bmod n\).
De plus, dans ce cas toute telle valeur de \(a\) fournit une factorisation non triviale \(n=\pgcd(a-1,n)\pgcd(a+1,n)\).
Démonstration
Si \(n=pq\), toute valeur \(a\) tq \(a=1\bmod p\) et \(a=-1\bmod q\) convient.
Tandis que si \(n=p\) est premier, alors \(\pm1\) sont les deux seules racines carrées de \(1\).
Enfin si \(n\mid a^2-1=(a-1)(a+1)\) mais que \(n\nmid a-1\) et \(n \nmid a+1\) alors les deux pgcd sont non triviaux.
Lemme
Soit \(n=pq\) un entier et \(m\) un entier tel que \(\forall a, a^{2m}=1\) mais \(\exists a, a^{m}\neq 1\).
Alors
En d’autres termes, plus de la moitié des \(a\) sont tels que \(\pgcd(a^m+1,n)\) est un facteur strict de \(m\).
Démonstration
Notons \(H=\set{a, a^m=\pm 1}\), alors \(H\) est un sous-groupe de \((\Z/n\Z)^\times\), et un sous-groupe strict car par hypothèse il existe \(a\) tq \(a^{m}\neq 1\bmod p\) ou \(a\neq 1\bmod q\), de sorte que \(b\) tq \(b=a\bmod p\) et \(b=1\bmod q\) n’est pas dans \(H\). Ainsi, \(H\) est d’indice au moins 2.
Résidus quadratiques¶
Structure¶
Définition
On appelle résidus quadratiques modulo \(n\) les carrés modulo \(n\), c’est-à-dire les \(a\in\Z/n\Z\) tels qu’il existe \(x\), \(a\equiv x^2\bmod n\).
Proposition
Soit \(p\geq 3\) un nombre premier. Il existe \(\frac{p-1}2\) résidu quadratiques dans \((\Z/p\Z)^\ast\).
Démonstration
Puisque \(\Z/p\Z\) est un corps, on a \(1\to \pm 1\to \F_p^\ast\to (\F_p^\ast)^2\to 1\), ce qui fait \(\frac{p-1}2\) résidus quadratiques non nuls.
Reconnaître les carrés¶
Symbole de Legendre
Soit \(p\) premier impair et \(a\in\Z\). Alors on définit le symbole de Legendre
et l’on a
symbole de Jacobi
On étend le symbole de Legendre à tout couple d’entiers \(a,n\), avec \(n\) impair, de la manière suivante : si \(n=\prod p_i^{e_i}\), on pose
Ce symbole est multiplicatif en \(a,n\), c’est-à-dire que pour tous \(a,b,m,n\) on a
Attention : on n’a plus \(n\) carré mod \(m\) ssi \(\kronecker nm=1\). Ainsi, si \(n=pq\) et \(a\) est non-résidu quadratique modulo \(p\) et \(q\), alors \(\kronecker an=(-1)(-1)=1\) mais \(a\) n’est pas résidu quadratique modulo \(n\). Le même exemple fonctionne modulo \(p^2\).
Toutefois on garde l’implication \(a\) carré \(\Rightarrow\) \(\kronecker an=1\).
Le calcul de \(\kronecker an\) sans factorisation de \(n\) est rendu possible par l’énoncé suivant
Réciprocité quadratique
Soient \(m,n\in\Z\) impairs, avec \(\pgcd(m,n)=1\). Alors on a les formules
\(\kronecker{-1}m=(-1)^{\frac{m-1}2}\) ;
\(\kronecker2m=(-1)^{\frac{m^2-1}8}\) ;
\(\kronecker mn\kronecker nm = (-1)^{\frac{(m-1)(n-1)}4}\).
Grâce à la réciprocité quadratique, on peut calculer des symboles de Jacobi modulo de grands entiers sans avoir besoin de les factoriser.