Répondre à la discussion
Affichage des résultats 1 à 26 sur 26

generateurs de (Z/Zp)*



  1. #1
    jeanlouisb

    Smile generateurs de (Z/Zp)*


    ------

    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

    -----

  2. Publicité
  3. #2
    zinia

    Re : generateurs de (Z/Zp)*

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

  4. #3
    matthias

    Re : generateurs de (Z/Zp)*

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

  5. #4
    zinia

    Re : generateurs de (Z/Zp)*

    Autant pour moi, je me suis embrouillé.

  6. #5
    GuYem

    Re : generateurs de (Z/Zp)*

    Citation 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.
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  7. A voir en vidéo sur Futura
  8. #6
    jeanlouisb

    Re : generateurs de (Z/Zp)*

    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

  9. Publicité
  10. #7
    µµtt

    Re : generateurs de (Z/Zp)*

    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.

  11. #8
    martini_bird

    Re : generateurs de (Z/Zp)*

    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 . En d'autres termes, l'équation admet deux solution tandis que l'équation n'en admet pas.

    Si , alors et l'on a : 2 ne peut engendrer .

    Si , 2 n'est pas un carré. Si l'on avait , alors est l'un quelconque des générateurs de , soit , contradiction. On a donc et 2 engendre .

    Cordialement.

    PS : remarque inutile : un élément ne génère pas un groupe, il l'engendre.
    « Angle éternel, la terre et le ciel, pour bissectrice, le vent. » Garcia Lorca

  12. #9
    µµtt

    Re : generateurs de (Z/Zp)*

    Citation Envoyé par martini_bird
    PS : remarque inutile : un élément ne génère pas un groupe, il l'engendre.
    Pff, pinaillage ridicule

  13. #10
    jeanlouisb

    Re : generateurs de (Z/Zp)*

    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

  14. #11
    martini_bird

    Re : generateurs de (Z/Zp)*

    Tu réponds à qui, jeanlouisb ?
    Citation 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...)
    « Angle éternel, la terre et le ciel, pour bissectrice, le vent. » Garcia Lorca

  15. #12
    jeanlouisb

    Re : generateurs de (Z/Zp)*

    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.

  16. Publicité
  17. #13
    jeanlouisb

    Re : generateurs de (Z/Zp)*

    Citation 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 . En d'autres termes, l'équation admet deux solution tandis que l'équation n'en admet pas.

    Si , alors et l'on a : 2 ne peut engendrer .

    Si , 2 n'est pas un carré. Si l'on avait , alors est l'un quelconque des générateurs de , soit , contradiction. On a donc et 2 engendre .

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

  18. #14
    rvz

    Re : generateurs de (Z/Zp)*

    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,
    par le théorème d'euler.
    Si a est un carré, alors a = b^2, et donc
    Après, il n'y a plus qu'à compter les éléments.
    Nombre de solutions de 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 (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

  19. #15
    martini_bird

    Re : generateurs de (Z/Zp)*

    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, n'implique pas nécessairement que : c'est l'erreur de mon raisonnement.

    Cordialement.
    « Angle éternel, la terre et le ciel, pour bissectrice, le vent. » Garcia Lorca

  20. #16
    jeanlouisb

    Re : generateurs de (Z/Zp)*

    Citation 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,
    par le théorème d'euler.
    Si a est un carré, alors a = b^2, et donc
    Après, il n'y a plus qu'à compter les éléments.
    Nombre de solutions de 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 (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.

  21. #17
    jeanlouisb

    Re : generateurs de (Z/Zp)*

    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.
    Dernière modification par martini_bird ; 18/04/2006 à 20h12.

  22. #18
    jeanlouisb

    Re : generateurs de (Z/Zp)*

    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;

  23. Publicité
  24. #19
    martini_bird

    Re : generateurs de (Z/Zp)*

    Citation 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, est bien le nombre de nombres premiers à n.

    Cordialement.
    « Angle éternel, la terre et le ciel, pour bissectrice, le vent. » Garcia Lorca

  25. #20
    rvz

    Re : generateurs de (Z/Zp)*

    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

  26. #21
    rvz

    Re : generateurs de (Z/Zp)*

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

    __
    rvz

  27. #22
    Moma

    Re : generateurs de (Z/Zp)*

    Bonjour,

    Citation 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 et donc mod p (on utilise le symbole de legendre)

    Or (c'est la formule qui traduit la propriété énoncée par Martini).
    Mais mod 2 justement !

    Et on arrive à mod p .


    Amicalement,
    Moma

  28. #23
    jeanlouisb

    Re : generateurs de (Z/Zp)*

    Ici, on a et donc 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.

  29. #24
    Moma

    Re : generateurs de (Z/Zp)*

    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)* : . (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é et donc

    Si a n'est pas un carré : et donc
    qui est une racine carré de 1, et donc égal +/-1.
    Or w est un générateur, donc 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é
    Dernière modification par Moma ; 20/04/2006 à 09h27.

  30. Publicité
  31. #25
    rvz

    Re : generateurs de (Z/Zp)*

    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

  32. #26
    jeanlouisb

    Re : generateurs de (Z/Zp)*

    Citation 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)* : . (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é et donc

    Si a n'est pas un carré : et donc
    qui est une racine carré de 1, et donc égal +/-1.
    Or w est un générateur, donc 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

Sur le même thème :

Discussions similaires

  1. Problème de générateurs de tension
    Par BL60 dans le forum Électronique
    Réponses: 5
    Dernier message: 27/12/2007, 13h40
  2. Générateurs en série
    Par Nashki dans le forum Physique
    Réponses: 3
    Dernier message: 29/09/2007, 15h34
  3. Générateurs de Z/pZ*
    Par Coco Beach dans le forum Mathématiques du supérieur
    Réponses: 10
    Dernier message: 08/09/2007, 16h34
  4. URGENT association de generateurs
    Par eldiablodu331 dans le forum Physique
    Réponses: 10
    Dernier message: 30/12/2006, 09h44
  5. TIPE Mathématiques : générateurs
    Par Aragorn_destroy dans le forum TPE / TIPE et autres travaux
    Réponses: 2
    Dernier message: 05/05/2006, 14h50