Salut

Montrer que (Z/pZ)* est cyclique n'est pas une réponse à ta question?

Salut Monrow,

J'ai vu un truc de ce genre là aussi, mais je suis plus bien sûr de la définition de cyclique. On dit qu'un groupe est cyclique ssi il existe un élément générateur non ? Dans ce cas là oui c'est complètement équivalent à ma question, mais comment montrer que (Z/pZ)* est cyclique ?

oui ta définition du groupe cyclique est la bonne !

En fait pour p premier (Z/pZ)* est cyclique et en plus tu as le nombre de ses générateurs (éléments primitifs) qui est égal à avec la fonction indicatrice d'Euler (je pense que vous l'aviez étudié en sup en exo). Mais pour trouver ces générateurs c'est pas toujours trivial et il n'y a pas de méthode générale à ce que je sais.

La démo n'est pas triviale ^^ mais t'as deux solutions, je te donne le pdf pour lire la démo ou bien je te guide pour la trouver ^^

"en plus tu as le nombre de ses générateurs (éléments primitifs) qui est égal à "
-> Ca je l'ai lu sur internet ce matin en effet, par contre :
"je pense que vous l'aviez étudié en sup en exo"
-> bah non, je ne crois pas. C'est vrai que cette année j'en ai entendu parler plusieurs fois, sans savoir ce que c'est. Je sais enfin ^^
"Mais pour trouver ces générateurs c'est pas toujours trivial et il n'y a pas de méthode générale à ce que je sais."
-> j'ai également lu ça ce matin, en fait il y a une méthode de construction, mais elle est irréalisable en complexité (comme si on utilisait le théorème de wilson pour démontrer qu'un nombre est premier )
-> : voir partie "2.3 Construction d'un élément générateur"

"La démo n'est pas triviale ^^ mais t'as deux solutions, je te donne le pdf pour lire la démo  ou bien je te guide pour la trouver ^^"

Que ça soit pas trivial, quelque part je m'en doute, mais c'est non trivial à mon niveau ou ça me dépasse complètement ?
Parce que si c'est comme ça :   (voir théorème 6 : Tout sous-groupe fini du groupe multiplicatif d'un corps commutatif est cyclique. En particulier, le groupe multiplicatif F∗q d'un corps fini est cyclique.) j'avoue que j'ai pas tout suivi ...

Sinon je te montre tout de même mon exercice initial, pour peu je me complique la vie pour rien :

Soit p un nombre premier et k un entier naturel. Que vaut la somme :   ?


Donc sur quelques exemples je trouve : si k=0[p-1] alors par fermat on trouve (p-1) sinon on trouve 0.
Et mon raisonnement c'était, dans le cas ou k n'est pas divisible par p-1 : on considère un élément générateur a, alors tout x s'écrit
et donc on se ramène à une somme de progression géométrique : en multipliant cette somme par qui est non nul dans Z/pZ puisque k n'est pas divisible par (p-1)    on trouve   (encore fermat) et comme on est dans un corps et que est non nul, on a bien la somme nulle.

Mais dans mon raisonnement, j'utilise : "il existe un élément générateur". Ai-je bien le droit ?

oui je suis d'accord avec ta démo et donc là ça dépend du cours de votre prof ... Si il vous a dit que (Z/pZ)* est cyclique c'est bon (y a des profs qui l'admettent dans leurs cours) sinon il faut le montrer mais pour un exo normal, je pense que c'est abusé, puisque c'est un oral classique d'ENS ...

En sup on a pas de cours sur les Z/pZ, enfin pas trop. On a fait une petite fiche TD sur les groupes et sous groupes cycliques mais c'est tout. On a jamais trop parlé du corps Z/pZ.

Le truc c'est que mon exo vient pas de mon prof, il vient d'un recueil de khole que j'ai trouvé sur internet, un ancien élève de mon lycée qui est aujourd'hui (après avoir fait ULM justement) kholeur en MPSI et MP* à Louis-le-Grand je crois. Du coup tous les exo de mon formulaire sont soit niveau sup soit niveau spé. Celui là est plus niveau spé je pense (tout ce qui est Z/pZ est surtout vu en spé) mais il me semblait à ma portée, à condition d'admettre ce fichu résultat.

"mais pour un exo normal, je pense que c'est abusé"
La démonstration est si longue que ça ? Si tu as un bon lien pdf, je suis preneur, rien ne m'empêche de regarder si je comprend un peu la démo, mais je vais pas te faire perdre du temps à m'expliquer un truc pour lequel il doit sûrement me manquer quelques acquis (il y a sûrement des théorèmes d'algèbres que je verrai l'année prochaine seulement et qui sont indispensables à la démo non ?).
En attendant je garde l'exo de côté et je verrai bien si mon prof à venir nous place dans le cours que Z/pZ est cyclique.

En tout cas merci pour ton aide Monrow, encore une fois tu me sors d'une impasse

Oui, je te passe ce lien (corrigé d'un oral ENS) qui montre que (Z/pZ)* est cyclique

C'est pas la longueur de la démo qui pose problème mais plutôt la "technicité" qu'il faut avoir

Pour ce qui est des acquis, normalement un élève de prépa a les outils nécessaires (pas besoin de savoir trop la théorie des corps finis et tout ce qui va avec à mon avis)

C'est bizarre en fait que vous n'aviez pas vu ça en sup, c'est vrai qu'on approfondit ça en spé, mais on voit la plupart de ces notions en sup ..

Bon courage

Bonjour

Voilà un topic qui met à peu près en ordre cette histoire... Corps finis (Remise en ordre)

Bonjour Camélia

Merci pour ce lien. Cependant il y a encore des choses que je ne connais pas dans tout ce vocabulaire, j'espère que je verrai ça l'année prochaine. Je relirai alors le topic à ce moment là.

Pour l'instant je comprends l'énoncé du A sans pouvoir y répondre je pense. Et dans le B qu'est ce que la caractéristique d'un corps ? (L de caractéristique p)
De même je ne connais pas la notion de corps de décomposition ...
Bref, encore un peu au dessus de mon niveau, pas pour longtemps j'espère !

Merci tout de même à vous deux, je vais pour l'instant rédiger mon exercice en admettant que Z/pZ est cyclique, et j'espère que l'on démontreras en cours de spé les résultats proposé par Camélia.
Encore merci

J'en profite pour vous demander (il serait inutile d'ouvrir un nouveau topic pour cela) :

Vous confirmez bien que le mot "indempotent" n'existe pas et qu'il faut comprendre "idempotent" ?

Oui, oui, il faut comprendre idempotent!

La caractéristique de Z/pZ est p, mais il est sage d'attendre un peu!

Bonjour Camélia,

"il est sage d'attendre un peu!"
C'est ce que je me suis dit, mais j'ai lu un peu sur Internet ce genre de chose lors de mes recherches d'hier matin. En fait on montre que tout corps fini est isomorphe à un Z/pZ et donc la caractéristique d'un corps fini est le p en question, c'est ça ?

Non, il y a des corps finis qui ne sont pas isomorphes à un Z/pZ... En fait un corps fini a toujours éléments avec p premier et c'est CE p qui est la carectéristique. (Le plus petit entier m strictement positif tel que )

Cadeau: un corps ayant quatre éléments: Les éléments sont

Addition:

Désolée, départ intempestif... mais c'est lisible! Pour la multiplication: , 1 est élément neutre, et le reste comme d'habitude, avec impératif



Si tu ne comprends pas, je me tappe aussi le tableau de la multiplication!

Bonjour Camélia, Monrow,

Désolé de ne pas avoir répondu, comme je l'ai indiqué dans un sujet dans la partie "site", je ne reçois plus les notifications de réponses par mail !

Camélia : au risque de me tromper une seconde fois, je rectifie :
tout corps fini est isomorphe à un Z/pZ ou à un (Z/pZ)^n ? D'où le cardinal de p^n ?
Par exemple, le corps à 4 éléments, c'est en fait : (Z/2Z)x(Z/2Z) ou je divague complet ?
En tout cas ça marche pour l'addition. Après il faut que j'explicite la loi x que l'on peut mettre sur cet ensemble.

Monrow : Z/nZ tout ça j'ai vu, mais l'indicatrice d'Euler non. L'année prochaine sûrement non ?

plutôt ...

Sinon, je pense que oui, c'est normal de la voir l'année prochaine

NON!

Ni ni ne sont des corps avec les structures usuelles... On démontre que sur le groupe additif on peut définir une multiplication qui en fait un corps... C'est l'exemple du corps à 4 éléments que j'ai donné plus haut!

est l'ensemble des classes modulo . Comme la classe n'est certainement pas inversible, donc ce n'est pas un corps.

est l'ensemble des n-uplets formé de classes modulo p. Il est muni de l'addition habituelle



qui en fait un groupe additif commutatif.

Si on le munit de la multiplication naturelle



on obtient un anneau commutatif qui n'est pas un corps car (1,0,0,...,0)(0,1,0,...,0)=(0,...,0).

Ce que j'ai dit c'est que sur ce groupe commutatif on peut toujours définir une multiplication qui en fait un corps...

désolé, j'ai dit une bêtise

> monrow ca arrive... aux meilleurs!

Salut

Justement en ce moment je me posais des questions similaires, qui m'ont amené à me renseigner sur pas mal de nouvelles notions . En particulier ce document :

http://perso.telecom-paristech.fr/~rioul/documents/200609corpsfinis.pdf

m'a permis de m'en sortir sur un problème de recherche de racines cubiques modulo sur lequel je butais (à savoir, je m'étais aperçu que l'application cube modulo un nombre premier est bijective si et seulement si ce nombre est 3 ou si il est de la forme 3k-1).

Pour répondre à ton problème initial qui était l'existence d'un élément primitif : oui, on peut le démontrer sans faire appel à des notions trop abstraites . Exit donc les "gros" mots.

Je ne fais que résumer les différentes étapes de la démonstration, mais elles ne font appel qu'à de l'arithmétique élémentaire: d'abord, on montre que si p est premier, alors en élevant un élément non-nul de Z/pZ à ses puissances successives, on tombera toujours à un moment donné sur 1 (en fait, c'est la première question à se poser, puisque ça n'a rien d'évident à priori ...) : ce qui est crucial c'est que tous les éléments non nuls soient inversibles. En effet comme la suite des puissances ne peut prendre qu'un nombre fini de valeurs différentes, il existe deux exposants i et j tels que a^i=a^j, et en multipliant l'égalité par l'inverse de a un nombre suffisant de fois, on obtient a^(i-j)=1. C'est la notion d'ordre d'un élément, que tu as découvert par expérimentation : le plus petit exposant non nul tel qu'on retombe sur 1.
Toujours en utilisant l'inversibilité, on montre que dans la suite des puissances 1,a,a² ... jusqu'à a^(ordre de a - 1), il n'y a pas deux éléments identiques.
Par suite, cet ordre est nécessairement inférieur au nombre de valeurs distinctes que peuvent prendre les puissances successives d'un élément non nul, c'est-à-dire p-1 . Il existe donc un élément d'ordre maximal.
Par diverses considérations sur cet élément (que je ne détaillerai pas, mais la démonstration du document plus haut est très claire), on montre que l'ordre de tout élément non nul divise cet ordre maximal.
Et c'est là qu'intervient le tour de passe-passe final :
- m est l'ordre maximal.
- l'ordre o d'un élément divise m, donc il existe k : m = ko .
- soit a d'ordre o, alors a^o = 1 et par conséquent a^m = a^ko = (a^o)^k = 1^k = 1.
- donc tout élément non nul est racine du polynôme X^m-1 .
- soit g un élément d'ordre m (un tel élément existe !) : on sait que les puissances 1,g,g² ... jusqu'à g^(m-1) sont deux à deux distinctes, ce sont donc exactement les racines du polynôme X^m-1.
- donc tout élément non nul est une puissance de g.
- or il existe p-1 éléments non nuls.
- donc il existe p-1 puissances de g 2à2 distinctes.
- donc g est d'ordre p-1, c'est-à-dire primitif.

Ainsi il existe bien toujours au moins un élément primitif, et de plus l'ordre de tout élément non-nul divise p-1 (ce qui permet de retrouver le petit théorème de Fermat).

Pour le problème que je m'étais posé, je suis d'ailleurs allé un peu plus loin que le document, en montrant en plus que pour tout diviseur d de p-1, il existe un élément d'ordre d.

Boujour Hoan,

Excuse moi de répondre si tard. J'ai lu une première fois ton message sans tout comprendre, si bien que je n'ai pas répondu, tout en laissant l'onglet ouvert pour pouvoir y revenir calmement. C'est ce que j'ai fait aujourd'hui, et j'ai tout compris (excepté les morceaux de démonstrations qui n'ont pas été détaillé bien sûr). Comme quoi mon prof avait raison : parfois il suffit de quelques jours de maturité pour que les choses paraissent plus claires.

Quant au pdf, je n'ai lu encore que l'introduction, mais ton message répond déjà bien à mes questions

Je te remercie pour ton intervention
Encore merci à Camélia et Monrow par ailleurs

Mais de rien ^^

(ah oui la technique de l'onglet ... chez moi y'en a tellement que je sais même plus ce que j'avais en tête en les ouvrant. Je les collectionne...)

Je n'ai pas grand mérite, il se trouve juste que je suis en plein dans le vif du sujet en ce moment... C'est d'ailleurs plus un hasard qu'autre chose si j'ai déterré ce document ... J'en ai des tonnes que j'ai accumulé en cherchant ça et là des idées pour divers problèmes costauds où il me fallait de l'aide, mais au final je ne prends jamais vraiment le temps de les potasser, je les ouvre, les survole, et ça va direct dans la case "hors-sujet, on fout ça sur un coin du disque dur au cas où ça servirait un jour et on passe à autre chose". Comme quoi, l'illumination est peut-être toute proche !

A vrai dire je suis tombé sur ce forum en cherchant un moyen, étant donné un élément primitif g et un élément a, de trouver à quelle puissance de g correspond a, autrement dit de résoudre g^x=a modulo p (d'ailleurs si ça t'intéresse j'en ai trouvé un pour p-1 = une puissance de deux). Sur d'autres je n'ai fait que passer, mais là, même si je n'ai toujours pas ma réponse, ç'aurait été criminel de ne pas aider quelqu'un qui se pose exactement la question que moi à à peine deux jours d'intervalle (j'insiste sur le exactement, c'est rare). Surtout que j'avais la chose bien fraîche en tête. Et puis ça rassure de voir qu'on n'est pas la seule personne sur cette planète à se poser ce genre de question ^^

Bon sinon je sais pas si tu as dépassé l'intro maintenant, mais la partie qui t'intéresse (à savoir, que l'ordre d'un élément divise l'ordre maximal) et que j'ai passé sous silence dans ma démo correspond à la page 11 du document (la page 17 du pdf). Après libre à toi de lire la suite, moi j'y ai appris pas mal de choses, et pas mal de notions m'effraient moins maintenant, mais j'avoue m'être arrêté aux calculs modulo des polynômes, là j'ai du mal... Enfin un de ces quatre je m'y mettrai peut-être, y'a pas grand chose qui résiste à un papier, un crayon, un grand bol de café et un peu de détermination.

Ah une petite remarque : de mémoire je sais plus si c'est démontré dans l'article, mais il faut avoir la propriété que les polynômes de degré m dans Z/pZ admettent au plus m racines, comme c'est le cas pour les polynômes "classiques" . Mais bon ça je pense que c'est une démonstration courante ... pis là ça confine au chipotage...

Bon et puis on sait jamais : Tonelli-Shanks, tu connais ? (c'est pour les racines carrées modulo). En théorie c'est fait pour les modulo premiers, mais tu sais si ça marche aussi dans les modulo p^n ? (enfin en prenant un élément inversible, c'est-à-dire non multiple de p). Autre question : l'extraction de racine cubique. Pour les éléments inversibles, j'ai trouvé des méthodes qui marchent plutôt bien, en combinant plusieurs idées, dont une adaptation de Tonelli-Shanks ; mais pour les éléments non-inversibles, il y en a qui admettent des racines cubiques, et c'est là-dessus que je bute. C'est pas aussi simple que je pensais au début...Par exemple dans 103^2, 0 admet un paquet de racines cubiques (j'ai la flemme de les compter). Quand est-ce qu'un élément non inversible admet une ou plusieurs racines ? Comment les construire ? (en supposant qu'on sache répondre à ces questions quand l'élément est inversible).

Bonjour

> Hoan En lisant tes posts, il me semble que tu manques de quelques résultats sur les groupes cycliques.

La clef est: Un groupe d'ordre n est cyclique si et seulement si il possède exactement un seul sous-groupe d'ordre d pour chaque diviseur strict d de n.

Ca répond aux questions que tu te poses sur les racines des inversibles (en sachant que le groupe multiplicatif d'un corps fini est cyclique)

Pour les Z/nZ qui ne sont pas des corps la meilleure tactique est d'utiliser d'abord un théorème chinois, puis de regarder...