Z/nZ

Comme "promis", je vous propose de partager mes connaissances sur l'anneau Z/nZ.
Je connais trés peu de choses, mais suffisamment pour montrer comment l'abstraction permet de simplifier, et pour montrer l'abstraction tout court.

Prenons N, l'ensemble des entiers naturels, c'est-à-dire les entiers qui sont positifs ou nuls.

Soit n un de ces entiers, non nul lui.

Imaginons N comme un ruban, où les entiers sont représentés par des traits.

Maintenant, on fait un trait sur 0, on part de 0 et on compte n entiers. On arrive donc à n-1 (de 1 à n, il y a n entiers, donc de 0 à n-1 aussi). Sur n, on fait un trait, puis on recommence à compter n entiers, de n à 2n-1, etc. à l'infini.

Imaginez qu'on enroule le ruban de façon à ce que les traits coincident.

C'est comme si on avait un ruban enroulé, qu'on coupait à n endroits, et sur toutes les couches du ruban, les entiers sur la même coupure sont séparés de n.

Et bien on a construit Z/nZ.

Z/nZ, c'est l'ensemble des n premiers naturels (de 0 à n-1). Et au lieu de faire des additions, des multiplications et des soustractions normallement, on les fait pareil autant que faire se peut, mais on voit bien qu'il y a un problème, par exemple lorsqu'on veut calculer 2(n-1): on "sort" de Z/nZ.

Et bien on considère le résultat obtenu sur le ruban, et on dit que le résultat dans Z/nZ correspond à la "tranche" qui est sur le ruban.

On peut imaginer aussi un tore = un tube dont on joint les 2 bouts, divisé en n. Une fourmi parcourt le tore en partant de 0, et c'est elle qui effectue les opérations. Lorsqu'on lui demande 3+5, elle part de 0, elle fait 3 pas, puis encore 5 pas, et on considère où elle arrive.

Si on a divisé le tore en 7, elle arrive à 1, puisqu'à 6, elle est arrivée "au bout", et elle doit faire 2 pas de plus, donc 0 puis 1.

Une autre façon de calculer dans Z/nZ: on regarde le résultat "normal".
On divise N en boîte de n objets. Alors, si le résultat est à la k-ième position dans sa boîte (en partant de 0), alors le résultat dans Z/nZ est k.

Tout ce qu'on a fait dans N peut s'étendre à Z.

Cette vision des choses a permis de simplifier bien des problèmes:
exemple hyper classique:
montrons que le carré d'un entier ne peut pas s'écrire 4k+2 ou 4k+3, où k est un entier, c'est-à-dire qu'il n'existe aucun entier a tel qu'il existe un entier k tel que a²=4k+2 ou a²=4k+3.

En effet, imaginons Z/4Z. Alors par l'absurde, supposons qu'il existe un couple d'entiers (a;k) tels que a²=4k+2 ou a²=4k+3.

Alors, a²=2 ou a²=3 dans Z/4Z, car 4=0 dans Z/4Z, d'où 4 fois k = 0 fois k = 0 (les propriétés des opérations sont conservées, puisqu'il n'y a pas de réel changement, à part le fait de "ramener" le résultat dans Z/4Z, mais on peut montrer facilement que cela n'altère rien).

Or, dans Z/4Z, soit a=0, soit a=1, soit a=2, soit a=3.
D'où soit a²=0, soit a²=1, soit a²=4=0, soit a²=9=2*4 + 1= 1 donc on a jamais a²=2 ou a²=3, ce qui conclut.

Tout ça pour montrer que rien n'est figé en maths, et que tout dépend de la façon de voir.

Si vous aimez ça, je peux continuer un peu sur l'arithmétique.

Bon bon, je ne posterais plus de topics qui n'intéressent personne.

Si si ça m'intéresse, continues.

Alpha.

T'as pas dit ce que c'était Z...Me souviens plus

En fait ce que tu expliques c'est la relation "modulo n" pour n dans N*.

Si on se donne n dans N*, et disons x dans N.
Alors il existe un unique entier x' dans [0,n-1] tel que (il existe k dans Z vérifiant x = x' + k.n)
Ce qu'on exprime par x congru à x' modulo n. Mathématiquement, on écrit x = x' [n] (en toute rigueur, le signe n'est pas "=" mais trois traits horizontaux)

Par exemple soit n = 4.
1009 (au hasard) = 4 x 252 + 1
Donc 1009 = 1 [4]

On peut montrer que la relation "modulo n" est une relation d'équivalence (pour ceux qui connaissent).

Symétrie : si x = x' [n] alors x = x' + k.n donc x' = x - k.n
Soit k' = -k
on a x' = x + k'.n
càd : x' = x [n]

Transitivité : si x = x' [n] et x' = x'' [n]
alors x = x' +k.n et x' = x'' + k'.n
donc x = x'' + k'.n + k.n
donc x = x'' + k''.n en posant k'' = k + k'
càd x = x'' [n]

Réflexivité : il faut montrer que x est congru à lui même modulo n, ce qui est évident avec k=0

Ainsi, pour n dans N* fixé, l'ensemble des entiers congrus à l'entier m dans N forme une classe d'équivalence.

Cioran a écrit:

T'as pas dit ce que c'était Z...Me souviens plus

C'est tous les entiers= les entiers relatifs= positifs, négatifs, nul.

En fait, il faut bien voir Z/nZ comme un "groupe", c'est-à-dire un ensemble de nombres possèdant des lois qui permettent de les lier entre eux, exactement comme dans R: 1+2=3=1+1+1=....

Le côté pratique, c'est que les lois, + et *, sont strictement les mêmes que dans Z, avec pour seul aménagement le fait que puisqu'on n'a pas le droit de "sortir" de l'ensemble (car il doit être "stable"), lorsqu'on sort on revient au départ, un peu comme quelqu'un qui court les yeux fermés pendant 30 minutes et il se rend compte que dans l'allée il y a un point de téléportation qui le faisait revenir 10 mètres plus bas.

Comme les lois sont les mêmes, on peut considérer Z "modulo n", c'est-à-dire qu'on parle toujours de Z, d'entiers qui ne sont pas forcément compris entre 0 et n-1, mais néanmoins en remplaçant la relation d'égalité par une relation de "congruence", avec a=a+n=a+2n=...

Pour utiliser plus profondément Z/nZ, il faut parler d'abord d'arithmétique élémentaire.

La base de l'arithmétique, c'est la division euclidienne, celle qu'on apprend en primaire.

On a le théorème suivant:
Pour tout entier relatif a, pour tout entier relatif b (non nul), il existe des entiers (relatifs) q et r tels que:
a= bq+r , avec r compris au sens large entre 0 et b-1.

C'est ce que disait protée.

Démonstration:
On va supposer a et b positifs pour être sûrs, mais c'est pareil dans les négatifs.

L'idée est que dans tous les cas, on peut poser a=b+k. En effet, k=a-b est un entier, et on a bien a=b+k.
Si k est compris entre 0 et b-1, on a fini, il suffit de prendre q=1 et r=k.

Sinon, on peut encore écrire a= b+(k-b)+b=2b+(k-b).
k-b est positif puisqu'on suppose que k est supérieur à b, et si k-b est inférieur à b-1, on a fini en prenant q=2 et r=k-b.

Sinon, on peut encore écrire a= 2b+(k-b-b)+b=3b+(k-2b).
Même argument, etc.

On voit qu'à un moment, on s'arrêtera, puisque sinon, k-nb ne serait jamais négatif, ce qui est absurde pour n assez grand.
Cette "démonstration" permet donc de conclure.

En réalité, ce qu'on a fait, c'est qu'en prenant Z en "boîtes" de taille b, on est parti de a et on a sauté de boîte en boîte "vers la gauche" (c'est-à-dire en étant de plus en plus petit). Alors, on va forcément arriver à un moment dans la boîte 0, 1, 2.... b-1 , et en comptant le nombre de boîtes sautées et le nombre sur lequel on arrive, on obtient respectivement q et r.

Exercice:
Nous avons un système de numération en base 10.
C'est-à-dire que l'écriture ...1425 représente le nombre:
5*10^0 + 2*10^1 + 4*10^2 + 1* 10^3 + ...

Mais on peut tout aussi bien représenter en base n, par exemple en base 2:
6 écrit en base 10 correspond à 110 en base 2, car 110 représente:
0*2^0+1*2^1+1*2^2 = 0 + 2 + 4= 6.

La définition générale de la décomposition d'un nombre a en base n est la suivante:

a peut s'écrire a= a_0 * n^0 + a_1*n^1 + a_2*n^2 + ... +a_k*n^k
où les nombres a_i sont des entiers naturels compris entre 0 et n-1 inclus (remarquez la ressemblance avec la division euclidienne...), k étant un entier naturel "quelconque" (sans importance en réalité).

Montrer que pour tout couple de naturels (a;n), une telle décomposition existe (c'est-à-dire qu'il existe des nombres a_i tels que...), et qu'elle est unique (c'est-à-dire que si on change ne serait-ce qu'un seul a_i, on est foutu).

On peut définir le Plus Grand Commun Diviseur de 2 nombres a et b, noté PGCD(a;b) (mais moi je note plus commodément (a;b) ) comme le plus grand entier positif qui divise a et b à la fois.
Je rappelle qu'on dit que k divise n si et seulement si il existe un entier q tel que n=kq (6=2*3 donc 2 et 3 divisent 6).

Voici un théorème dont la démonstration est belle:
Théorème de Bézout:
Soit a et b, 2 entiers relatifs (positifs, négatifs ou nuls).
Alors, l'ensemble des nombres qui s'écrivent au+bv où u et v parcourent l'ensemble des entiers relatifs est exactement l'ensemble des multiples de (a;b).
Autrement dit, pour tout entier k, il existe des entiers u et v tels que:
au + bv = k(a;b).

En particulier, pour k=1, il existe des entiers u et v tels que au+bv=(a;b).

Exemple: pour a=2 et b=4, (a;b)=2 et 3(a;b)=a*1 + b*1.

au+bv est appellé une combinaison linéaire de a et de b. L'ensemble des combinaisons linéaires de a et de b est en réalité l'ensemble des nombres au+bv où u et v sont successivement tous les entiers possibles.

Je ne sais pas si c'est trés clair, sinon dites-le moi, mais lisez d'abord la démonstration ci-dessous, qui est trés jolie:

Démonstration:
Soit d le plus petit entier strictement positif qui s'écrive ax + by.
Alors d divise tous les entiers s'écrivant au+bv:
en effet, soit m=au+bv. Alors la division euclidienne de m par d donne
m=qd+r soit r=m-qd , avec r compris entre 0 et d-1.

m-qd=au+bv-aqx-bqy=a(u-qx)+b(v-qy)=r qui est bien une combinaison linéraire de a et de b (r=aU+bV en posant U=u-qx et V=v-qy) ) , donc r est une combinaison linéaire de a et de b, mais strictement plus petite que d. Or on avait supposé d la plus petite possible qui soit non nulle, donc r doit être nul, d'où m=qd, soit d divise m, et ce pour m=au+bv quelconque.

Ainsi, d divise toutes les combinaisons linéaires de a et de b. Il divise donc en particulier a*1+b*0=a et a*0+b*1=b donc c'est un diviseur de a et de b.
En outre, d=ax+by donc si p est un diviseur commun à a et à b, il existe des entiers a' et b' tels que a=pa' et b=pb' et on a alors d=pxa'+pyb'=p(xa'+yb') qui est un multiple de p, donc p divise d.

Ainsi, d est un diviseur commun de a et de b, et comme tout diviseur commun de a et de b divise d, d est le plus grand diviseur commun de a et de b, donc leur PGCD.

Il existe donc des entiers x et y tels que (a;b)=ax+by , toute combinaison linéaire de a et de b est multiple de d=(a;b), et tout multiple de d=(a;b) est bien une combinaison linéaire de a et de b car il s'écrit kd=kax+kby=a(kx)+b(ky).

Qu'en pensez-vous?

Pour le cas k=1, tu as même une équivalence si je me rappelle bien :

(a;b)=1 ssi il existe u et v tels que au + bv = (a;b)

Alors que pour les autres cas, on a seulement l'implication :

(a;b)=k implique il existe ...

Oui, cela provient du fait que 1 est le plus petit naturel non nul, donc il correspond forcément au d de la démonstration.


C'est important de le préciser, tu as raison, car cela donne effectivement un critère de coprimalité (c'est-à-dire qu'on peut alors savoir si le pgcd de 2 entiers est 1).