Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
118 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Équation sur $\mathbb F_p$

Envoyé par gai requin 
Équation sur $\mathbb F_p$
l’an passé
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$).



Edité 2 fois. La dernière correction date de l’an passé et a été effectuée par Poirot.
Re: x^2+x+1=0 dans Z/pZ
l’an passé
A coup de réciprocité quadratique, on a donc pour tout premier $p\geq 5$,
$$X^2+X+1\text{ a une racine dans }\Z/p\Z\Leftrightarrow p=1,7\bmod 12.$$
Re: x^2+x+1=0 dans Z/pZ
l’an passé
@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 ?
Re: x^2+x+1=0 dans Z/pZ
l’an passé
Bien sûr !
Mais quand je vois un carré modulo $p$, mon sang ne fait qu'un tour !

Tu fais comment sans réciprocité quadratique ?
Re: x^2+x+1=0 dans Z/pZ
l’an passé
avatar
Gai requin,

$$(x^2+x+1)(x-1)$$
Re: x^2+x+1=0 dans Z/pZ
l’an passé
thumbs down

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$.



Edité 2 fois. La dernière correction date de l’an passé et a été effectuée par gai requin.
Re: x^2+x+1=0 dans Z/pZ
l’an passé
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) ?
Re: x^2+x+1=0 dans Z/pZ
l’an passé
avatar
@Gai requin : tu as une condition pour $x^2+x-1 = 0$ modulo $p$, combien de racine ?
Re: x^2+x+1=0 dans Z/pZ
l’an passé
@Claude :

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. winking smiley
Re: x^2+x+1=0 dans Z/pZ
l’an passé
@flipflop : c'est plus facile en fait.

$$X^2+X-1\text{ a une racine dans }\Z/p\Z\Leftrightarrow p=\pm 1\bmod 5.$$
Re: x^2+x+1=0 dans Z/pZ
l’an passé
avatar
Mais sans utiliser la réciprocité quadratique grinning smiley



Edité 1 fois. La dernière correction date de l’an passé et a été effectuée par flipflop.
Re: x^2+x+1=0 dans Z/pZ
l’an passé
Qui te dit que je l'ai utilisée ? cool smiley
Re: x^2+x+1=0 dans Z/pZ
l’an passé
@gai requin
Peut-on se passer de l'utilisation de $(\Z/p\Z)^*$ cyclique ? Peut-on attraper un élément d'ordre 3 autrement ?
Re: x^2+x+1=0 dans Z/pZ
l’an passé
On écrit $p=1+3k$.
Alors $(3k)^k$ est d'ordre $3$.
Re: x^2+x+1=0 dans Z/pZ
l’an passé
Hum : ton $3k$, c'est $-1$ (modulo $p$ of course) ; et tu prétends donc que ...
Re: x^2+x+1=0 dans Z/pZ
l’an passé
Mince !

$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$.



Edité 3 fois. La dernière correction date de l’an passé et a été effectuée par gai requin.
Re: x^2+x+1=0 dans Z/pZ
l’an passé
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).
Re: x^2+x+1=0 dans Z/pZ
l’an passé
L'image de $\varphi$ est non triviale et c'est un sous-groupe du groupe $U_3$ des racines troisièmes de l'unité donc c'est $U_3$.
D'où $\#M=\dfrac{p-1}{3}$ et $\#B=\dfrac{2(p-1)}{3}$.
Re: x^2+x+1=0 dans Z/pZ
l’an passé
@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^*$.
Re: x^2+x+1=0 dans Z/pZ
l’an passé
Soit $q$ un diviseur premier de $p-1$ et $k$ sa valuation.

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$.



Edité 1 fois. La derni&egrave;re correction date de l&rsquo;an pass&eacute; et a &eacute;t&eacute; effectu&eacute;e par gai requin.
Re: x^2+x+1=0 dans Z/pZ
l’an passé
@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.
Re: x^2+x+1=0 dans Z/pZ
l’an passé
Salut Claude.
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. confused smiley
Re: x^2+x+1=0 dans Z/pZ
l’an passé
@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.
Re: x^2+x+1=0 dans Z/pZ
l’an passé
$x^{3^{k-1}}=y^{p-1 \over 3}\neq 1$ donc $x$ est d'ordre $3^k$.

Plus facile en effet !
Re: x^2+x+1=0 dans Z/pZ
l’an passé
avatar
Gai requin : Et tu tu as fait comment avec $x^2+x-1$ ?
Re: x^2+x+1=0 dans Z/pZ
l’an passé
Salut flipflop.

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$.



Edité 1 fois. La derni&egrave;re correction date de l&rsquo;an pass&eacute; et a &eacute;t&eacute; effectu&eacute;e par gai requin.
Re: x^2+x+1=0 dans Z/pZ
l’an passé
@Claude : Je pense que pour $q$ premier diviseur quelconque de $p-1$,
$$\#B=(q-1)\#M$$
ce qui permet d'éviter les tirages trop nombreux.

En tout cas, thumbs down pour cette construction d'un générateur de $(\mathbb F_p)^\times$.
Re: x^2+x+1=0 dans Z/pZ
l’an passé
avatar
@Gai requin :

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 ?
Re: x^2+x+1=0 dans Z/pZ
l’an passé
J'ai dit la même chose plus haut non ? winking smiley

Mais surtout, on fait quoi si $y$ n'existe pas ?
Re: x^2+x+1=0 dans Z/pZ
l’an passé
avatar
Ah mince gai requin, j'avais pas bien compris ton message grinning smiley

Si $y$ n'existe pas, beh on passe dans $\mathbb{F}_{p^4}$ comme ça on a un $y$ grinning smiley 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 !
Re: x^2+x+1=0 dans Z/pZ
l’an passé
Trop bien. thumbs down

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.
Re: x^2+x+1=0 dans Z/pZ
l’an passé
avatar
Tu as remarqué que $x^2+x-1$ c'est un polynôme qui décrit l'anneau d'entier de $\Q(\sqrt{5})$ et que l'on a l'inclusion $\Q(\sqrt{5}) \subset \Q(\zeta_5)$ ?

Bon bah il faut faire $x^2+x+2$ grinning smiley

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$)



Edité 1 fois. La derni&egrave;re correction date de l&rsquo;an pass&eacute; et a &eacute;t&eacute; effectu&eacute;e par flipflop.
Re: x^2+x+1=0 dans Z/pZ
l’an passé
Merci Kronecker-Weber !

Ok pour $x^2+x+2$ mais plus tard (je dois décortiquer une preuve de pappus d'abord)...
Re: x^2+x+1=0 dans Z/pZ
l’an passé
Comme quoi, la réciprocité quadratique est très pratique !

$$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)$. cool smiley
Re: x^2+x+1=0 dans Z/pZ
l’an passé
avatar
Les Frobenius Alphonse les Frobenius grinning smiley

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



Edité 2 fois. La derni&egrave;re correction date de l&rsquo;an pass&eacute; et a &eacute;t&eacute; effectu&eacute;e par flipflop.
Re: x^2+x+1=0 dans Z/pZ
l’an passé
Petit malin ! winking smiley

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$.



Edité 1 fois. La derni&egrave;re correction date de l&rsquo;an pass&eacute; et a &eacute;t&eacute; effectu&eacute;e par AD.
Re: x^2+x+1=0 dans Z/pZ
l’an passé
avatar
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)
Re: x^2+x+1=0 dans Z/pZ
l’an passé
On a fait la loi de réciprocité quadratique pour les Gauss ! grinning smiley
Re: x^2+x+1=0 dans Z/pZ
l’an passé
De manière générale, $\tau_1$ et $\tau_{-1}$ sont racines de
$$X^2+X+\frac{1-p^*}{4}.$$
Re: x^2+x+1=0 dans Z/pZ
l’an passé
avatar
comment tu sais tout ça grinning smiley

Et comment on fait avec la caractéristique $p$ et tout, tu penses aux Frobenius !
Re: x^2+x+1=0 dans Z/pZ
l’an passé
Salut flipflop.
C'est une question ?
Re: x^2+x+1=0 dans Z/pZ
l’an passé
avatar
C'est $-23$ questions !
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 134 344, Messages: 1 293 751, Utilisateurs: 23 309.
Notre dernier utilisateur inscrit raoul.S.


Ce forum
Discussions: 4 938, Messages: 59 759.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page