exo sur les groupes
Réponses
-
La cyclicité est une application de la formule $k=\sum_{d|k}\varphi(d)$.
Pour $d|n-1$, montre que le nombre d'éléments d'ordre $d$ de $(\Z/n\Z)^*$ est $0$ ou $\varphi(d)$, puis déduis en qu'il y en a exactement $\varphi(d)$. En particulier il y a des éléments d'ordre $n-1$.
Je crois qu'en général on ne sait pas donner de générateur de ces groupes autrement que par tatonnement. -
Bonjour,
Une méthode pour trouver les générateurs autrement que par tâtonnement:
p étant premier : [(Z/pZ)*,.] est isomorphe à [(Z/(p-1)Z),+).
Il existe donc $\varphi(p-1)$ générateurs pour chacun des deux groupes.
Exemple pour (Z/11Z)*:
1) d'abord , en trouver un : cl(2)
2) considérer l'isomorphisme
$\phi$: [(Z/10Z),+]---> [(Z/11Z)*,+] tel que $\phi(n)=cl(2^n)$.
3) les générateurs de (Z/10Z) sont plus cools à trouver :1,3,7;9.
4) les générateurs de (Z/11Z)* sont alors les images des générateurs de (Z/10Z).
5) exemple : $\phi(7)=cl(2^7)=cl(128)=cl(7)$
6) finalement: cl(2), cl(8), cl(7), cl(6) sont les quatre générateurs recherchés.
Bonne journée. -
Bonjour,
Je trouve la preuve du résultat suivant plus intuitive :
Tous sous-groupe fini du groupe multiplicatif d'un corps commmutatif est cyclique.
Preuve :
Soit K un corps commutatif et G un sous-groupe de cardinal n de K*.
On pose $n = (p_1)^(\alpha_1) ... (p_k)^(\alpha_k)$ la décomposition en facteurs premiers de n.
On considère le polynôme $P(X)=X^(\frac{n}{(p_1)^(\alpha_1)}) - 1 $
Il existe $y_1 \in G$ tel que $P(y_1) \neq 0$
Alors $(y_1)^((p_2)^(\alpha_2) ... (p_k)^(\alpha_k))$ est d'ordre (p_1)^(\alpha_1)$
On fait la même chose pour les autres indices, on multiplie les $y_i$ et on trouve un élément d'ordre n.
Lebesgue -
Bonjour,
Je trouve la preuve du résultat suivant plus intuitive :
Tous sous-groupe fini du groupe multiplicatif d'un corps commmutatif est cyclique.
Preuve :
Soit K un corps commutatif et G un sous-groupe de cardinal n de K*.
On pose $n = p_1^{\alpha_1} ... p_k^{\alpha_k}$ la décomposition en facteurs premiers de n.
On considère le polynôme $P(X)=X^{\frac{n}{p_1^{\alpha_1}}} - 1 $
Il existe $y_1 \in G$ tel que $P(y_1) \neq 0$
Alors $y_1^{p_2^{\alpha_2} ... p_k^{\alpha_k}}$ est d'ordre $p_1^{\alpha_1}$
On fait la même chose pour les autres indices, on multiplie les $y_i$ et on trouve un élément d'ordre n.
Lebesgue -
Plus généralement, si $G=$ est d'ordre $n$, les générateurs de $G$ sont exactement les $x^k$ où $k$ est premier avec $n$.
-
Bonjour
BS > Ta méthode est excellente dès que tu as ton 1), c'est à dire que tu as déjà un générateur de $[(\Z/p\Z)^*,\cdot ]$, mais le problème est justement de trouver un tel générateur.
Lebesgue > Ce que tu as prouvé, c'est que $ y_1^{p_2^{\alpha_2} ... p_k^{\alpha_k}}$ est d'ordre {\bf un diviseur de} $ p_1^{\alpha_1}$.
Tout le problème va être justement d'en trouver un qui soit d'ordre $ p_1^{\alpha_1}$
Guimauve > Je crois que tu confonds $$ dont tu connais un générateur (précisément $x$) avec $[(\Z/p\Z)^*,\cdot ]$ que tu sais être isomorphe au cyclique $$ mais dont tu ne connais pas explicitement le générateur $x$.
Une méthode pour montrer la cyclicité de $G= (\mathbb{F}_p^*,\cdot)$, est
$G$ est un groupe fini d'ordre $p-1$. Tous ses éléments satisfont $x^{p-1}=1$ (Lagrange).
Donc le polynôme $P(X)=X^{p-1}-1$ s'annule sur tous les éléments de $G$.
Or $\mathbb{F}_p$ est un corps donc $P$, qui est de degré $(p-1)$ a au plus $(p-1)$ racines dans $\mathbb{F}_p$, donc exactement les $(p-1)$ éléments de $G$.
Ces éléments sont donc les $(p-1)$ racines $p$-èmes de 1, donc forment un groupe cyclique d'ordre $(p-1)$
Cette démo se généralise à tout corps fini $\mathbb{F}_q, \ q=p^r$ et à tout sous-groupe fini de $(K^*,\cdot)$ où $K$ est un corps commutatif quelconque.
Comme dit Corentin, trouver un générateur de $(\mathbb{F}_p^*,\cdot)$ consiste en tâtonnements, essayer 2, puis 3, etc. en général on en trouve un assez rapidement, car il y en a quand même $\varphi(p-1)$ qui doit être plus du tiers de $p$ (Borde existe-t-il une minoration de $\varphi(p-1)$ en fonction de $p$ ? )
Alain -
Alain : je disais ça pour BS qui suppose connu un générateur (2 dans son exemple). Les autres générateurs sont alors les $2^k$ où k est premier avec 10.
Elle est cool ta démo. -
J'ai entre-aperçu une demande d'Alain ci-dessus, demande à laquelle je vais tenter de répondre.
Mais avant, rappelons néanmoins que ce problème est équivalent à l'existence ou non de racines primitives modulo $n$. Dans mon livre, j'ai mis deux preuves de cette existence lorsque $n=p$ est premier (théorème 3.29 et corollaire 4.21, que je préfère).
Maintenant, si $p \geqslant 5$, alors la minoration $\displaystyle {\varphi(p-1) > \frac {\ln 2}{2} \, \frac {p-1}{\ln(p-1)}$ est valide.
Dans un post récent, je donnais une majoration de $n\varphi(n)$ valide pour $n \geqslant 3$. En reprenant ce calcul, on a pour $p \geqslant 5$ : $$\varphi(p-1) \gg \frac {p-1}{\ln \ln (p-1)}.$$ Pour des minorations explicites, on se tournera vers le haut-de-gamme constitué par les (fameux !) résultats de Rosser & Schoenfeld (1962, on n'a pas fait mieux, depuis...) : pour $n \geqslant 3$, on a $$\frac{n}{\varphi(n)} < e^{\gamma} \ln \ln n + \frac {2,51}{\ln \ln n}.$$
Borde. -
J'ai entre-aperçu une demande d'Alain ci-dessus, demande à laquelle je vais tenter de répondre.
Mais avant, rappelons néanmoins que ce problème est équivalent à l'existence ou non de racines primitives modulo $n$. Dans mon livre, j'ai mis deux preuves de cette existence lorsque $n=p$ est premier (théorème 3.29 et corollaire 4.21, que je préfère).
Maintenant, si $p \geqslant 5$, alors la minoration $\displaystyle {\varphi(p-1) > \frac {\ln 2}{2} \, \frac {p-1}{\ln(p-1)}}$ est valide.
Dans un post récent, je donnais une majoration de $n\varphi(n)$ valide pour $n \geqslant 3$. En reprenant ce calcul, on a pour $p \geqslant 5$ : $$\varphi(p-1) \gg \frac {p-1}{\ln \ln (p-1)}.$$ Pour des minorations explicites, on se tournera vers le haut-de-gamme constitué par les (fameux !) résultats de Rosser & Schoenfeld (1962, on n'a pas fait mieux, depuis...) : pour $n \geqslant 3$, on a $$\frac{n}{\varphi(n)} < e^{\gamma} \ln \ln n + \frac {2,51}{\ln \ln n}.$$
Borde. -
J'ai entre-aperçu une demande d'Alain ci-dessus, demande à laquelle je vais tenter de répondre.
Mais avant, rappelons néanmoins que ce problème est équivalent à l'existence ou non de racines primitives modulo $n$. Dans mon livre, j'ai mis deux preuves de cette existence lorsque $n=p$ est premier (théorème 3.29 et corollaire 4.21, que je préfère).
Maintenant, si $p \geqslant 5$, alors la minoration $\displaystyle {\varphi(p-1) > \frac {\ln 2}{2} \, \frac {p-1}{\ln(p-1)}}$ est valide.
Dans un post récent, je donnais une majoration de $n / \varphi(n)$ valide pour $n \geqslant 3$. En reprenant ce calcul, on a pour $p \geqslant 5$ : $$\varphi(p-1) \gg \frac {p-1}{\ln \ln (p-1)}.$$ Pour des minorations explicites, on se tournera vers le haut-de-gamme constitué par les (fameux !) résultats de Rosser & Schoenfeld (1962, on n'a pas fait mieux, depuis...) : pour $n \geqslant 3$, on a $$\frac{n}{\varphi(n)} < e^{\gamma} \ln \ln n + \frac {2,51}{\ln \ln n}.$$
Borde (message précédent à supprimer. Merci). -
Bonsoir Borde
Merci beaucoup pour cette réponse.
J'ai tabulé ces différentes minorations $$ \begin{array}{ccccc}
p & \varphi(p-1) & \dfrac{\ln(2)(p-1)}{2 \ln(p-1)} & \dfrac{p-1}{e^\gamma \ln \ln (p-1) + \frac{2,51}{\ln \ln (p-1)}} & \dfrac{p-1}{\ln \ln(p-1)} \\
3 & 1 & 1,00 & -0,27 & -5,46 \\
5 & 2 & 1,00 & 0,48 & 12,25 \\
7 & 2 & 1,16 & 1,12 & 10,29 \\
11 & 4 & 1,51 & 2,22 & 11,99 \\
13 & 4 & 1,67 & 2,74 & 13,18 \\
17 & 8 & 2,00 & 3,74 & 15,69 \\
19 & 6 & 2,16 & 4,23 & 16,96 \\
23 & 10 & 2,47 & 5,20 & 19,49 \\
29 & 12 & 2,91 & 6,62 & 23,26 \\
31 & 8 & 3,06 & 7,09 & 24,51 \\
37 & 12 & 3,48 & 8,49 & 28,21 \\
41 & 16 & 3,76 & 9,42 & 30,64 \\
43 & 24 & 3,89 & 9,88 & 31,86 \\
47 & 22 & 4,16 & 10,80 & 34,26 \\
53 & 24 & 4,56 & 12,17 & 37,84 \\
59 & 28 & 4,95 & 13,53 & 41,39 \\
61 & 16 & 5,08 & 13,98 & 42,57
\end{array} $$ La deuxième colonne donne une minoration proche de la valeur $\varphi(p-1)$.
Il semblerait sur ces valeurs, que $\varphi(p-1) \geq 0,23 p$ mais ça ne peut marcher parceque $\frac{n}{\ln \ln n}$ n'a pas d'asymptote.
La dernière colonne est une minoration asymptotique, sait-on à partir de quelle valeur de $n$ cette minoration est valable ?
Alain -
bonsoir, bien que je ne connaisse pas grand-chose en théorie des groupes, la lecture de ce fil m'a rappelé que j'avais dévoré étant étudiant le bouquin de warusfel: Structures algébriques finies qui donne pas mal de résultats sur les éléments inversibles de $\Z / n \Z$.A demon wind propelled me east of the sun
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 165.5K Toutes les catégories
- 64 Collège/Lycée
- 22.2K Algèbre
- 37.6K Analyse
- 6.3K Arithmétique
- 61 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 26 CultureMath
- 51 Enseignement à distance
- 2.9K Fondements et Logique
- 10.8K Géométrie
- 86 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 79 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 29 Mathématiques et finance
- 343 Mathématiques et Physique
- 5K Mathématiques et Société
- 3.4K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 804 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres