# Arrel primitiva

### De Viquipèdia

Hom diu que el nombre enter a és una arrel primitiva (mod n) si pertany a l'exponent φ(n) (mod n), és a dir, si φ(n) és l'exponent no negatiu més petit que fa (φ és la funció Fi d'Euler).

## [edita] El punt de vista de la Teoria de Grups

Des del punt de vista de la teoria de grups, que a sigui una arrel primitiva (mod n) és el mateix que dir que , el grup multiplicatiu de les unitats de l'anell , és cíclic i que la classe a n'és un generador.

## [edita] Existència d'arrels primitives

- Si n és 2 o 4, hom comprova fàcilment, només escrivint-ne la taula, que el grup és cíclic: 1 és una arel primitiva (mod 2) i 3 ho és (mod 4)
- En canvi, si n és 2k, amb k > 2, el grup ja no és cíclic, com resulta inmediatament de la congruència . En efecte, com que , és clar que els grups no són cíclics, perquè 2 és el màxim dels ordres dels elements d'aquests grups.
- Per a nombres primers senars, p, els grups són tots cíclics, per qualsevol valor de k > 0.
- Per a un nombre n qualsevol, si n'és la descomposició en factors primers, el grup és isomorf al producte directe dels grups . Tenint en compte quins d'aquests factors són grups cíclics i el fet que el producte és cíclic si, i només si, els factors ho són i els ordres respectius són coprimers, resulta que és cíclic si, i només si, el nombre n és d'una d'aquestes quatre formes 2, 4, pk o 2pk. En conseqüència, hi ha arrels primitives (mod n) si, i només si, el nombre n és d'una d'aquestes quatre formes 2, 4, pk o 2pk.

## [edita] Obtenció d'arrels primitives

- Pel mòdul 2 només hi ha l'arrel primitiva 1 i, pel mòdul 4, només 3 ho és.
- Si a és una arrel primitiva (mod p) (p primer senar) aleshores, o bé a, o bé a + p és una arrel primitiva (mod p2).
- Si a és una arrel primitiva (mod p2) (p primer senar) aleshores, a també és una arrel primitiva (mod pk), per tot k > 1.

Per tant, calcular arrels primitives (mod pk), k > 1 és ben senzill: a partir de les arrels primitives (mod p). es calculen les arrels primitives (mod p2) i, d'aquí, les de (mod pk), per qualsevol k > 1.

Però el càlcul de les arrels primitives (mod p) és molt llarg i dificultós i poca cosa més es pot fer apart de cerques exhaustives, per la qual cosa, l'importància de les arrels primitives és molt gran en Criptografia.

## [edita] Referències

- Gauß Carl F. Disquisicions aritmètiques. (Disquisitiones Arithmeticæ Pascual Xufré, Griselda, (trad.) 1996) Societat Catalana de Matemàtiques (I. E. C.) Barcelona
- Hardy G. H. & Wright E. M. (1983) An Introduction to the Theory of Numbers. Clarendon Press - Oxford (en anglès)
- Ireland Kenneth & Rosen Michael (1990) A Classical Introduction to Modern Number Theory. Springer - Verlag

Obtingut de "http://ca.wikipedia.org../../../a/r/r/Arrel_primitiva.html"

Categories: Teoria de nombres | Aritmètica

##### Views

- Article
- Discussió
- Revisió actual

##### Cerca