generateurs de (Z/Zp)*

**jeanlouisb** · 15/04/2006, 15h44

si p premier et p=4k+1
Je souhaiterais montrer que 2 est un générateur de (Z/Zp)*
si et seulement si k est impair.
Merci d'avance à celui qui pourra m'aider.
Jean-Louis

invite636fa06b · 15/04/2006, 16h38

Envoyé par jeanlouisb

si p premier et p=4k+1
Je souhaiterais montrer que 2 est un générateur de (Z/Zp)*
si et seulement si k est impair.

Quelque chose m'échappe ..
Si p est premier tous les éléments de (Z/Zp)* autres que 1 sont générateurs.

invitec314d025 · 15/04/2006, 16h47

Envoyé par zinia

Quelque chose m'échappe ..
Si p est premier tous les éléments de (Z/Zp)* autres que 1 sont générateurs.

Non, ils sont générateurs du groupe additif (Z/pZ) pas nécessairement du groupe multiplicatif (Z/pZ)*. Il suffit de regarder Z/17Z pour s'en convaincre.

invite636fa06b · 15/04/2006, 17h05

Autant pour moi, je me suis embrouillé.

A voir en vidéo sur Futura · Aujourd'hui

invitedf667161 · 16/04/2006, 00h47

Envoyé par zinia

Quelque chose m'échappe ..
Si p est premier tous les éléments de (Z/Zp)* autres que 1 sont générateurs.

Comme quoi celle-là, tout le monde la fait. Il vaut toujours mieux préciser la loi quand on parle de Z/machinZ.

**jeanlouisb** · 16/04/2006, 05h16

il s'agit bien sûr du groupe multiplicatif (Z/pZ)* qui a p-1 élément et non pas du groupe additif (Z/pZ) qui lui a p éléments.
On sait qu'il est cyclique et donc isomorphe à Z/(p-1)Z additif généré par 1.
Si on a un générateur w on les a tous, les autres étant w^q avec q premier avec p-1.
On sait déjà par FERMAT que 2^4k=1; et donc que 2^2k=+ou-1 (car (Z/Zp) est un corps fini.
En fait je voudrais montrer que 2^2k=(-1)^k.
Je sais le faire en utilisant une astuce qui consiste qui consiste à montrer que (2^2k)(2k)!=((-1)^k)(2k)! car (2k)!différent de 0 modulo p (p=4k+1>2k).
Ceci en regroupant les 2k "2" avec les 2k termes (2k-i) de (2k);Et le résultat tombe tout seul.
Mais je voudrais savoir si quelqu'un saurait le faire sans cette astuce en utilisant le cours sur les générateurs d'un groupe cyclique ou bien la théorie des corps finis ou les deux ou autre chose.
Merci d'avance à celui qui pourrait m'aider.
Jean-Louis

inviteca3a9be7 · 17/04/2006, 12h43

Salut,

Tu es sûr de ce résultat ???

Je croyais que le fait de savoir si 2 était ou non un générateur de Z/pZ* était un problème non résolu.

**invite4793db90** · 17/04/2006, 12h56

Salut,

je propose une approche différente par la théorie des résidus quadratiques : le lemme de Gauss a pour conséquence que 2 est résidu quadratique modulo p ssi $\text{[math]}$ . En d'autres termes, l'équation $\text{[math]}$ admet deux solution tandis que l'équation $\text{[math]}$ n'en admet pas.

Si $\text{[math]}$ , alors $\text{[math]}$ et l'on a $\text{[math]}$ : 2 ne peut engendrer $\text{[math]}$ .

Si $\text{[math]}$ , 2 n'est pas un carré. Si l'on avait $\text{[math]}$ , alors $\text{[math]}$ où $\text{[math]}$ est l'un quelconque des générateurs de $\text{[math]}$ , soit $\text{[math]}$ , contradiction. On a donc $\text{[math]}$ et 2 engendre $\text{[math]}$ .

Cordialement.

PS : remarque inutile : un élément ne génère pas un groupe, il l'engendre.

inviteca3a9be7 · 17/04/2006, 13h03

Envoyé par martini_bird

PS : remarque inutile : un élément ne génère pas un groupe, il l'engendre.

Pff, pinaillage ridicule

**jeanlouisb** · 17/04/2006, 13h08

Salut,
Non, je ne suis pas sûr.
Je suis seulement sûr que si p=4k+1 alors si k est pair 2 ne peut pas être générateur car 2^2k=1 donc 2 n'est pas générateur (il ne génère que 2k éléments).
Et si k est impair comme 2^k=-1 (2^4k=1) il me semble qu'on ne peut pas rencontrer 1 comme reste avant 2k sinon par périodicité on aurait aussi 2^k=1?Et ds ce cas 2 serait générateur.
Pour les autres p (congrus à 3 modulo 4) je ne sais pas.
Merci
Jean-Louis

**invite4793db90** · 17/04/2006, 13h12

Tu réponds à qui, jeanlouisb ?

Envoyé par µµtt

Pff, pinaillage ridicule

Ben j'ai bien dit que c'était une remarque inutile...

(C'est ça quand on a été traumatisé en sup...)

**jeanlouisb** · 17/04/2006, 13h34

Je répondais à uutt 2mn avant d'avoir lu ta réponse,martini.
Je ne connais pas la théorie de résidus quadratiques, néanmoins je vais regarder attentivement ta réponse et je t'en remercie.
jeanlouisb.

**jeanlouisb** · 18/04/2006, 16h46

Envoyé par martini_bird

Salut,

je propose une approche différente par la théorie des résidus quadratiques : le lemme de Gauss a pour conséquence que 2 est résidu quadratique modulo p ssi $\text{[math]}$ . En d'autres termes, l'équation $\text{[math]}$ admet deux solution tandis que l'équation $\text{[math]}$ n'en admet pas.

Si $\text{[math]}$ , alors $\text{[math]}$ et l'on a $\text{[math]}$ : 2 ne peut engendrer $\text{[math]}$ .

Si $\text{[math]}$ , 2 n'est pas un carré. Si l'on avait $\text{[math]}$ , alors $\text{[math]}$ où $\text{[math]}$ est l'un quelconque des générateurs de $\text{[math]}$ , soit $\text{[math]}$ , contradiction. On a donc $\text{[math]}$ et 2 engendre $\text{[math]}$ .

Cordialement.

PS : remarque inutile : un élément ne génère pas un groupe, il l'engendre.

Ce n'est pas toujours vrai que 2^2k=w^4k=1 implique 2=w².
Prendre p=17 ; w=3,10,5,ou 11. Seul w=11 correspond à
2=w².
mieux, 4 qui est un carré n'est pas le carré d'un w mais le carré de 2 qui n'est pas générateur.
Finalement je pense que pour montrer 2^2k=(-1)^k il faut dans tous les cas passer par (2^2k)(2k)!=((-1)^k)(2k)!

invite6b1e2c2e · 18/04/2006, 17h24

Dans ton exemple, tu peux peut-être essayer w = 6, non ?
En fait, tu as souvent, voire très souvent que w et -w sont 2 solutions différentes de X^2 = w^2.
En fait, si w = -w, c'est que 2w = 0, donc que w = 0 si tu n'es pas en caractéristique 2, et donc, là, effectivement, il n'y a qu'une solution....

Si p est un premier impair :
En gros, tu sais que si a est non nul,
$\text{[math]}$ par le théorème d'euler.
Si a est un carré, alors a = b^2, et donc $\text{[math]}$
Après, il n'y a plus qu'à compter les éléments.
Nombre de solutions de $\text{[math]}$ ne peut pas être supérieur à (p-1)/2, parce que Fp est un corps.
Mais, tu as exactement p-1 nombres dans Fp*, et donc l'ensemble de leur carré A est de taille (p-1)/2. En effet, si x^2 = y^2, alors (x-y)(x+y) = 0, donc x = y ou x = -y car Fp est intègre. Donc c'est ok, n'est ce pas.

Du coup, a est un carré dans Fp ssi $\text{[math]}$ (Au passage, sinon, ça vaut -1)

Bon, maintenant, il me semble que Martini a craqué, parce que je suis quasi sûr que c'est pas parce qu'un nombre n'est pas un carré qu'il engendre Fp*. Un exemple, pour p =13, tu as que p-1 = 12 = 3*4.
On peut vérifier sans mal que 5 n'est pas un carré, mais que 5^4 = 1

Cela dit, je crois me souvenir d'un truc comme ça effectivement? Mais je n'arrive pas à mettre le doigt dessus. Je crois qu'il y a des choses à regarder dans le Michel Demazure, Cours d'arithmétique et cryptographie, ou quelque chose comme ça. Excellente introduction à la loi de réciprocité quadratique et aux usages pratiques en algorithme de primalité.

__
rvz

**invite4793db90** · 18/04/2006, 19h08

Salut,

Bon, maintenant, il me semble que Martini a craqué, parce que je suis quasi sûr que c'est pas parce qu'un nombre n'est pas un carré qu'il engendre Fp*.

Oui, comme le dit jeanlouisb, $\text{[math]}$ n'implique pas nécessairement que $\text{[math]}$ : c'est l'erreur de mon raisonnement.

Cordialement.

**jeanlouisb** · 18/04/2006, 19h41

Envoyé par rvz

Dans ton exemple, tu peux peut-être essayer w = 6, non ?
En fait, tu as souvent, voire très souvent que w et -w sont 2 solutions différentes de X^2 = w^2.
En fait, si w = -w, c'est que 2w = 0, donc que w = 0 si tu n'es pas en caractéristique 2, et donc, là, effectivement, il n'y a qu'une solution....

Si p est un premier impair :
En gros, tu sais que si a est non nul,
$\text{[math]}$ par le théorème d'euler.
Si a est un carré, alors a = b^2, et donc $\text{[math]}$
Après, il n'y a plus qu'à compter les éléments.
Nombre de solutions de $\text{[math]}$ ne peut pas être supérieur à (p-1)/2, parce que Fp est un corps.
Mais, tu as exactement p-1 nombres dans Fp*, et donc l'ensemble de leur carré A est de taille (p-1)/2. En effet, si x^2 = y^2, alors (x-y)(x+y) = 0, donc x = y ou x = -y car Fp est intègre. Donc c'est ok, n'est ce pas.

Du coup, a est un carré dans Fp ssi $\text{[math]}$ (Au passage, sinon, ça vaut -1)

Bon, maintenant, il me semble que Martini a craqué, parce que je suis quasi sûr que c'est pas parce qu'un nombre n'est pas un carré qu'il engendre Fp*. Un exemple, pour p =13, tu as que p-1 = 12 = 3*4.
On peut vérifier sans mal que 5 n'est pas un carré, mais que 5^4 = 1

Cela dit, je crois me souvenir d'un truc comme ça effectivement? Mais je n'arrive pas à mettre le doigt dessus. Je crois qu'il y a des choses à regarder dans le Michel Demazure, Cours d'arithmétique et cryptographie, ou quelque chose comme ça. Excellente introduction à la loi de réciprocité quadratique et aux usages pratiques en algorithme de primalité.

__
rvz

Bien sûr il y a (p-1)/2 carré dans Fp* et autant de "non carré" et en général il y a beacoup moins de générateurs
puisqu'il y en a phi(p-1) c'est à dire autant que de q compris entre 2 et p-1 et premiers avec p-1.
Pour mémoire phi=indicatrice d'Euler.

**jeanlouisb** · 18/04/2006, 19h50

J'avais oublié de dire que si tu es dans un corps tu as toujours x²=w² ssi x²-w²=0 ssi (x-w)(x+w)=0 ssi x=w ou x=-w car il est effectivement intégre.

EDIT : Inutile de citer chaque fois l'intégralité du message. /martini_bird.

**jeanlouisb** · 18/04/2006, 20h23

Autant pour moi j'ai écrit une bétise: phi(p-1) est le nombre de nombres premiers entre 2 et p-1; il est bien sûr encore plus petit que le nb de q premiers avec p-1 qui lui même est inférieur au nb de carrés;

**invite4793db90** · 18/04/2006, 22h09

Envoyé par jeanlouisb

Autant pour moi j'ai écrit une bétise: phi(p-1) est le nombre de nombres premiers entre 2 et p-1; il est bien sûr encore plus petit que le nb de q premiers avec p-1 qui lui même est inférieur au nb de carrés;

Non non, $\text{[math]}$ est bien le nombre de nombres premiers à n.

Cordialement.

invite6b1e2c2e · 19/04/2006, 11h43

Tu es sûr ? En tout cas, c'est clair qu'il y a exactement k générateurs, où k est le nombre de nombres premiers à p-1, à cause de la structure cyclique de Fp*.

__
rvz

invite6b1e2c2e · 19/04/2006, 11h50

Euh, en fait je suis d'accord avec Martini. J'avais pas vu son message...

__
rvz

invitead065b7f · 19/04/2006, 13h59

Bonjour,

Envoyé par jeanlouisb

En fait je voudrais montrer que 2^2k=(-1)^k.

Je vais reprendre un peu les idées de Martini_bird pour tenter de le montrer.
Ici, on a $\text{[math]}$ et donc $\text{[math]}$ mod p (on utilise le symbole de legendre)

Or $\text{[math]}$ (c'est la formule qui traduit la propriété énoncée par Martini).
Mais $\text{[math]}$ mod 2 justement !

Et on arrive à $\text{[math]}$ mod p .

Amicalement,
Moma

**jeanlouisb** · 19/04/2006, 22h46

Ici, on a $\text{[math]}$ et donc $\text{[math]}$ mod p (on utilise le symbole de legendre)

Bonjour
Je ne comprends pas pourquoi tu as (2/p)=2^2k (ou (2/p)=2^((p-1)/2)) D'où tiens-tu ce résultat? Tout ce qu'on sait dans le fil (cf. Martini) c'est que si 2=a² alors 2^2k=1 (FERMAT) mais pourquoi si 2 n'est pas un carré on a 2^2k=-1 ? ou encore pourquoi si 2^2k=1 alors 2 est un carré.
Par ailleurs j'ai vu que le lemme de Gauss dit que l'on a (2/p)=(-1)^((p²-1)/8)=(-1)^k Donc OK pour ça.

invitead065b7f · 20/04/2006, 09h24

Salut,

c'est un résultat classique sur le symbole de Legendre. Il est utilisé en particulier dans le test de primalité de Solovay-Strassen
Allons-y :

On va repartir d'un résultat de Gauss : un nombre est un carré dans Z/pZ ssi son "indice" est pair i.e ssi c'est une puissance paire d'un générateur (multiplicatif). On va montrer la propriété pour tout a dans (Z/pZ)* : $\text{[math]}$ . (remarque que le symbole de Legendre est parfois défini comme valant 0 en 0, et donc ce serait vrai pour Z/pZ entier)

Soit donc w un générateur de (Z/pZ)*.
Si a est un carré $\text{[math]}$ et donc $\text{[math]}$

Si a n'est pas un carré : $\text{[math]}$ et donc
$\text{[math]}$ qui est une racine carré de 1, et donc égal +/-1.
Or w est un générateur, donc $\text{[math]}$ ne peut valoir 1 car w est d'odre p-1 .
CQFD

Amicalement,
Moma

PS : les exposants sont des alpha.. On ne voit pas bien la différence avec les a, désolé

invite6b1e2c2e · 20/04/2006, 10h30

Par ailleurs, je l'avais aussi démontré en utilisant du simple dénombrement, c'est-à-dire sans utiliser que Fp* est cyclique.

Te voilà maintenant avec 2 jolies preuves sur les résidus quadratiques

__
rvz

**jeanlouisb** · 20/04/2006, 13h57

Envoyé par Moma

Salut,

c'est un résultat classique sur le symbole de Legendre. Il est utilisé en particulier dans le test de primalité de Solovay-Strassen
Allons-y :

On va repartir d'un résultat de Gauss : un nombre est un carré dans Z/pZ ssi son "indice" est pair i.e ssi c'est une puissance paire d'un générateur (multiplicatif). On va montrer la propriété pour tout a dans (Z/pZ)* : $\text{[math]}$ . (remarque que le symbole de Legendre est parfois défini comme valant 0 en 0, et donc ce serait vrai pour Z/pZ entier)

Soit donc w un générateur de (Z/pZ)*.
Si a est un carré $\text{[math]}$ et donc $\text{[math]}$

Si a n'est pas un carré : $\text{[math]}$ et donc
$\text{[math]}$ qui est une racine carré de 1, et donc égal +/-1.
Or w est un générateur, donc $\text{[math]}$ ne peut valoir 1 car w est d'odre p-1 .
CQFD

Amicalement,
Moma

PS : les exposants sont des alpha.. On ne voit pas bien la différence avec les a, désolé

Merci beaucoup à tous. Pour moi on a fait le tour de la question. Bonnes vacances de Paques à tous et bonne rentrée et bon courage pour les Parisiens; Je suis content d'avoir découvert votre Forum et ça sera plus facile et moins cher qd je serai rentré dans la région parisienne car là je n'ai pas l'ADSL.
jeanlouis

generateurs de (Z/Zp)*

generateurs de (Z/Zp)*

Re : generateurs de (Z/Zp)*

Re : generateurs de (Z/Zp)*

Re : generateurs de (Z/Zp)*

Re : generateurs de (Z/Zp)*

Re : generateurs de (Z/Zp)*

Re : generateurs de (Z/Zp)*

Re : generateurs de (Z/Zp)*

Re : generateurs de (Z/Zp)*

Re : generateurs de (Z/Zp)*

Re : generateurs de (Z/Zp)*

Re : generateurs de (Z/Zp)*

Re : generateurs de (Z/Zp)*

Re : generateurs de (Z/Zp)*

Re : generateurs de (Z/Zp)*

Re : generateurs de (Z/Zp)*

Re : generateurs de (Z/Zp)*

Re : generateurs de (Z/Zp)*

Re : generateurs de (Z/Zp)*

Re : generateurs de (Z/Zp)*

Re : generateurs de (Z/Zp)*

Re : generateurs de (Z/Zp)*

Re : generateurs de (Z/Zp)*

Re : generateurs de (Z/Zp)*

Re : generateurs de (Z/Zp)*

Re : generateurs de (Z/Zp)*

Discussions similaires

Problème de générateurs de tension

Générateurs en série

Générateurs de Z/pZ*

URGENT association de generateurs

TIPE Mathématiques : générateurs