Équation sur $\mathbb F_p$
dans Arithmétique
On a donc la généralisation suivante :
Pour tout $n\geq 2$, si $x^2+x+1=0$ a une solution dans $\Z/n\Z$, alors $x^2+3=0$ a une solution dans $\Z/n\Z$.
La réciproque est vraie pour tout $n$ impair mais fausse pour $n$ pair (prendre $n=2$).
Pour tout $n\geq 2$, si $x^2+x+1=0$ a une solution dans $\Z/n\Z$, alors $x^2+3=0$ a une solution dans $\Z/n\Z$.
La réciproque est vraie pour tout $n$ impair mais fausse pour $n$ pair (prendre $n=2$).
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
$$X^2+X+1\text{ a une racine dans }\Z/p\Z\Leftrightarrow p=1,7\bmod 12.$$
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 ?
Mais quand je vois un carré modulo $p$, mon sang ne fait qu'un tour !
Tu fais comment sans réciprocité quadratique ?
$$(x^2+x+1)(x-1)$$
Soit $a$ l'ordre de $x$ tel que $x^2+x+1=0\bmod p$.
Comme $x^3=1$, $a$ divise $\gcd(3,p-1)$.
Or, $p\geq 5$ donc $x\neq 1$ et $a=3$.
Donc $3$ divise $p-1$.
Pour la réciproque, soit $y$ un générateur de $(\Z/p\Z)^\times$.
Alors $x=y^{(p-1)/3}$ vérifie $x\neq 1$ et $x^3=1$ donc $x^2+x+1=0\bmod p$.
$$
\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) ?
Je résume mon post précédent.
$$-3\text{ carré modulo }p\Leftrightarrow X^2+X+1 \text{ a une racine }\Leftrightarrow p=1\bmod 3.$$
@flipflop : Après manger. ;-)
$$X^2+X-1\text{ a une racine dans }\Z/p\Z\Leftrightarrow p=\pm 1\bmod 5.$$
Peut-on se passer de l'utilisation de $(\Z/p\Z)^*$ cyclique ? Peut-on attraper un élément d'ordre 3 autrement ?
Alors $(3k)^k$ est d'ordre $3$.
$X^k-1$ a au plus $k$ racines donc il existe $y$ INVERSIBLE tel que $y^k\neq 1\bmod p$.
Alors $y^k$ est d'ordre $3$.
$$
\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).
D'où $\#M=\dfrac{p-1}{3}$ et $\#B=\dfrac{2(p-1)}{3}$.
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$
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^*$.
On cherche $y$ tel que $y^{(p-1)/q^r}\neq 1$ pour tout $1\leq r\leq k$.
Alors $y^{(p-1)/q^k}$ est d'ordre $q^k$.
On répète ça pour tous les $q$ divisant $p-1$ et un petit produit donne un générateur de $(\mathbb F_p)^\times$.
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.
J'ai tapé ça avant de me coucher pour coucher ce que j'avais compris de ton "Do you see what I mean ?".
Avec mes conditions avec $r$, je ne voyais pas trop les ensembles $M$ et $B$, même en comptant les moutons dans mon lit.
Pour le reste, notons $\alpha=\frac{p-1}{q^k}$ et $y$ tel que $y^{\alpha}\neq 1$.
On aimerait bien que l'ordre de $y^\alpha$ soit $q^k$.
Pour cela, il suffit de montrer que $(y^{\alpha})^{q^{k-1}}\neq 1$.
Je pense que c'est classique et qu'il faut développer un truc du type $(1+u)^q$... mais je n'ai pas conclu. :-S
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.
Plus facile en effet !
Ben j'ai utilisé la loi de réciprocité quadratique parce qu'on a des solutions quand $5$ divise $p+1$.
J'ai quand même une autre idée mais je n'ai l'ai pas exploitée.
Si $y\neq 1$ est tel que $y^5=\pm 1$, alors $\pm(y+y^{-1})$ est solution de $x^2+x-1$.
$$\#B=(q-1)\#M$$
ce qui permet d'éviter les tirages trop nombreux.
En tout cas, (tu) pour cette construction d'un générateur de $(\mathbb F_p)^\times$.
si $y^5 = 1$ et $y \ne 1$, on note $\tau_1 = y+y^4$ et $\tau_{-1} = y^2 +y^3$ ... on dirai que c'est les racines de $x^2+x-1$, non ?
Mais surtout, on fait quoi si $y$ n'existe pas ?
Si $y$ n'existe pas, beh on passe dans $\mathbb{F}_{p^4}$ comme ça on a un $y$ :-D et on utilise : soit $z \in \mathbb{F}_{p^4}$, alors $z \in \mathbb{F}_p$ si et seulement si $z^p=z$ pour voir quand les $\tau_i$ sont dans le corps de base.
Fais gaffe, j'ai pas trop vérifié ce que je dis mais je pense que ça marche bien !
Soit $y$ une racine primitive cinquième de l'unité dans une certaine extension (cyclotomique) de $\mathbb F_p$.
Alors $y+y^{-1}=y+y^4$ est racine de $X^2+X-1$ qui a donc une racine dans $\mathbb F_p$ si et seulement si $(y+y^4)^p=y^p+y^{4p}=y+y^4$.
En regardant les valeurs de $p$ modulo $5$, on obtient assez facilement
$$X^2+X-1\text{ a une racine dans }\mathbb F_p\Leftrightarrow p=\pm 1\bmod 5\text{ ou }p=5.$$
Remarque : $p=5$ est l'unique cas où la racine est double.
Bon bah il faut faire $x^2+x+2$ :-D
PS :
Sinon tu peux dire aussi que $5$ est un carré modulo $p$ si et seulement si $x^2+x-1$ a deux racines dans $\mathbb{F}_p$ et enchainer avec ton équivalence. ($p \ne 5$)
Ok pour $x^2+x+2$ mais plus tard (je dois décortiquer une preuve de pappus d'abord)...
$$X^2+X+2\text { a une racine modulo }p\Leftrightarrow p=1,2,4\bmod 7\text{ ou }p=7.$$
Je vais regarder en considérant $\Q(\sqrt{-7})\subset \Q(\zeta_7)$. B-)
Sinon faut faire pareil $\tau_1$, $\tau_{-1}$
Je viens de me rappeler des sommes de Gauss : $$\tau_1=z+z^2+z^4,\quad \tau_{-1}=z^3+z^5+z^6$$ avec $z^7=1,\ z\neq 1$.
$$X^2+X+\frac{1-p^*}{4}.$$
Et comment on fait avec la caractéristique $p$ et tout, tu penses aux Frobenius !
C'est une question ?