Forum de mathématiques - Bibm@th.net

JeanPaul

Invité

Exercies sur Z/NZ

Voici mon problème je vais essayer de retranscrire le sujet correctement,
je demande pas spécialement des réponses exactes aux questions surtout de quoi comprendre,
j'ai un sujet de révision sur lequel je travail actuellement dont voici les questions
1) Calculer dans Z/12Z
(a) 8+5 (je sais pas mettre les barres au dessus)
(b) 8x5
(c) 8^5
2) Combien y'a t'il d'élements inversibles dans Z/12Z ? En drésser la liste
3) Quel est l'ordre de (Z/12Z) * ? Quels sont les ordres possibles des élements de (Z/12Z)*?
4) Le groupe (Z/12Z)* posséde t'il un génerateur?
5) Montrer que l'equation 6x=1 n'a pas de solution dans Z/12Z (On pour remarquer que si x est solution alors c'est un inverse de 6)
6) Montrer que 6x =5 n'a pas de solution dans  x appartient à  Z/12Z
7) Les équations suivantes possédent t'elles une solution x appartient à Z/12Z  ? Si oui laquelle ou lesquelles, justifier chaque réponse)
=> 3x =1 / 7x=3 /10x =0 / 3x =7 / 7x =5 / 10x=2

Ce que j'ai pour l'instant :
8 et 5 ne sont pas inversibles donc je sais pas trop comment les calculer, dois je calculer ça normalement?
Pour la 2 il y'a 4 élement avec le théorème de bezout que j'ai trouvé 1,-1 et 5 -5 cependant y'a t'il une solution pour trouver le nombre d'élement directement? (j'imagine que les tester un par un n'est pas la solution)
3 4 je ne sais pas
Pour la 5 les inverses sont déja trouvés et ils sont a partir de 11 et 7 donc x n'est pas un inverse donc pas solution

J'ai trouvé la formule d'Euler pour la deux ce qui fairait Fi(12) = Fi(2) x Fi(6)
=1 x 2 = 2
Est ce le 1 et le 5? que je dois ensuite multiplier par  2 pour prendre positif et negatif?

Cdt Cordialement.

Dernière modification par yoshi (14-06-2014 06:38:55)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 401

Re : Exercies sur Z/NZ

Bonjour,

Après vérifications, divers scripts Python calculent l'inverse de a modulo n :
http://www.bibmath.net/forums/viewtopic … 814#p13814
En outre
12 = 5 * 2 +2
5 = 2 * 2 +1
D'où
1 = 5 - 2 * 2
1 = 5 - (12 - 5 * 2) * 2
1 = 5 - 12*2 +5 *4
1 = 5 * 5 -4 * 12
L'inverse de 5 est 5 : 5 * 5 = 24 +1 = 1 [12], non ?

Pour finir, va voir là :
http://www.math.polytechnique.fr/~harin … Groupe.pdf

@+

ehoulm

Invité

Re : Exercies sur Z/NZ

je veux des exercice sur z nz

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 401

Re : Exercies sur Z/NZ

Salut,

Décidément, la politesse fout le camp...
Je veux ? Et puis encore ?
Si tu cherchais un peu hein ?
Ces exos -corrigés - existent sur BibMath dans la base de données d'exercices...

@+
      Yoshi
- Modérateur -

JeanPaul

Invité

Re : Exercies sur Z/NZ

Desolé pour mon manque de politesse sur le premier post :'(
Merci pour ton explication pour le 5
cependant mon probléme (si il y'en a un )
est plutot au niveau du 8
Je me vois pas trouvé 12u+ 8v =1 du fait qu'ils sont tout les deux paires, d'habitude j'ai pas trop de probléme avec ce type d'exo on a du 13 du 37Z mais rarement 12, je m'étais donc pas poser la question du : qu'est ce que je fais si j'arrive pas à trouver d'inverse?
(J'espere avoir été précis sur ce que je ne comprend pas :) )
Cordialement

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Exercies sur Z/NZ

Salut,

si tu dresses le tableau du produit deux par deux des éléments de (Z/12Z)² dans Z/12Z, tu vas vite trouver les réponses à tes questions !

Si tu lis avec attention le lien internet donné par yoshi, tu as toutes les réponses à toutes tes questions !

A partir de là, on peut t'aider le cas échéant !

Bon courage !

Dernière modification par freddy (16-06-2014 10:13:28)

JeanPaul

Invité

Re : Exercies sur Z/NZ

Exemple. On a Z/5Z = {0, 1, 2, 3, 4} et 4 × 4 = 1 3 × 2 = 1.
Dans Z/8Z, 4 n’a pas d’inverse pour la multiplication (on ne peut pas trouver x tel que 4x =
1 mod 8).
(Qui vient du cour)
Aprés cet exemple qui est donc un cas comme le mien il n'y a pas de plus amples informations
J'avou être un peu perdu :x
Cordialement

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 401

Re : Exercies sur Z/NZ

Salut,

http://mat.free.free.fr/downloads/crypt … crypto.pdf
Page 1 :

DETERMINER L'EXISTENCE D'UN INVERSIBLE DANS Z/nZ

a est inversible dans [tex]\mathbb{Z}/n\mathbb{Z} \Leftrightarrow[/tex] a et n sont premiers entre eux [tex]\Leftrightarrow[/tex] pgcd(a,n)=1 [tex]\Leftrightarrow\; \exists b,\;a\times b = 1[/tex]

Autrement dit, tu ne peux trouver u et v tels que 8u+12v =1 (facile à prouver si besoin est)

Et voilà, tirés de la Base de données d'exercices de BibMath, 8 exos sur ce thème, avec énoncés, indications et corrigés...
http://www.bibmath.net/exercices/index. … uoi=arithm
Et plus particulièrement les exercices 1 et 6

@+

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Exercies sur Z/NZ

Re,

bon, je comprends mieux. Alors regarde pour la multiplication (je commence à partir de 2 jusqu'à 11, avant ne sert à rien et je me sers de la propriété ab=ba modulo n) : dans chaque intersection ligne-colonne, je donne le résultat de axb modulo 12

[tex]\begin{matrix} \times & 1 & 2 & 3 & 4 & 5 &  6 & 7 &  8 &  9 &  10 & 11
\\ 1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11
\\ 2 && 4 &  6 & 8 &  10 & 0 & 2 & 4 & 6 & 8 & 10
\\ 3 &&& 9 & 0 & 3 &  6 & 9 & 0 & 3 &  6 &  9
\\ 4 &&&& 4 & 8 & 0 &   4 & 8 &  0 & 4 &  8
\\ 5 &&&&& 1 & 6 & 11 & 4 & 9 & 2 & 7
\\ 6 &&&&&& 0 & 6 & 0 & 6 & 0 & 6
\\7  &&&&&&& 1  & 8 &  3  & 10  &  5
\\8 &&&&&&&& 4 &  0 & 8 &  4
\\9 &&&&&&&&& 9 & 6 & 3
\\10 &&&&&&&&&& 4 & 2
\\11 &&&&&&&&&&& 1
\end{matrix}[/tex]

Tu mélanges cela avec les conseils avisés de yoshi + un peu de gamberge, et tu casses la baraque !!!

PS : pour minorer le trouble de notre ami, j'ai enrichi le tableau de l'élément neutre pour la multiplication ...

Dernière modification par freddy (17-06-2014 21:16:58)

JeanPaul

Invité

Re : Exercies sur Z/NZ

Donc pour le 1 n'ayant pas d'inverse je laisse 8 pour faire le calcul?

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Exercies sur Z/NZ

Re,

1 étant l'élément neutre pour la multiplication, il est son propre symétrique !

On a 8x5 = 4 , (8x8)(8x8)x8 = (4x4)x8 = 4x8 = 8 [12] qui est un résultat dû à Fermat puisque 5 est premier !

Dernière modification par freddy (16-06-2014 22:28:15)

JeanPaul

Invité

Re : Exercies sur Z/NZ

Je comprend bien que le 5 deviennent 5, pour le 8 c'est un 12-8 =4 (le reste en Z/12Z)?

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 401

Re : Exercies sur Z/NZ

Salut,

Les liens donnés plus le tableau de freddy devraient suffire à te monter que 8 n'est pas inversible, de même que tout nombre pair :
[tex]PGCD(8,12) \neq 1[/tex]
si 8 avait un inverse x, on aurait [tex]8 \times x =1 \;[12][/tex]
Or, dans [tex]\mathbb{Z}/12\mathbb{Z} [/tex] c'est impossible : le tableau de freddy (colonne 8) te le montre bien...

@+

JeanPaul

Invité

Re : Exercies sur Z/NZ

Je comprend bien depuis le début qu'il n'est pas inversible, ce que je ne comprend pas (pour en revenir a la question 1) c'est que si un nombre n'est pas inversible ( ce qui peut arriver dans ce type d'exercices) Que fais je du 8? je le laisse telle qu'il est dans l'exercice?
Ou je le remplace par une certaine valeur?
Je n'avais jamais eu à faire à des nombres non inversibles dans ce type d'exos, je m'étais donc jamais posé la question.

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 401

Re : Exercies sur Z/NZ

Salut,

Que fais je du 8?

Là quelque chose m'échappe... Je ne comprends pas ta question ?!
A tout hasard, dans [tex]\mathbb{Z}/12\mathbb{Z}[/tex] :
1.a)  8 + 5 = 1
   b)  8 x 5 = 4
   c)  8^5 = (-4)^5 = (-4)^4 x (-4) = 256 x (-4) = 4 x (-4) = -16 = 8 les calculs sont plus faciles comme ça...

@+

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 352

Re : Exercies sur Z/NZ

Je vais te renvoyer la question. 5 et 7 sont inversibles dans Z/12Z. Comment calcules-tu 7*5 dans Z/12Z? Est-ce que tu utilises vraiment qu'ils sont inversibles???

Fred.

JeanPaul

Invité

Re : Exercies sur Z/NZ

Je voulais à tout prix calculer avant en Z/12Z (j"entend par la de modifier mes valeurs a posteriori)  je pense avoir compris actuellement :)
Pour la 2 je ne savais pas comment déterminer le nombre d’éléments je l'avais fait par élimination.
J'ai utilisé Euler ce qui fait donc Fi(12) = Fi(6) x Fi(2) = Fi(3)xFi(3)xFi(2) avec les -1 de la formule cela me donne 2x2x1 =4
Je pense que c'est bon.
Pour la suite je ne comprend pas trop je vais chercher dans le cour.
Encore merci pour les explications.

JeanPaul

Invité

Re : Exercies sur Z/NZ

Je ne sais pas trop quoi répondre pour la question suivante
Pour (Z/12Z)* je suis tenté de mettre 4^(k-1) k appartenant à n

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 352

Re : Exercies sur Z/NZ

La réponse est dans le tableau de Freddy (Post 9).
Un élément de Z/12Z est inversible si on trouve un autre élément de Z/12Z tel que le produit de ces deux éléments soit égal à 1.

JeanPaul

Invité

Re : Exercies sur Z/NZ

Pour les élements inversibles j'ai utilisé Euler ce qui me semblait bon, je comprend pas trop la notion de (Z/12Z)* c'est cet ensemble x lui même?

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 352

Re : Exercies sur Z/NZ

Non!!!! Es-tu sûr d'avoir lu ton cours????
(Z/12Z)* est le groupe des éléments inversibles de Z/12Z, muni de la multiplication....

JeanPaul

Invité

Re : Exercies sur Z/NZ

Donc si je me refére au tableau du post 3 j'ai donc 3 éléments inversibles? soit 6 avec le +/- ?
Cependant je ne comprend pas trés bien la notion d'ordre et de génerateur (j'ai lu le cour mais je ne le comprend pas vraiment :x)
C'est pourquoi je fais des sujets pour apprendre ces notions je comprend mieux quand je le fais
Cordialement

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 352

Re : Exercies sur Z/NZ

Donc si je me refére au tableau du post 3 j'ai donc 3 éléments inversibles?

Pas tout à fait, car il manque 1 qui n'apparait pas dans le tableau (mais qui est toujours inversible)

soit 6 avec le +/- ?

Pas du tout!!!! Freddy a pris tous les éléments de Z/12Z et a regardé quels étaient leurs multiples.
Donc pas besoin de prendre un signe en plus.
D'ailleurs, 5 et 7 sont inversibles, et 7=-5 modulo 12 donc -5 et 7 sont les mêmes éléments dans Z/12.

Fred.

JeanPaul

Invité

Re : Exercies sur Z/NZ

J'ai donc 4 élements inversibles, le groupe (Z/12Z)* est donc (1,5,7,11) ?
pour l'ordre je ne sais pas trop je dirais 4 du coup avec 1 5 7 11 leur ordres possibles?
Pour le generateur j'ai trouvé ça sur le net :
"un generateur x de Z/5Z si il est parmi 1, 2, 3 ou 4 doit verifier x^5 = 1"
Je ne sais pas si c'est bon du coup je sais pas trop quoi répondre. encore merci pour les explications j'ai fait quelques autres sujets en parallèle et je commence à saisir le truc.
Toujours quelques soucis avec cette notion de generateur

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 352

Re : Exercies sur Z/NZ

* Quel est l'ordre de (Z/12Z) ?

L'ordre d'un groupe, c'est le nombre d'élément du groupe!!! Je suis sûr que tu as cette définition dans ton cours!!!

* Quels sont les ordres possibles des élements de (Z/12Z)*?

Connais-tu le théorème de Lagrange???

* Le groupe (Z/12Z)* posséde t'il un génerateur?

g est un générateur d'un groupe G si quand tu regardes toutes les puissances de g, on obtient tous les éléments de G.
Ainsi, tu dois prendre 1, 5, 7 puis 11, et regarder si quand tu fais disons 5, 5^2, 5^3, 5^4,..., on obtient tous les éléments de (Z/12Z)*, c'est-à-dire 1,5,7,11.

Fred.