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).
Taula de continguts |
[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

