Nombre de puissances n-ièmes dans Fp*

OShine

Bonjour.
Je bloque sur une partie de la dernière question.

raoul.S

Si tu considères le polynôme $X^{\gcd(n,p-1)}-1$ et la question 2) ça t'inspire ?

Julia Paule

Prends x un générateur de Ker f, sans oublier que ce sous-groupe est cyclique.

Riemann_lapins_cretins

Julia Paule
C'est tricher, je ne pense pas que OS ait ce résultat dans son livre.

OShine

Julia Paule
Je ne vois pas.

OShine

raoul.S a dit : https://les-mathematiques.net/vanilla/index.php?p=/discussion/comment/2374770/#Comment_2374770

Si x est dans ker f alors le polynôme que tu donnes possèdes p-1 racines.
Mais je ne comprends pas le lien avec le cardinal de ker f.
Le livre donne un corrigé mais je n'ai rien compris.

Riemann_lapins_cretins

OShine a dit :

Julia Paule a dit :

Prends x un générateur de Ker f, sans oublier que ce sous-groupe est cyclique.

Je ne vois pas.

Le début ou la fin de la phrase ?

OShine

Je ne vois pas comment faire avec la méthode de @Julia Paule. Je ne comprends pas l'idée.

Je ne sais pas démontrer que ker f est cyclique pour commencer.

raoul.S

@OShine je te donne un indice supplémentaire juste pour voir à partir de quand tu arriveras à terminer tout seul...

Si on regarde bien la question 2) et qu'on la traduit un peu elle nous dit ça en fait : $x\in \ker f \Leftrightarrow$ $x$ est racine de $X^{\gcd(n,p-1)}-1$.

Et tu auras aussi besoin de l'indication de Julia Paule.

OShine

Je n'ai pas trop compris son indication mais il me semble que c'est un résultat sur les sous-groupes d'un groupe cyclique.
D'ailleurs j'ai lu dans un rapport des ENS que bon nombres de candidats des ENS ne savaient pas décrire les sous-groupes de $\Z / n \Z$.
D'ailleurs le corrigé donne ceci que je n'ai pas compris. Je vais continuer à chercher dans le cours sur les groupes cycliques.

Julia Paule

Avec $x$ un générateur de Ker f, tu peux montrer que l'ordre de Ker f divise pgcd (n,p-1).
Puis, si la division est stricte, tu obtiens une contradiction avec l'hypothèse en considérant $u^{(p-1)/pgcd(n,p-1)}$ où $u$ est un générateur de $F_p^*$.

Riemann_lapins_cretins

Ah mais tu savais que $F_{p}^{*}$ était cyclique OS ?

OShine

Tu ne justifies pas que ker f est cyclique pour commencer... Il faut dire que ker f est un sous-groupe de F_p * qui est cyclique. 
Si x est générateur de ker f c'est facile.
Si la division est stricte. L'ordre de u est pgcd(n,p-1). Mais je ne trouve pas la contradiction.
Pourquoi le corrigé ne se prend pas la tête à faire ça et répond en une demi ligne ?

OShine

Une tentative mais je pense que mon problème est que je ne comprends pas comment utiliser la question 2. C'est ce point qui me bloque depuis plus d'une journée.

Julia Paule

Un sous-groupe d'un groupe cyclique est cyclique.
L'ordre de u est p-1 dans tous les cas !
Si la division est stricte, $y=u^{(p-1)/pgcd(n,p-1)}$ vérifie la condition $y^{pgcd(n,p-1)}=1$, mais $y \notin Ker f$ (sinon ...).
Pourquoi le corrigé prend une phrase : il doit utiliser un résultat vu plus haut !

Amédé

Je ne comprend pas pourquoi demander alors que de toutes les manières tu as un corrigé. Essayes de comprendre ce corrigé.

Riemann_lapins_cretins

Je sais, OShine est insupportable... D'ailleurs, on ne devrait même pas être là à lui répondre... Mais on y est. C'est comme dans les grandes classes de collège, monsieur lourran, celles qui n'apprenaient vraiment rien, celles où il n'y avait pas géométrie et algèbre. Parfois, on ne voulait pas leur faire cours car comment rester heureux ? Comment notre monde pouvait-il redevenir comme il était avec tous les "c'est du chinois" qu'il a vus passer ? Mais, en fin de compte, il ne fait que passer ce diplômé prétentieux, même les vaniteux doivent passer. Un jour nouveau viendra et, lorsque le soleil ne shinera pas, il n'en sera que plus éclatant. C'était ces minors prétentieux dont on se souvenait et qui signifiaient tellement, même lorsqu'on était trop jeune taupe pour comprendre. Et je crois, monsieur lourran, que je comprends. Je sais maintenant. Les personnages de ces histoires avaient trente-six occasions de se retourner mais ils ne le faisaient pas, ils continuaient leur route parce qu'ils avaient envie de nous insupporter-...Sur quoi nous défoulons-nous, Riemann ?

-Il y a des têtes à claques en ce monde, monsieur lourran, et il faut se battre pour cela.

troisqua

@Amédé  : +1 . Il continue de demander des explications sur son corrigé et donc n'apprend pas l'autonomie (clé de l'apprentissage) parce qu'on lui répond... C'est sans fin. Vu qu'OShine apparaît mathématiquement "inférieur", ceux qui l'aident pensent avoir le dessus (ils lui donnent la leçon) et c'est pourtant lui qui a psychologiquement le dessus puisqu'il se fiche royalement de leur leçon et profite de leurs réponses pour satisfaire cette boulimie totalement absurde.

Chaque fil qu'il créé recommence un cycle infernal. La modération laisse faire, peut-être parce que ça fait vivre le forum, je me questionne à ce sujet, mais la qualité des échanges qui en découle est selon moi une grosse tâche sur ce si bel espace de rencontre mathématique, qui est pour moi l'un des joyaux de l'internet (comparé à ce qui se passe ailleurs .....).

Je crois que ceux qui continuent encore à lui répondre, après tant de temps, sans pouvoir arrêter devraient se questionner sur la(es) raison(s) qui les poussent à le faire.

JLT

Soit $C_n$ un groupe cyclique et $d$ un diviseur de $n$. Alors $H_d=\{x\in C_n\mid x^d=1\}$ est l'unique sous-groupe de $C_n$ de cardinal $d$. En effet,

1) Soit $a$ un générateur de $C_n$. Pour tout $k\in \{0,\ldots,n-1\}$, on a $a^k\in H_d\iff a^{kd}=1\iff n\mid kd\iff\frac{n}{d}\mid k$ donc $H_d=\{a^0,a^{\frac{n}{d}},a^{2\frac{n}{d}},\ldots,a^{(d-1)\frac{n}{d}}\}$, par conséquent $H_d$ est de cardinal $d$.

2) $H_d=\ker(x\mapsto x^d)$ donc $H_d$ est un sous-groupe de $C_n$.

3) Réciproquement, si $H$ est un sous-groupe de $C_n$ de cardinal $d$, alors $H\subset H_d$ d'après le théorème de Lagrange, et par égalité des cardinaux, $H=H_d$.

Riemann_lapins_cretins

Mais OS, la preuve du fait que le groupe multiplicatif d'un corps fini soit cyclique est difficile. Ça m'étonne particulièrement de savoir que tu as compris la preuve en bloquant sur des choses bien plus élémentaires.

Fin de partie

Il faut se rappeler qu'un diviseur commun à un entier $x$ et à un entier $y$ divise le pgcd de x et de y.

Ce qui fait qu'on a bien $x\in \mathbb{F}^\star_p,x^n=1$ implique $x^{\text{PGCD}(n,p-1)}=1$

Soit $d$ l'ordre de $x$, puisque le groupe $\mathbb{F}^\star_p$ est d'ordre $p-1$ on a que $d$ divise $p-1$.

Une propriété* sur les groupes finis, permet d'une égalité comme $x^n=1$, $n$ entier non nul, d'en déduire que $n$ est divisible par l'ordre de $x$ c'est-à-dire $d$ ici.

Donc a bien que $d$, l'ordre de $x$, divise à la fois $p-1$ et $n$ donc il divise leur PGCD donc il existe $k$ entier naturel tel que $\text{PGCD}(n,p-1)=d\times k$ donc $x^{\text{PGCD}(n,p-1)}=(\underbrace{x^d}_{=1})^m=1$

NB : dans ce qui précède on n'a pas utilisé le fait que $\mathbb{F}^\star_p$ était cyclique.

* :  l'ordre d'un élément $x$ d'un groupe fini est le plus petit entier naturel non nul tel que $x^d=1$, $1$ est l'élément neutre du groupe.

Si on a $x^n=1$ on divise $n$ par $d$, on a $n=k\times d+r$ avec $r$ un entier naturel tel que $0\leq r<d$.

Or, $1=x^n=x^{kd+r}=(\underbrace{x^d}_{=1})^k\times x^r=x^r$ on a donc trouvé un entier naturel $r$ strictement inférieur à $d$ tel que $x^r=1$ mais $d$ est par définition le plus petit entier naturel non nul qui vérifie une telle relation, cela signifie que $r=0$ ($x^0=1$) et donc que $d$ divise $n$.

Fin de partie

@Troisqua: Toute personne qui donne une réponse à quelqu'un qui ne l'a pas trouvée tout seul donne la leçon pour reprendre ton expression.  C'est inhérent à tout ce qui ressemble de près ou de loin à une relation de maître à élève.

OShine

Riemann_lapins_cretins a dit : https://les-mathematiques.net/vanilla/index.php?p=/discussion/comment/2374813/#Comment_2374813

Dans mon livre la preuve est facilitée par deux lemmes intermédiaires.

troisqua

On peut plus ou moins "donner la leçon". Il n'est pas difficile ici de voir dans quel sens cette expression a été employée. Mais je ne tiens pas à tenir un débat sur ce sujet avec toi. Je ne fais qu'exprimer une opinion personnelle, un souhait. Je n'oblige personne à être d'accord avec moi.

OShine

C'est plus facile à dire qu'à faire qu'il suffit de lire un corrigé pour le comprendre. Ce passage me pose beaucoup de difficultés même en relisant le cours 10 fois. Il est possible que seul je n'y arrive jamais à le comprendre.

OShine

Julia Paule a dit : https://les-mathematiques.net/vanilla/index.php?p=/discussion/comment/2374799/#Comment_2374799

Je ne comprends pas ce raisonnement.

troisqua

Selon moi, tu devrais trouver un professionnel pour t'aider psychologiquement. Je dis ça après avoir observé ton comportement, sans blague ni mépris. C'est juste le meilleur conseil que j'ai envie de te donner d'humain à humain. Ce conseil te sera plus utile que toutes les réponses que tu viens chercher ici, sans fin, sans progrès, dans une relation aux autres de plus en plus toxique pour tout le monde, surtout pour toi.

OShine

Fin de partie a dit : https://les-mathematiques.net/vanilla/index.php?p=/discussion/comment/2374814/#Comment_2374814

[Inutile de recopier un message présent sur le forum. Un lien suffit. AD]

Pourrais-tu préciser à quelle question es-tu en train de répondre ?
Je bloque sur la question 3 je n'ai pas eu de difficulté pour la question 2.

OShine

JLT a dit : https://les-mathematiques.net/vanilla/index.php?p=/discussion/comment/2374811/#Comment_2374811

[Inutile de recopier un message présent sur le forum. Un lien suffit. AD]

Merci mais je bloque sur le $H \subset H_d$.
Le théorème de Lagrange dit que le cardinal de $H$ divise le cardinal de $C_n$. Je ne vois pas comment en déduire l'inclusion.
Par ailleurs je n'ai pas l'impression que tu utilises la question 2. Comment fait le corrigé pour utiliser la question 2 et le théorème et répondre en une ligne ?

Vassillia

Bonjour,
Messieurs les matheux et mesdames les matheuses vous avez des capacités d'abstraction, des capacités de déduction, vous essayez généralement de convaincre que les maths sont fondamentales pour le développement de l'esprit. Ne me faites pas croire que vous n'êtes pas capable de résister à l'envie de répondre ou de vous défouler sur quelqu'un qui, certes est inférieur à vous en maths, mais vous manipule pour satisfaire un besoin insensé ? C'est toxique pour tout le monde et je dirais surtout pour vous de mon point de vue, j'ai peut-être trop d'ego mais jamais je ne me laisserai faire personnellement. A la limite, comme JLT, écrire la réponse pour un éventuel lecteur intéressé qui a le niveau pour ce genre d'exercice et c'est tout, peu importe que OShine comprenne ou non, vous ne le lui devez rien.

troisqua

@Vassillia : merci

JLT

Le théorème de Lagrange a pour corollaire que pour tout groupe $G$ d'ordre $d$ et tout $x\in G$ on a $x^d=1$.

Je n'utilise pas la question 2. La question 2 + mon message précédent permet de répondre à la première partie de la question 3.

Fin de partie

La réciproque: $x^{\text{PGCD}(n,p-1)}=1$ implique $x^n=1$ est immédiate. Soit $k=\text{PGCD}(n,p-1)$*.
On a donc $x^k=1$ par hypothèse et il existe $m$ tel que $n=m\times k$
$x^n=(\underbrace{x^k}_{=1})^m=1$

NB. Ici, non plus, on n'utilise pas le fait que $\mathbb{F}^\star_p$ est un groupe cyclique.

Donc, sauf erreur, on pourrait démontrer de la même manière et plus généralement que:

Si $G$ est un groupe fini, le nombre d'éléments de $G$ qui sont des puissances $n$-ème est égal à $\dfrac{|G|}{\text{PGCD}\left(n,|G|\right)}$

*Le PGCD de $x$ et de $y$ est un diviseur de $x$ et de $y$.

PS.
Je me suis laissé entraîner par l'enthousiasme. Tout ce que j'ai écrit ne permet pas en réalité de calculer l'ordre du cardinal du noyau du morphisme $x\in G\rightarrow x^n$. J'imagine que pour conclure on a besoin du fait que $\mathbb{F}_p$ est un corps à $p$ éléments et que donc une équation comme $x^n-1=0$ admet au plus $n$ racines.

OShine

@JLT ok merci.
Je ne vois pas comment combiner la question 2 et ce théorème. Je ne comprends pas pourquoi cet unique sous-groupe est $\ker f$.
J'ai écrit $\ker f =\{ x \in F_p ^{*} \ | \ x^{pgcd(n,p-1)} =1 \}$ mais je ne vois pas comment utiliser ce résultat.
Je bloque aussi sur la dernière ligne de la démonstration.

JLapin

@Vassillia @troisqua

N'oubliez pas d'insulter lourdement JLT qui a envoyé lui aussi un message de complément à son premier message en réponse à un autre message d'OS qui demandait des explications.

Il faut absolument le traiter lui aussi de gros pervers : il a osé répondre à une question, probablement pour mettre en valeur son énorme ego et obtenir la récompense suprême d'un "merci" par la suite. C'est vraiment scandaleux.

Plaisanterie à part, ça vous dirais d'arrêter de harceler des personnes qui font des maths ou parlent de maths sur un forum de maths ?

JLT

d=pgcd(n,p-1)

troisqua

@JLapin : "Insulter" ? "Gros pervers" ? Où as-tu lu cela ? Tu me fais dire des choses que je n'ai pas dites non ? Je crois que personne n'a mentionné l'égo comme seule raison qui ferait qu'on aide OShine. Vassillia en a donné plusieurs dans un message précédent et je les trouvais très justes. Quand je parle de pourrissement du forum, c'est exactement à ce genre d'emballement que je pense. Il arrive à semer la zizanie au sein des autres tout en continuant à recevoir ses "réponses" dans sa quête absurde. Ça doit être jubilatoire. Je vais m'arrêter là car je ne voudrais pas contribuer à ce que je dénonce (trop tard certainement).

Vassillia

Qu'est ce que tu racontes JLapin ? Il est évident pour moi que JLT fait partie des personnes qui ont la vocation d'enseignant et qui ne peuvent s’empêcher d'essayer de bien faire. J'ai la plus grande admiration pour ce comportement et cela m'insupporte d'autant plus de savoir qu'on les prend pour des c...

Si je peux faire en sorte qu'OShine se remette en question et que JLT ouvre les yeux, je pense avoir fait quelque chose de positif, rien à voir avec le harcèlement et ce n'est jamais moi qui fait dévier le fil en premier.

OShine ne fait pas de maths, il fait des photos d'un livre (dont il n'a vraisemblablement pas le droit de publier les écrits d'ailleurs même si peu importe) en disant j'ai pas compris, bosse pour moi gratuitement car ton temps ne représente rien pour moi et je ne veux surtout pas faire d'effort. Si tu cautionnes cette attitude, moi non. Mais effectivement, ça doit être jubilatoire pour lui de réussir à obtenir ce qu'il veut de personnes bien meilleures que lui en maths alors que professionnellement, il ne peut pas les égaler, c'est peut-être une revanche sur quelque chose.

JLapin

Je ne cautionne ni les critiques débiles d'OS du type "mon bouquin manque de pédagogie" ni les diagnostics bidons de problèmes psy sur OS et ceux qui lui répondent. Pour moi, les deux se valent.

Vassillia

Je n'ai pas dit que c'est un problème psy, je dis juste qu'il ne fait aucun effort et ne respecte pas ses interlocuteurs, c'est factuel et vérifiable et je trouve cela méprisable. D'ailleurs si je pensais que c'était un problème psy, je n'aurai pas de mépris pour cette attitude car ce ne serait pas de sa faute.

Fin de partie

Une fois qu'on sait que  $\{x\in \mathbb{F}^\star_p | x^n=1\}=\{x\in \mathbb{F}^\star_p | x^{\text{PGCD}(n,p-1)}=1\}$

$d=\text{PGCD}(n,p-1)$ il existe donc $k$ tel que $p-1=dk$ soit $g$ un générateur du groupe cyclique $\mathbb{F}^\star_p$

On a: $(g^k)^d=1$. Ce qui fait que $1,g^k,g^{2k},...,g^{(d-1)k}$ sont tous des éléments distincts* ($kd=p-1$) et si $x$ est l'un d'entre-eux alors $x^d=1$.

Ainsi, l'ordre du noyau du morphisme de groupes $x\in \mathbb{F}^\star_p\rightarrow x^n$ est supérieur ou égal à $d$.

Or, on sait aussi que tous les éléments du noyau appartiennent à $\{x\in \mathbb{F}^\star_p | x^d=1\}$ donc son cardinal est inférieur ou égal à $d$. Donc on a bien l'égalité qu'on voulait prouver.

*: le groupe $\mathbb{F}^\star_p$ est cyclique d'ordre $p-1$ ce qui fait que si $g$ est un générateur de ce groupe et si $0\leq k_1,k_2<p-1$ sont deux entiers naturels distincts $g^{k_1}$ et $g^{k_2}$ sont distincts.

OShine

Fin de partie
À partir du $d=$ c'est du chinois pour moi je ne comprends rien.

OShine

JLT a dit : https://les-mathematiques.net/vanilla/index.php?p=/discussion/comment/2374851/#Comment_2374851

Je ne comprends pas pourquoi $H_d = \ker f$ ni comment on utilise la question 2.

Cyrano

Tu ne comprends sérieusement pas pourquoi $d=pgcd(n,p-1)$ implique qu'il existe $k$ tel que $p-1=dk$ ?

OShine

Dans les messages de @Fin de partie je ne comprends pas ce qu'il veut faire ou montrer je suis noyé dans plein de texte et de calcul et je ne comprends pas ce qu'il fait.
Il y a plein de calculs et de phrases et je ne comprends pas le lien entre les différentes lignes.

Si car d divise p-1.

yawp

OShine=Doc

OShine

Je reste bloqué au même point sur le corrigé de la question 3 qui n'explique rien.

Thierry Poma

@OShine : l'on se sert du point 2) et des hypothèses. $\ker\,f$ (avec une minuscule !) étant un sous-groupe distingué du groupe multiplicatif $\Bbb{F}_p^*$ et vu que la corestriction de $f$ à $P$ est surjective, alors (...)

OShine

Le cardinal de $P$ j'ai compris je l'ai fait avec le théorème d'isomorphisme et les groupes quotients.
Le cardinal de $\ker f $ je suis bloqué dessus depuis 2 jours.

raoul.S

Par 2) on a $\ker(f)=\{x\in \mathbb{F}_p^{*}\mid x^d=1\}$. Je pense que ça tu es d'accord.

Ensuite tu prends le message de JLT ICI et tu remplaces $C_n$ par $\mathbb{F}_p^{*}$, $n$ par $p-1$, $d$ par $pgcd(n,p-1)$. (edit : ah oui j'allais oublier, attention de ne pas confondre les notations avant le "par" qui sont celle de JLT avec celles après qui sont celles de ton exo, par exemple lorsque je dis de remplacer $n$ par $p-1$ alors le $n$ c'est celui de JLT et le $p-1$ c'est celui de ton exo... mon Dieu )

Alors le $H_d$ de JLT correspond à $\ker f$. Et il a $d$ éléments comme il l'a montré et c'est terminé.

Le point 3) de JLT que tu ne comprends pas et ben il n'y a pas besoin de lui pour répondre à la question de ton exo donc tu peux l'oublier...

Le point 2) de JLT tu n'en as pas besoin non plus pour répondre à ton exo.

lourrran

Ecris noir sur blanc ce que tu sais sur $f$, sur $\mathbb{F}^{\star}_p$, sur les autres éléments qui interviennent dans l'exercice.
Ce que je dis, c'est juste du bon sens. Ca s'appelle travailler avec méthode.
Peut-être qu'en voyant tout ça noir sur blanc, tu auras la révélation.

Et si tu écris ça sur le forum, des gens sauront te dire ce qui est faux, ce qui manque, 
Là on sait que tu es perdu, mais on ne sait pas si tu es perdu au milieu des champs, en forêt ou dans une zone industrielle.