Nombre d'éléments d'ordre $k$ dans un groupe
Bonjour,
est-ce que l'un d'entre vous pourrait m'expliquer comment calculer le nombre d'éléments d'ordre $k$ dans un groupe ?
Par exemple je souhaite calculer le nombre d'éléments d'ordre $12$ dans le groupe multiplicatif $(\mathbb Z/N\mathbb Z)^*$ avec $N=5\times 7\times 9$.
Merci
est-ce que l'un d'entre vous pourrait m'expliquer comment calculer le nombre d'éléments d'ordre $k$ dans un groupe ?
Par exemple je souhaite calculer le nombre d'éléments d'ordre $12$ dans le groupe multiplicatif $(\mathbb Z/N\mathbb Z)^*$ avec $N=5\times 7\times 9$.
Merci
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
tu parcours toutes les valeurs de i=2 à N et tu calcules , à i fixé, i^k modulo(N) pour k=2,.... tant que tu n'obtiens pas le reste 1.
Quand tu obtiens un reste de 1 tu regardes si k=12, si c'est le cas alors tu incrémentes un compteur de 1. et tu passe à i+1...
A la fin la valeur du compteur te donnera le nombre d'éléments d'ordre 12.
merci poirot pourrais tu expliquer le raisonnement ?
D'autre part, l'assertion de Poirot n'est juste que si $k$ divise l'ordre du groupe.
Pour répondre à la question initiale, notons $a_k(G)$ le nombre d'éléments $g\in G$ tels que $g^k=e$. Alors le nombre d'éléments de $G$ d'ordre $12$ est $a_{12}(G)-a_6(G)-a_4(G)+a_2(G)$.
D'autre part, si $G=H\times K$ alors $a_k(G)=a_k(H)a_k(K)$.
Enfin, on sait que $(\Z/N\Z)^*\cong (\Z/5\Z)^*\times (\Z/7\Z)^*\times (\Z/9\Z)^*$ et que chacun des facteurs est cyclique. Ceci devrait permettre de faire le calcul, sachant que si $H$ est cyclique alors $a_k(H)=\mbox{pgcd}(k,|H|)$.
Il me semble que si $(Z/NZ)^*$ peut s'écrire comme produit de groupe cyclique, il était également cyclique à la condition que les n soit deux a deux premiers entre eux.
Ici par le lemme chinois on peut voir que $(\Z/N\Z)^*\cong (\Z/5\Z)^*\times (\Z/7\Z)^*\times (\Z/9\Z)^* \cong (\Z/4\Z) \times (\Z/6\Z) \times(\Z/6\Z)$.
Du coup les indices des groupes inversibles sont premiers entre eux, tandis que ceux des groupes ne le sont pas. Comment l'expliquer ?
P.S. Je trouve le même résultat numérique que flipflop.
$$144-72-16+8= 144-72-8= ... 64$$
C'est un principe d'exclusion, avec une formule de Möbius ?
[Edit : coquille corrigée d'après le message ci-dessous.]
ça serait pas plutôt n/d
$a_n=\sum_{d\mid n}b_d$, donc $b_n=\sum_{d\mid
n}\mu(d)a_{n/d}$?
$(f\ast g)(n)=\sum_{d\mid n} f(d)g(n/d)$. Alors on a $(f\ast g)(x)=\sum_{yz=x}f(y)g(z)$. Cette expression est symétrique, donc $f\ast g = g\ast f$.
De plus, on a la formule $(f\ast g)\ast h=f\ast (g\ast h)$ car $(f\ast g\ast h)(x)=\sum_{yzt=x}f(y)g(z)h(t)$.
Notons $\mathbf{1}$ la fonction constante égale à $1$, et $\delta$ la fonction telle que $\delta(1)=1$ et $\delta(n)=0$ si $n>1$. Soit $\mu$ la fonction de Möbius. On a $\mu\ast \mathbf{1}=\mathbf{1}\ast\mu=\delta$.
L'égalité $a_n=\sum_{d\mid n}b_d$ s'écrit $a=b\ast \mathbf{1}$.
On a donc $b=b\ast\delta=b\ast(\mathbf{1}\ast\mu)=(b\ast\mathbf{1})\ast\mu=a\ast\mu=\mu\ast a$, donc $b_n=\sum_{d\mid n}\mu(d)a_{n/d}$.
mais tu avais écrit a(d/n) au lieu de a(n/d) .
Hier je ne connaissais pas ça.
Je conclus conclue ma nuit pas trop mal mais ce n'est pas en dormant que je maîtriserai maîtriserai ce sujet.
voici un autre moyen, du moins pour l'exemple proposé, en utilisant le fait que l'ordre d'un élément $(a,b,c)$ d'un groupe produit est le ppcm des ordres de $a,b,c$
ici $a$ est dans $(Z/5Z)^*$ cardinal 4, cyclique
$b$ est dans $(Z/7Z)^*$, cardinal 6, cyclique
$c$ est dans $(Z/9Z)^*$ cardinal 6, cyclique donc isomorphe au précédent
Il est facile de trouver les ordres de chaque élément de ces (petits) groupes
le ppcm des ordres de $a,b,c$ devant être 12, cela implique que l'ordre de $a$ soit 4 (pas 1, ni 2), sinon le ppcm est au plus $6$
comme $(Z/5Z)^*$ a deux éléments d'ordre $4$ ( ses générateurs)
il y a au plus $2\times 6 \times 6=72$ éléments $(a,b,c)$ possibles :
il faut ôter les cas où les ordres de $b$ et $c$ ne sont pas divisibles par 3 , soit
$2\times 2 \times 2=8$
Et le nombre d'éléments $(a,b,c)$ d'ordre $12$ est $72-8=64$
j'ai donc vérifié et tu as raison il est cyclique
isomorphe à $(\mathbb {Z}/6\mathbb {Z},+)$
:-X
perte de temps inutile et gaspillée pour rien :-X
entre parenthèses
existe t-il une notation commode pour écrire l'ordre d'un élément?
parce que dans ce que j'écris ord(x) est chiant (mon texte est long)
je voudrai écrire [x] pour l'ordre d'un élément et pareil [G] pour l'ordre d'un groupe
notations identiques pour deux choses différentes
vous feriez quoi à ma place?
Ici sur ce fil, je donne un petit résultat sur les groupes
Vraiment pas grand chose [modéré].
Bon bref ...j'ai utilisé le théorème de Cauchy voir ici-> https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Cauchy_(groupes)
___________________
par convention de notation pour x un réel positif
la notation INT(x) désignera la partie entière usuelle de x
donc $x\geq INT(x)$
_______________________
Soit G un groupe, je note $n$ son ordre
tel que n est supérieur à 3 et n'est pas premier
je note $\{ p_1, ... , p_m \},m\geq 2$
l'ensemble des facteurs premiers de $n$
je pose que $p_1$ est le plus petit des facteurs premiers de $n$
ALORS
si je note $z_i$ est le nombre d'éléments de $G$ qui sont d'ordre $p_i$
on vérifie toujours
$p_i-1\leq z_i\leq (p_i-1)+p_i . INT\begin {pmatrix}\frac {m+n-1+\sum _{i=1}^m p_i}{p_1} \end {pmatrix}$
soit $G$ un groupe d'ordre $n\geq 2$ et notant $P=\{p_1,...,p_m\},m\geq 1$ les facteurs premiers de $n$ et notant $p_1$ le plus petit de ces facteurs premiers et notant $f_i$ la quantité d'éléments de $G$ dont l'ordre est $p_i$ et notant $INT(x)$ la partie entière usuelle d'un rationnel positif
alors $p_i-1\leq f_i\leq p_i-1+p_i . INT\begin {pmatrix}\frac {m+n-1+\sum _{i=1}^m p_i}{p_1} \end {pmatrix}$
_______
démonstration
selon le théorème de Cauchy stipulant que $f_i$ est de valeur $-1[p_i]$
et étant donné que l'ordre d'un élément est unique, il vient qu'en ne comptant pas l'élément neutre, on a:
$\sum _{i=1}^m f_i=(p_1-1)+l_1p_1+...+(p_m-1)+l_mp_m\leq n-1,l_i\in \mathbb {N}$
il vient donc $\sum _{i=1}^m l_ip_i \leq m+n-1-\sum _{i=1}^m p_i $
posons $l=m+n-1-\sum _{i=1}^m p_i $
en notant $p_1$ le plus petit des facteurs premiers de $n$ alors $\forall i\in \mathbb {N}^*_m,\mathbb {N}^*_m=\{1,...,m\},l_i\leq \frac {l}{p_1}$
et en posant $l_0=INT\begin {pmatrix}\frac {l}{p_1} \end {pmatrix}$ alors $\forall i\in \mathbb {N}^*_m,l_i\leq l_0$
démonstrons-le par l'absurde :
admettons qu'il existe $u\in \mathbb {N}^*_m$ tel que $l_u>l_0$ et pour tout $i\neq u,l_i=0$ posons $l_u=INT\begin {pmatrix}\frac {l}{p_1} \end {pmatrix}+1$
alors $\frac {l}{p_1}=INT\begin {pmatrix}\frac {l}{p_1} \end {pmatrix}+\begin {Bmatrix}\frac {l}{p_1} \end {Bmatrix},0\leq \begin {Bmatrix}\frac {l}{p_1} \end {Bmatrix}<1$ donc $l_u=\frac {l}{p_1}-\begin {Bmatrix}\frac {l}{p_1} \end {Bmatrix}+1$
on peut donc poser $0<t\leq 1$ tel que $l_u=\frac {l}{p_1}+t$
$p_u-1+l_up_u+\sum _{i=1,i\neq u}^m \begin {pmatrix}(p_i-1)+\underbrace {l_ip_i}_{=0 }\end {pmatrix}\leq n-1$
il vient $l_upu-m+\sum _{i=1}^m p_i\leq n-1$ donc $p_u.\begin {pmatrix}\frac {l}{p_1}+t \end {pmatrix}-m+\sum _{i=1}^m p_i\leq n-1$
et étant donné que $p_1$ est le plus petit des facteurs premiers de $n$ alors $\frac {p_u}{p_1}\geq 1$
on peut poser $w\in \mathbb {N}^*$ tel que $lw+tp_u-m+\sum _{i=1}^m p_i\leq n-1$
on doit démontrer par l'absurde que cette inégalité est fausse donc il suffit de le démontrer avec $w=1$ et $tp_u=1$ car $t>0$
on en arrive à l'inégalité $l-m+1+\sum _{i=1}^m p_i\leq n-1$ donc à $m+n-1-\sum _{i=1}^m \begin {pmatrix} p_i\end {pmatrix}-m+1+\sum _{i=1}^m \begin {pmatrix} p_i\end {pmatrix} \leq n-1$
donc à $n\leq n-1$ ce qui est faux