Inscription / Connexion Nouveau Sujet
Niveau LicenceMaths 2e/3e a
Partager :

Ordre et générateur

Posté par
etuupmc
29-11-20 à 23:15

Bonsoir,

Voici des questions sur lesquelles je bloque:

Soit un entier k > 4:

1)  Déterminer l'ordre de 5 (mod. 2^{k}) dans (Z/2^{k}Z)* (on pourra s'aider du fait que la valuation 2-adique de 5 ^{2^{k-2}}-1 vaut k).

2) Montrer que (Z/2^{k}Z)* = {±5^{r} (mod. 2^{k}), 1 ≤ r ≤ 2^{k-2}}

Je vois bien que de l'indication de la première question on déduit que 5^{2^{k-2}} = 1 [2^{k}]. Mais à partir de là je bloque

Merci d'avance pour votre aide!

Posté par
etuupmc
re : Ordre et générateur 29-11-20 à 23:21

J'ai oublié une dernière question:

3) En déduire si (Z/2^{k}Z)* admet un générateur.

Posté par
GBZM
re : Ordre et générateur 30-11-20 à 09:58

Bonjour,

Tu vois donc que l'ordre de 5 divise 2^{k-2}. Est-ce que ce peut être un diviseur plus petit que  2^{k-2} ?

Posté par
etuupmc
re : Ordre et générateur 30-11-20 à 10:34

Oui, ça j'ai bien vu aussi. Les diviseurs de 2^{k-2} sont 2, 2^{2}, ... , 2^{k-3}, 2^{k-2}.
En notant d l'ordre de 5 (mod 2^{k}), je ne vois pas comment déterminer s'il y a un d diviseur de 2^{k-2} différent de 2^{k-2} tel que l'on a 5^{d}\equiv 1[2^{k}], c'est là que je bute

Posté par
GBZM
re : Ordre et générateur 30-11-20 à 10:53

Réfléchis mieux, tu as tous les éléments et tu y es presque.

Posté par
etuupmc
re : Ordre et générateur 30-11-20 à 11:39

Ai-je le droit de diviser une congruence par une autre?
Par exemple, je sais par le théorème d'Euler que 5^{2^{k-1}}\equiv 1[2^{k}]. Et si je divise cette congruence par 5^{2^{k-2}}\equiv 1[2^{k}], j'ai comme résultat 5\equiv 1[2^{k}]. Est-ce possible de faire une telle chose?

**le profil indique "autre licence" et tu postes en "licence maths 2e/3e année " qu'en est-il ? et modifier le profil si besoin **

Posté par
GBZM
re : Ordre et générateur 30-11-20 à 13:46

Non, là tu refroidis. Tu devrais voir que la conclusion à laquelle tu arrives est absurde.

Est-ce qu'on peut avoir \large 5^{2^{k-3}}\equiv 1\pmod{2^k} ?

Posté par
etuupmc
re : Ordre et générateur 30-11-20 à 14:09

Uniquement si 5\equiv 1[2^{k}] car c'est en multipliant la congruence que vous avez indiquée par 5\equiv 1[2^{k}] que l'ont arrive à 5^{2^{k-2}}\equiv 1[2^{k}]
Je ne vois aucun autre raisonnement logique...

Posté par
GBZM
re : Ordre et générateur 30-11-20 à 14:17

Ça ne va toujours pas.
Bon, je crache pratiquement le morceau :
quelle est la valuation 2-adique de  \large 5^{2^{k-3}}-1 ? Valuation 2-adique, qu'est-ce que ça veut dire ?

Posté par
etuupmc
re : Ordre et générateur 30-11-20 à 19:03

Désolé pour la réponse tardive, j'étais en cours.

La valuation 2-adique de 5^{2^{k-3}}-1 est l'exposant de 2 dans la décomposition de 5^{2^{k-3}}-1 en produit de facteurs premiers, ça je n'ai aucun soucis, c'est une notion simple.
Pour trouver cette valutation 2-adique, je ne vois pas du tout comment procéder. J'ai essayé de faire un lien avec 5^{2^{k-2}}-1 : (5^{2^{k-3}})^{2}-1 = 5^{2^{k-2}}-1 mais ça n'avance à rien. Où est le problème?

Posté par
GBZM
re : Ordre et générateur 30-11-20 à 20:30

etuupmc @ 29-11-2020 à 23:15

(on pourra s'aider du fait que la valuation 2-adique de 5 ^{2^{k-2}}-1 vaut k).

Posté par
etuupmc
re : Ordre et générateur 30-11-20 à 20:53

Je suis désolé mais je ne vois pas du tout où vous voulez en venir, je suis perdu... J'ai toujours ce que vous avez cité en tête, mais en quoi cela m'avance-t-il si ce n'est de pouvoir écrire (5^{2^{k-3}})^{2}\equiv 1[2^{k}]?
D'ailleurs, je ne vois pas du tout en quoi la valuation 2-adique de 5^{2^{k-3}}-1 nous avance pour donner l'ordre de 5(mod 2^{k})...

Posté par
GBZM
re : Ordre et générateur 30-11-20 à 21:06

Un entier a est congru à 1 modulo 2^k si et seulement si la valuation 2-adique de a-1 est supérieure ou égale à k.
Tu as tout sous le nez. Peut-être devrais-tu prendre un peu de recul ?

Posté par
etuupmc
re : Ordre et générateur 30-11-20 à 21:21

Ce qui me dérange là c'est qu'on est dans le cas de a^{2}-1, et je ne vois pas comment déduire de cela la valuation 2-adique de a-1...

Je vais laisser ça là pour aujourd'hui et j'y reviendrai demain matin a tête froide alors!

Posté par
etuupmc
re : Ordre et générateur 01-12-20 à 13:10

GBZM @ 30-11-2020 à 21:06

Un entier a est congru à 1 modulo 2^k si et seulement si la valuation 2-adique de a-1 est supérieure ou égale à k.


On a  5^{2^{k-2}}-1=(5^{2^{k-3}}-1)(5^{2^{k-3}}+1)   donc    5^{2^{k-3}}-1    divise    5^{2^{k-2}}-1
Alors  v_{2}(5^{2^{k-3}}-1) \leq v_{2}(5^{2^{k-2}}-1)=k    donc    5^{2^{k-3}}-1\neq 1 [2^{k}]   (l'inégalité signifiant la non congruence).

SI l'on répète le même raisonnement par récurrence, on arrive à la conclusion que l'ordre de 5(mod  2^{k}) est   2^{k-2}

Et en voyant l'information donnée à la question 2, on peut en conclure que  (Z/2^{k}) * n'admet pas de générateur.

Le raisonnement est-il juste cette fois?

Posté par
GBZM
re : Ordre et générateur 01-12-20 à 14:21

Non, ça ne va pas. Tu écris une égalité large, donc tu laisses la possibilité que la valuation 2-adique de 5^{2^{k-3}}-1 soit k.
Et on ne voit pas clairement ce que tu admets et ce que tu démontres.

Mais bon sang, si tu admets que la valuation 2-adique de 5^{2^{k-2}}-1 est k, pourquoi n'utilises-tu pas que celle de 5^{2^{k-3}}-1  est k-1 ???
(Il serait bon de montrer que la valuation 2-adique de  5^{2^{k-2}}-1  est k pour tout k\geq 3.)

Posté par
etuupmc
re : Ordre et générateur 01-12-20 à 14:54

Oui, j'ai bien vu le problème de l'égalité large...

J'ai tendance à aller chercher trop loin quand j'ai passé trop de temps sur une question, je ne sais pas pourquoi j'ai autant bloqué sur une chose si évidente...

Concernant la deuxième question j'aurais besoin d'un petit éclaircissement. Il est évident que les ±5^{r}(mod 2^{k}) pour 1\leq r\leq 2^{k-2} appartiennent à (Z/2^{k}Z)* puisque 5 élevé à n'importe quelle puissance et 2^{k} sont toujours premiers entre eux.

Je trouve que la question n'a pas de sens puisque tout nombre premier élevé à n'importe quelle puissance entière et 2^{k} sont premiers entre eux également donc les classes de congruences de ces nombres premiers élevés à n'importe quelle puissance entière sont aussi inversible modulo 2^{k}...
Et qu'en est-il des classes de congruences de 5 élevé à une puissance supérieure à 2^{k-2}?

Posté par
GBZM
re : Ordre et générateur 01-12-20 à 16:40

Le but de la question 2 est de décrire les 2^{k-1} éléments de (\mathbb Z/2^k\mathbb Z)^*.

Posté par
etuupmc
re : Ordre et générateur 01-12-20 à 16:50

Comment ça les 2^{k-1} éléments de (\mathbb Z/2^k\mathbb Z)^*?

Posté par
GBZM
re : Ordre et générateur 01-12-20 à 17:07

Pourquoi cette question ?

Posté par
etuupmc
re : Ordre et générateur 01-12-20 à 17:17

Je ne comprends pas ce que les éléments 2^{k-1} de (\mathbb Z/2^k\mathbb Z)^* sont. Des puissances de 5 (mod 2^{k})?

Posté par
GBZM
re : Ordre et générateur 01-12-20 à 17:21

Le groupe des inversibles de \mathbb Z/ 2^k\mathbb Z a 2^{k-1} éléments, et ces 2^{k-1} éléments sont ceux décrits dans l'énoncé de la question 2.
Qu'est-ce qui te pose problème dans cette question 2 ???

Posté par
etuupmc
re : Ordre et générateur 01-12-20 à 17:33

Ah oui d'accord pardon j'ai mal compris en effet.

Ce qui me pose problème c'est que par exemple 11 (mod 2^{k}) est inversible car pgcd(11, 2^{k})=1. Donc elle appartient (\mathbb Z/2^k\mathbb Z)^* mais pourtant elle ne figure pas dans l'ensemble donné... Et cela marche aussi pour tout nombre premier avec 2

Posté par
GBZM
re : Ordre et générateur 01-12-20 à 17:38

Tu es vraiment sûr que 11 n'est pas égal modulo 2^k à un des éléments de l'ensemble donné ?

Posté par
etuupmc
re : Ordre et générateur 01-12-20 à 17:40

Je m'en doute bien. Mais comment le prouver pour chaque entier premier avec 2 différent de 5? Je ne vois pas du tout

Posté par
GBZM
re : Ordre et générateur 01-12-20 à 18:52

Il suffit de prouver que les 2^{k-1} éléments listés sont tous différents deux à deux.

Posté par
etuupmc
re : Ordre et générateur 01-12-20 à 19:53

Pour quelle raison? Une piste pour cette démonstration? Je ne vois pas du tout comment faire

Posté par
GBZM
re : Ordre et générateur 01-12-20 à 21:11

Je te laisse y réfléchir un peu ...

Posté par
etuupmc
re : Ordre et générateur 02-12-20 à 11:38

Pour 1 ≤ r ≤ 2^{k-2}, pgcd(5^{r}, 2^{k})
donc les ±5^{r}(mod 2^{k}) appartiennent à (\mathbb Z/2^k\mathbb Z)^*
Comme 1 ≤ r ≤ 2^{k-2}, alors il y a 2^{k-2} classes 5^{r} et 2^{k-2} classes -5^{r} soit un total de 2*2^{k-2}=2^{k-1} classes ±5^{r}
Il suffit donc de démontrer que ces classes soient deux à deux différentes pour répondre à la question.

Pour cette démonstration, je me suis dit qu'il serait plus convenable de traiter la partie les classes positives et de dire que la démarche est la même pour les classes négatives car, en effet on a bien : si a\equiv b[2^{k}] alors -a\equiv -b[2^{k}]. Mais cela ne marche que si nos classes positives et leurs homologues négatives sont différentes donc uniquement si b n'est pas congru à -b modulo 2^k, donc j'imagine que ce n'est pas une bonne piste.

Jusqu'ici la seule information que nous ayons sur ces classes est leurs valuations 2-adique respectives. Donc je me demande : suffit-il de dire que les 5^{r}-1 ont tous des valuations 2-adiques différentes pour dire que les classes sont forcément toutes différentes? Sinon je ne vois rien d'autre...

Posté par
GBZM
re : Ordre et générateur 02-12-20 à 12:41

Tu peux raisonner en termes de sous-groupes : tu as le sous-groupe du groupe multiplicatif engendré par 5, et le sous-groupe engendré par -1.
Que peux-tu dire de ces sous-groupes ?

Posté par
etuupmc
re : Ordre et générateur 02-12-20 à 13:01

Ils sont l'opposé l'un de l'autre. Je ne vois rien d'autre

Posté par
GBZM
re : Ordre et générateur 02-12-20 à 14:20

Ne réponds pas n'importe quoi, s'il te plaît.

Posté par
etuupmc
re : Ordre et générateur 02-12-20 à 20:38

Désolé, j'ai tendance à paniquer quand je dois travailler avec des groupes pour des démonstrations.
J'ai trouvé un moyen de démontrer cela sans parler de groupes.
Je prends deux entiers r et s entre 1 et 2^{k-2}, je suppose que ±5^{r}(mod 2^{k}) et ±5^{s}(mod 2^{k}) sont égaux, d'ordres respectifs d et d'. La preuve amène à dire que les deux ordres sont forcément égaux et que donc les deux classes sont forcément de même signe et que r=s. Et le tour est joué!

Merci beaucoup pour votre aide! Bien que ça m'ait aidé pour faire cet exercice, ça m'a surtout aidé à mieux comprendre le cours!

Posté par
GBZM
re : Ordre et générateur 03-12-20 à 10:06

Hum ... D'après ce que tu en dis, ton raisonnement ne m'a pas l'air correct.
Quel est le cardinal du sous-groupe multiplicatif de (/2k)* engendré par (la classe de) 5 ? Quel est le cardinal du sous-groupe engendré par -1 ? Quelle est l'intersection de ces sous-groupes ?

Posté par
etuupmc
re : Ordre et générateur 03-12-20 à 13:08

Oui en effet, je m'en suis rendu compte plus tard! Voici un cheminement correct:
Je suppose d'abord que 5^{r}(mod2^{k}) = 5^{s}(mod2^{k})
que l'on simplifie en 5^{r-s}\equiv 1[2^{k}]
La plus petite puissance de 5 telle que 5 élevé à cette puissance est congru à un mod. 2^k est 2^{k-2}
Donc 2^{k-2} divise r-s, ce qui implique que r-s=0 donc r=s

Puis je suppose que 5^{r}(mod2^{k}) = -5^{s}(mod2^{k})
que l'on simplifie en 5^{r-s}\equiv -1[2^{k}]
Ce qui est impossible car aucune puissance de 5 n'est congrue à -1 modulo 2^k. Mais je n'arrive pas à montrer cela...

Je comprends que (Z/2^kZ)* est isomorphe au produit du sous-groupe engendré par 5 et du sous-groupe engendré par -1. Mais je suis vraiment mauvais en théorie des groupes et de plus je n'ai que de vagues souvenirs de ce cours donc je ne peux même pas répondre à vos questions...

Posté par
GBZM
re : Ordre et générateur 03-12-20 à 13:50

Ben, ça vaudrait sans doute le coup que tu rafraîchisses un peu tes souvenirs concernant les groupes...
Par exemple : tu sais (enfin, je ne sais pas si tu l'as démontré complètement) que 5 est d'ordre 2^{k-2}.  Ça devrait te dire immédiatement quel est le cardinal du groupe cyclique engendré par 5.

Posté par
etuupmc
re : Ordre et générateur 03-12-20 à 14:37

Oui je sais bien, je fais un double cursus chargé et je n'ai pas toujours le temps...

Oui je l'ai complètement démontré. Ça me dit que le cardinal du groupe cyclique engendré par 5 est 2^{k-2} qui est aussi le cardinal du groupe engendré par -1. L'intersection de ces sous-groupes est l'ensemble vide, donc le cardinal de leur produit est la somme de leurs cardinaux qui est égale à 2^{k-1} qui est le cardinal de (Z/2^kZ)*. C'est ça?

Posté par
GBZM
re : Ordre et générateur 03-12-20 à 14:44

etuupmc @ 03-12-2020 à 14:37

Oui je l'ai complètement démontré. Ça me dit que le cardinal du groupe cyclique engendré par 5 est 2^{k-2}

Oui
Citation :
qui est aussi le cardinal du groupe engendré par -1.

Non.
Citation :
L'intersection de ces sous-groupes est l'ensemble vide,

Sûrement pas !
Citation :
donc le cardinal de leur produit est la somme de leurs cardinaux qui est égale à 2^{k-1} qui est le cardinal de (Z/2^kZ)*. C'est ça?

Pas du tout.
Réfléchis plus à ce que tu écris.

Posté par
etuupmc
re : Ordre et générateur 03-12-20 à 15:02

A quoi correspond le groupe engendré par -1? Je ne comprends pas.

Posté par
GBZM
re : Ordre et générateur 03-12-20 à 15:19

Vrai, tu ne vois pas quel est le groupe multiplicatif engendré par -1 ??
Tu dois être complètement perdu. Fais un "Control reset".

Posté par
etuupmc
re : Ordre et générateur 03-12-20 à 17:04

Non je ne suis pas perdu. La théorie des groupe est un cours que j'ai validé il y a longtemps et je n'en ai que quelques vagues souvenirs. Je fais mes études de maths à distance donc sans professeurs. Si je pose des questions qui semblent bêtes c'est juste qu'il y a des notions que je n'ai pas comprises et donc je viens chercher de l'aide sur les forums

Posté par
etuupmc
re : Ordre et générateur 03-12-20 à 19:01

Je viens de relire mes cours de L1 et les groupes ne sont que survolés : juste une définition et quelques exemples.
Donc il est tout à fait normal que je ne comprenne pas puisque la théorie des groupes est l'objet des deux derniers chapitres de mon cours d'arithmétique, et je ne les ai pas encore abordés!

Posté par
GBZM
re : Ordre et générateur 03-12-20 à 19:12

Écoute, il n'y a pas besoin de connaissance sophistiquée sur les groupes pour savoir quel est le groupe multiplicatif engendré par -1. Quel est l'inverse de -1 ? Que vaut ( -1)2 ?

Posté par
etuupmc
re : Ordre et générateur 03-12-20 à 19:44

Certes mais mes connaissances sur les groupes s'arrêtent à la définition de la notion de groupe! Sans savoir ce qu'est un sous groupe engendré par un élément c'est compliqué...

Je viens de feuilleter mon cours sur les groupes et donc je comprend que le sous-groupe engendré par -1 a 2 comme cardinal car il correspond à -1 et 1.

Et comme je l'ai dit plus haut (Z/2^kZ)* et le produit des sous groupes engendrés respectivement par -1 et 5 sont isomorphes (le produit à bien 2.2^{k-2}=2^{k-1} éléments, qui est le cardinal de (Z/2^kZ)*).

Posté par
GBZM
re : Ordre et générateur 03-12-20 à 21:31

Il reste encore à voir que l'intersection des deux sous-groupes est réduite à l'élément neutre, c'est-à-dire que -1 n'appartient au sous-groupe engendré par la classe de 5.

Je suis un peu surpris qu'on te donne à faire cet exercice alors que tu as si peu ce connaissances sur les groupes. L'étude du groupe multiplicatif de /n, ce n'est pas immédiat, et en plus le cas de /2^k est le cas "vache".

Posté par
etuupmc
re : Ordre et générateur 03-12-20 à 21:47

En fait les groupes sont traités dans le prochain chapitre (qui ne fait pas partie du programme pour ce devoir). Je vous envoie ma preuve (sans groupes) demain matin!

Posté par
etuupmc
re : Ordre et générateur 04-12-20 à 17:33

Pardon pour le retard!
Je prend deux entiers r et s tels que 1 ≤ r ≤ 2^{k-2} et 1 ≤ s ≤ 2^{k-2}
Je suppose dans un premier temps que 5^r (mod 2^k) = 5^s (mod 2^k), que je simplifie en 5^{r-s}\equiv 1 [2^{k}]. Cela implique que 2^{k-2} divise r-s et comme r-s < 2^{k-2} alors on a r-s=0 donc r=s

Puis je suppose 5^r (mod 2^k) = -5^s (mod 2^k) que je simplifie en 5^{r-s}\equiv -1 [2^{k}] ce qui est impossible (que je montre en réduisant la congruence au modulo 4). Donc 5^r (mod 2^k) et 5^s (mod 2^k) sont forcément du même signe

Ces deux points prouvent bien cela :

GBZM @ 01-12-2020 à 18:52

Il suffit de prouver que les 2^{k-1} éléments listés sont tous différents deux à deux.

Posté par
GBZM
re : Ordre et générateur 04-12-20 à 22:36

Très bien. Le point clé est de montrer que -1 n'est pas dans le sous-groupe multiplicatif engendré par 5. L'idée de passer modulo 4 est ingénieuse. Ça vient de toi ou ça faisait partie des indications ?
Attention tout de même ; tel que tu l'as écrit, rien n'empêche r-s d'être négatif.

Posté par
etuupmc
re : Ordre et générateur 04-12-20 à 22:42

Il n'y a aucune indication pour cette question, ça vient de moi.
Oui il faut noter r>=s

Posté par
GBZM
re : Ordre et générateur 05-12-20 à 10:09

OK.



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1674 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !