Équation sur $\mathbb F_p$

@gai requin
Mais pour un premier $p$, c'est la même chose que $p \equiv 1 \bmod 3$, non ?
Et surtout, pas besoin de loi de réciprocité quadratique. Au contraire, cela pourrait être une INTRODUCTION à la loi de réciprocité quadratique. Non ?

Gai requin,

$$(x^2+x+1)(x-1)$$

Et peut-être que l'équivalence à montrer, on peut l'énoncer de la manière suivante, pour $p \ne 3$ :
$$
\hbox {$-3$ carré modulo $p$} \quad\iff\quad p \equiv 1 \bmod 3 \qquad\qquad (\heartsuit)
$$
Ainsi cela sentira bon la réciprocité ($p$ modulo 3 versus $-3$ modulo $p$).

Un sens de $(\heartsuit)$ a été (presque) montré, sens dans lequel le trinôme $X^2 + X + 1$, de discriminant $-3$, a son mot à dire.

Et dans l'autre sens (pour des petits) ?

Mais sans utiliser la réciprocité quadratique :-D

@gai requin
Peut-on se passer de l'utilisation de $(\Z/p\Z)^*$ cyclique ? Peut-on attraper un élément d'ordre 3 autrement ?

Hum : ton $3k$, c'est $-1$ (modulo $p$ of course) ; et tu prétends donc que ...

Yes. Et on peut ajouter que $\mathbb F_p^*$ se partage en deux morceaux, $M$ pour mauvais, $B$ pour bon :
$$
\mathbb F_p^* = M \vee B, \qquad \qquad
M = \{ y \mid y^{p-1 \over 3} = 1 \} \qquad
B = \{ y \mid y^{p-1 \over 3} \ne 1 \}
$$
En prenant $y \in B$, comme tu as dit et en posant $x = y^{p-1 \over 3}$, alors $x$ est d'ordre 3.

(A) Idée de $\#M$ et $\#B$ ? Avant : faire intervenir $\varphi : \mathbb F_p^* \ni z \mapsto z^{p-1 \over 3} \in \mathbb F_p^*$. Quelle est l'image de $\varphi$ ? Puis revenir à la question (A).

@gai requin
OK. Dans la pratique (sic), tu tires au hasard et tu as donc 2 fois plus de chances de tomber dans $B$ que dans $M$. C'est quoi la pratique ? Ce qui suit pour obtenir un des deux éléments d'ordre 3 dans $\mathbb F_p^*$ pour $p \equiv 1 \bmod 3$

> p := 3*Random(10^30, 10^40) + 1 ;             <---  pour être sûr d'avoir p = 1 mod 3
> while not IsPrime(p) do p := p+3 ; end while ; <-- incrément de 3
> p ;
16320282724446584012075970839134221093319
> 
> e := ExactQuotient(p-1, 3) ; 
> repeat "un tirage" ; y := Random(1,p-1) ; x := Modexp(y,e,p) ; until x ne 1 ;
un tirage
un tirage
> x ;
4269838427940354808946318071811887957614
> x^3 mod p ;
1

Modexp(y,e,p) c'est $x^e \bmod p$ de manière efficace (on ne calcule pas $x^e$ que l'on réduit modulo $p$ plus tard, on réduit au fur et à mesure).

Extrêmement efficace pour obtenir une racine cubique (une vraie, pas 1). Car ne pas oublier qu'il y en a 2 seulement et que si, bêtement, je parcours 1 à $p-1$ pour en trouver, je risque attendre longtemps.


On s'amuse ? Ben oui. Mais maintenant, on peut aller plus loin. On suppose $p \equiv 1 \bmod 3^2$ et peut-être même $p \equiv 1 \bmod 3^k$ selon son envie. Montrer de manière constructive (ah, ah) l'existence d'un élément d'ordre $3^2$ (ou $3^k$ selon les goûts) et le moyen efficace d'en attraper 1. Et on va trouver la même répartition $(1, 2)$ pour M, B et ceci quel que soit $k$ !!

Et ensuite, on chante le truc : $3$ est un premier quelconque. Do you see what I mean ? Et à la fin, tout à la fin, on assemble ... Et on obtient un générateur de $\mathbb F_p^*$.

@gai requin
Problème 1 : on est en train de squatter le fil de Skywear, c'est pas bien.

Problème 2 : il manque (à mon goût) un certain nombre de précisions dans ta réponse, Par exemple, pour $q = 3$, on ne voit pas la proportion $(1/3, 2/3)$ pour ``bon versus mauvais''. Il y a également des conditions inutiles sur $r$ (suffit d'assurer la chose pour $r = k$, je ne peux pas en dire plus). Et d'autres informations.

Ma philosophie, tu la connais, c'est de ne pas en dire le moins possible mais le plus possible. Et bien sûr, on pourrait penser que l'on fait tout un fromage de quelque chose que l'on juge élémentaire (ici cyclicité de $\mathbb F_p^\times$) parce que l'ON CONNAIT. Rien à voir, circulez.
Mais qu'en sera-t-il dans un nouveau domaine que l'on cherche à comprendre ? Ainsi, de mon côté, j'aurais bien aimé que l'on me fasse tout un fromage autour de la définition $\text{Cl}_{\mathfrak m} = I_K(\mathfrak m)/P_{K,1}(\mathfrak m)$, au lieu de balancer la définition comme si c'était du petit lait. Heureusement que l'on trouve certains auteurs qui en font tout un fromage (Lenstra & Stevenhagen).

Mais ``ma philosophie'', je n'impose absolument pas qu'on la partage.

@gai requin
C'est plus simple que tu ne le penses. Je continue à prendre $q = 3$ (pourquoi ? parce que j'en ai envie) et donc $p \equiv 1 \bmod 3$. Dans ma manière de voir les choses :

1) Je ne suppose pas que $k$ est la valuation de $3$ dans $p-1$ mais seulement que $p \equiv 1 \bmod 3^k$
2) Je continue à utiliser le polynôme $Y^{p-1 \over 3} -1$ en prenant $y \in \mathbb F_p^*$ NON racine de ce polynôme.

Pourquoi 1). Parce que je veux être compatible avec avant i.e. le cas $k=1$ qui ne supposait pas que 1 est la valuation de $3$ dans $p-1$. De plus, on pourrait avoir l'impression que la valuation de $3$ dans $p-1$ joue un rôle dans la preuve mais ce n'est pas le cas.

2) En continuant à utiliser $Y^{p-1 \over 3} - 1$, on voit mieux la proportion $(1/3, 2/3)$. Mais surtout je fais quoi avec $y$ non racine de ce polynôme ? Réponse ; je pose
$$
x = y^{p-1 \over 3^k}
$$
Cela a du sens car $3^k \mid p-1$. Et je dis que $x^{3^k} = 1$, ça c'est sûr. Et que $x$ est d'ordre $3^k$ exactement. Indication : puisque $x^{3^k} = 1$, l'ordre de $x$ est parmi les ... (à compléter). Et les diviseurs de $3^k$ sont .... (à compléter). Conclure.

Gai requin : Et tu tu as fait comment avec $x^2+x-1$ ?

Les Frobenius Alphonse les Frobenius :-D

Sinon faut faire pareil $\tau_1$, $\tau_{-1}$

Et c'est pas évident de voir que $\tau_1$ et $\tau_{-1}$ vérifie l'équation en question ! (enfin surtout si on veut généraliser)