Universitatea Bucuresti

Facultatea de Matematica si Informatica

Radacini primitive modulo n

Indrumator stiintific:

Prof. Dr. Victor Alexandru

2010

Rezumat

Tema lucrarii este studiul radacinilor primitive. Folosind niste rezultate pre-

liminare (date in capitolul 1), vom introduce notiunea de radacina primitiva si

o vom studia in mod detaliat. Vom caracteriza numerele care admit radacini

primitive si vom da structura generala a grupului unitatilor inelului de resturi

modulo n. De asemenea, vom enunta conjectura lui Artin referitoare la radacini

primitive si pe baza ei vom formula si demonstra un rezultat oarecum asem-

anator (dar mult, mult mai slab).

In ultimul capitol vom vedea si niste aplicatii diverse ale teoriei prezentate.

Astfel, vom avea o aplicatie de natura teoretica (studiul congruentelor binome),

aplicatii de natura problemistica (folosirea radacinilor primitive in solutia unor

probleme) si chiar si o aplicatie care poate fi considerata ”curiozitate matemat-

ica” sau ”matematica distractiva” (numere ciclice si legatura lor cu radacinile

primitive).

2

Cuprins

1 Rezultate preliminarii 4

1.1 Divizibilitate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Congruente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.3 Resturi patratice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2 Radacini primitive 16

2.1 Ordinul unui numar modulo n . . . . . . . . . . . . . . . . . . . . . . 17

2.2 Radacini primitive . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.3 Existenta radacinilor primitive modulo numere prime . . . . . . . . . 22

2.4 Existenta radacinilor primitive in cazul general . . . . . . . . . . . . 24

2.5 Structura grupului U(Zn) . . . . . . . . . . . . . . . . . . . . . . . . 31

2.6 Calculul radacinilor primitive . . . . . . . . . . . . . . . . . . . . . . 34

2.7 Inegalitati referitoare la radacini primitive. Conjectura lui Artin . . 36

3 Exemple si aplicatii 43

3.1 Congruente binome . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3.2 Probleme in care apar radacinile primitive . . . . . . . . . . . . . . . 48

3.3 Numere ciclice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

3

1 Rezultate preliminarii

In acest prim capitol vom prezenta niste rezultate generale pe care le vom aplica in

cursul acestei lucrari. In mare parte ele vor fi enuntate fara demonstratie, sau va fi

data ideea generala a demonstratiei. Pentru demonstratii complete, se pot consulta

[2] sau [4].

In prima parte a acestui capitol vom incepe prin a defini relatia de divizibilitate pe

Z si prin a enunta teorema fundamentala a aritmeticii. Urmeaza enuntul teoremeii

impartirii cu rest, definitia celui mai mare divizor comun, si algoritmul lui Euclid.

La finalul primei parti se defineste notiunea de functie aritmetica, si se dau cateva

exemple de functii aritmetice clasice (d, σ, µ, ϕ), formulele lor de calcul si cateva

proprietati ale lor, alaturi cu teorema de inversiune a lui Mobius.

In a doua parte a acestui capitol vom studia relatia de congruenta modulo n pe

Z si proprietati ale acesteia. Incepem cu teorema chineza a resturilor si teoremele

lui Euler si Fermat. Apoi vom studia ecuatii cu congruente, demonstrand la final

teorema lui Lagrange referitoare la numarul solutiilor unei congruente polinomiale

modulo un numar prim.

In cea de a treia parte a acestui capitol vom trata resturile patratice modulo un

numar prim. Incepem prin a defini simbolul lui Legendre si a da niste proprietati

ale sale, apoi enuntam criteriul lui Euler, lema lui Gauss, si, in final, enuntam legea

de reciprocitate patratica a lui Gauss.

4

1.1 Divizibilitate

Definitia 1.1.1 (Divizibilitate). Fie a si b doua numere intregi. Vom spune ca a

divide b, sau, echivalent, b este divizibil cu a daca exista un numar intreg c astfel

incat b = ac. Vom nota acest fapt prin a|b sau b...a.

Definitia 1.1.2 (Numere ireductibile). Fie p ≥ 2 un numar natural. Spunem ca p

este ireductibil daca dintr-o relatie de forma p = ab rezulta a = 1 sau b = 1.

Data definitia numerelor ireductibile, putem acum sa enuntam (fara demonstratie)

urmatorul rezultat:

Teorema 1.1.3 (Teorema fundamentala a aritmeticii). Oricare ar fi numarul nat-

ural n > 1, exista numarul natural s si numerele ireductibile p1, . . . , ps astfel incat

n = p1p2 . . . ps. In plus, aceasta scriere este unica pana la o permutare a terme-

nilor, adica daca n = p1p2 . . . ps = q1q2 . . . qt cu (pi)1≤i≤s si (qj)1≤j≤t sunt numere

ireductibile, si in plus p1 ≤ p2 ≤ . . . ≤ ps si q1 ≤ q2 ≤ . . . ≤ qt, atunci s = t si

pi = qi pentru orice 1 ≤ i ≤ s.

Corolarul 1.1.4. Oricare ar fi numarul natural n > 1, exista numerele ireductibile

p1, . . . , ps distincte oricare doua si numerele naturale nenule a1, . . . as astfel incat

n = pa11 · pa22 · . . . · pass . In plus, aceasta scriere este unica pana la o permutare a

indicilor.

De fapt, cand ne referim la ultimele doua rezultate, numim numerele ireductibile ce

apar in aceste rezultate ca fiind prime. Mai jos vom enunta propozitia ce leaga cele

doua notiuni.

Definitia 1.1.5 (Numere prime). Fie p ≥ 2 un numar natural. Spunem ca p este

prim daca din p|ab rezulta ca p|a sau p|b.

Propozitia 1.1.6. Un numar natural este ireductibil daca si numai daca este prim.

Vom continua prin a enunta o alta teorema importanta, care sta la baza multor

rezultate care vor fi enuntate sau demonstrate pe parcurs.

Teorema 1.1.7 (Teorema impartirii cu rest). Fie a si b doua numere intregi, iar b

nenul. Atunci exista si sunt unice numerele intregi q si r astfel incat a = bq + r si

0 ≤ r < |b|.

5

Demonstratie. Vom da doar ideea demonstratiei: consideram multimea

S ={a− bk | k ∈ N, a− bk ≥ 0

}⊂ N.

Aceasta multime are un cel mai mic element, iar acela este chiar r.

Definitia 1.1.8. Numerele q si r din teorema de mai sus se numesc catul respectiv

restul impartirii lui a la b.

In cele ce urmeaza, vom defini o alta notiune foarte des intalnita, cea de cel mai mare

divizor comun, si vom prezenta algoritmul lui Euclid pentru determinarea acestuia,

efectiv aplicand teorema anterioara.

Definitia 1.1.9 (Cel mai mare divizor comun). Fie a si b doua numere intregi.

Numarul d se numeste cel mai mare divizor comun al numerelor a si b si se noteaza

(a, b) daca satisface urmatoarele proprietati:

i) d|a si d|b

ii) Daca d′ este un numar ce satisface d′|a si d′|b, atunci d′|d.

iii) d > 0

Definitia 1.1.10 (Numere prime intre ele). Numerele a si b se numesc prime intre

ele sau relativ prime daca (a, b) = 1.

Existenta, unicitatea si un mod de calcul pentru cel mai mare divizor comun sunt

toate date de urmatorul rezultat ce poarta numele de algoritmul lui Euclid.

Teorema 1.1.11 (Algoritmul lui Euclid). Fie a si b doua numere intregi, iar b

nenul. Vom construi sirul r0, r1, r2, . . ., cu r0 = a, r1 = b iar rn+1 va fi restul

impartirii lui rn−1 la rn (conform teoremei 1.1.7); evident rn+1 va fi definit doar

pentru rn > 0. Atunci ultimul element nenul din sir este chiar (a, b).

Demonstratie. Din nou vom da doar ideea demonstratiei: din 1.1.7 vom avea ca

r0 > r1 > . . . si cum nu putem avea un sir infinit strict descrescator de numere

naturale rezulta ca exista un indice n pentru care rn > 0, rn+1 = 0. Se poate arata

ca rn|rn−1, rn|rn−2, si asa mai departe , urmand ca rn|r1 = b, rn|r0 = a. Apoi daca

d′|a , d′|b, se poate arata inductiv ca d′|r2 , d′|r3, si asa mai departe, urmand ca

d′|rn. Astfel, rn = (a, b).

6

Teorema 1.1.12. Fie a si b doua numere intregi si (a, b) = d. Atunci exista

numerele intregi x si y astfel incat ax+ by = d.

Demonstratie. Ideea demonstratiei este sa luam cel mai mic element al multimii

S = {ax+ by | x, y ∈ Z, ax+ by > 0} ⊂ N.

Se arata ca acest element este chiar d.

Corolarul 1.1.13. Fie a si b doua numere intregi. Atunci a si b sunt prime intre

ele daca si numai daca exista numerele intregi x si y astfel incat ax+ by = 1.

In cele ce urmeaza vom defini cateva functii artimetice ”clasice” si formulele lor de

calcul, avand la baza scrierea din corolarul 1.1.4. Prin functie aritmetica intelegem

o functie avand ca domeniu de definitie multimea N∗ a numerelor naturale nenule.

Definitia 1.1.14 (Numarul divizorilor lui n). Fie n ≥ 2 un numar natural. Vom

nota cu d(n) numarul divizorilor pozitivi ai lui n. Daca n = pa11 · . . . ·pakk , atunci are

loc formula

d(n) = (a1 + 1)(a2 + 1) . . . (ak + 1).

Demonstratie. Ideea demonstratiei este ca orice divizor pozitiv al lui n se scrie sub

forma pb11 · . . . · pbkk , cu 0 ≤ bi ≤ ai pentru orice 1 ≤ i ≤ k.

Definitia 1.1.15 (Suma divizorilor lui n). Fie n ≥ 2 un numar natural. Vom nota

cu σ(n) suma divizorilor pozitivi ai lui n. Daca n = pa11 · . . . · pakk , atunci are loc

formula

σ(n) =pa1+11 − 1

p1 − 1· . . . ·

pak+1k − 1

pk − 1.

Demonstratie. Ideea demonstratiei are in vedere calculul sumei tuturor divizorilor

lui n scrisi sub forma din demonstratia teoremei anterioare:

∑b1≤a1,...,bk≤ak

pb11 . . . pbkk =k∏i=1

(1 + pi + . . .+ paii

),

iar membrul drept se poate reduce imediat la forma dorita.

Definitia 1.1.16 (Functia lui Mobius). Functia lui Mobius se defineste astfel: µ :

N∗ → Z, unde µ(n) este dat de:

7

µ(n) =

1, daca n = 1;

0, daca exista p prim astfel incat p2|n;

(−1)k, daca n = p1p2 . . . pk cu p1, p2, . . . , pk prime distincte.

Referitor la functia lui Mobius vom enunta urmatoarea teorema:

Teorema 1.1.17 (Teorema de inversiune a lui Mobius). Fie f : N∗ → C o functie

aritmetica. Definim F : N∗ → C ca fiind F (n) =∑d|n

f(d). Atunci are loc identitatea

f(n) =∑d|n

F (d) · µ(nd

)=∑d|n

µ(d) · F(nd

).

Definitia 1.1.18 (Indicatorul lui Euler). Fie n un numar natural nenul. Vom nota

cu ϕ(n) numarul numerelor mai mici decat n si relativ prime cu n.

Vom da si doua rezultate foarte importante referitoare la functia ϕ:

Propozitia 1.1.19. Fie n un numar natural nenul. Atunci n =∑d|n

ϕ(d).

Demonstratie. Vom prezenta si o demonstratie aici. Fie A =

{1

n,

2

n, . . . ,

n

n

}multi-

mea fractiilor mai mici sau egale cu 1, avand numitorul n. Mai departe, vom nota

cu Ad multimea fractiilor din A care in forma ireductibila au numitorul d. Are rost

sa definim Ad doar pentru d|n, iar multimile Ad cand d parcurge toti divizorii lui n

formeaza o partitie a lui A. Cum

Ad =

{k

n

∣∣∣ exista l, cu 1 ≤ l ≤ d si (l, d = 1) astfel incatk

n=l

d

},

se poate observa usor ca |Ad| = ϕ(d). Asadar n = |A| =∑d|n

|Ad| =∑d|n

ϕ(d), si

demonstratia se incheie.

Propozitia 1.1.20. Fie n = pa11 · . . . · pakk un numar natural nenul scris conform

corolarului 1.1.4. Atunci are loc formula:

ϕ(n) = n

(1− 1

p1

)(1− 1

p2

). . .

(1− 1

pk

).

Demonstratie. Ideea demonstratiei aici este sa aplicam teorema de inversiune a lui

Mobius (teorema 1.1.17) pentru f(n) = ϕ(n). Folosind propozitia anterioara, rezulta

ca F este functia identitate, deci:

8

ϕ(n) =∑d|n

µ(d) · nd

,

si mai departe se calculeaza direct.

Vom incheia aceasta prima parte cu un rezultat ce caracterizeaza functiile d(n), σ(n), ϕ(n).

Definitia 1.1.21. O functie aritmetica f se numeste multiplicativa daca pentru

orice m,n prime intre ele are loc relatia f(mn) = f(m) · f(n).

Propozitia 1.1.22. Functiile d, σ si ϕ definite anterior sunt functii aritmetice

multiplicative.

9

1.2 Congruente

Fie n un numar natural nenul si a, b doua numere intregi. Vom spune ca a este

congruent cu b modulo n daca n|a − b. Vom nota acest fapt prin a ≡ b (mod n).

Relatia de congruenta astfel definita este o relatie de echivalenta. Vom nota multi-

mea claselor de echivalenta cu Zn. Clasa de echivalenta corespunzatoare lui a este

a = {a + nk | k ∈ Z}. Vom numi aceasta relatie de echivalenta congruenta modulo

n.

Definitia 1.2.1 (Sistem complet de resturi). Un sistem de reprezentanti pentru

relatia de congruenta modulo n se numeste sistem complet de resturi modulo n.

Definitia 1.2.2 (Sistem redus de resturi). Fie S un sistem complet de resturi mod-

ulo n. Vom considera R = {s ∈ S | (s, n) = 1} corespunzator reprezentantilor care

sunt relativ primi cu n. Un astfel de R se numeste sistem redus de resturi modulo

n.

Teorema 1.2.3 (Teorema chineza a resturilor). Fie n ≥ 2 un numar natural,

m1,m2, . . . ,mn numere intregi prime intre ele oricare doua si a1, a2, . . . , an numere

intregi oarecare. Atunci exista o solutie pentru sistemul de congruente:

x ≡ a1 (mod x1)

x ≡ a2 (mod x2)...

x ≡ an (mod xn)

Demonstratie. Ideea demonstratiei este urmatoarea: fie M = m1m2 . . .mn si Mi =

M/mi pentru orice i. Se arata ca (mi,Mi) = 1, si apoi, conform corolarului 1.1.13

exista numerele ri, si astfel incat rimi + siMi = 1. Notand ei = siMi, se arata ca

x =n∑i=1

aiei este solutie a sistemului de congruente.

Putem observa ca (Zn,+, ·) este un inel comutativ, unde operatiile + si · sunt cele

”naturale”: a + b = a+ b si a · b = a · b. Folosind notatia standard, fie U(Zn)

multimea elementelor inversabile din Zn. Se poate arata (folosind corolarul 1.1.13)

ca, de fapt, clasele din U(Zn) corespund numerelor ce sunt prime cu n, altfel spus

U(Zn) = {a | (a, n) = 1}. Din aceasta scriere rezulta ca |U(Zn)| = ϕ(n). Mai mult,

U(Zn) formeaza un grup cu operatia de inmultire. De aici urmeaza o consecinta

imediata:

10

Teorema 1.2.4 (Teorema lui Euler). Fie n ≥ 2 un numar natural si a un numar

intreg prim cu n. Atunci aϕ(n) ≡ 1 (mod n).

Demonstratie. Ideea demonstratiei are la baza grupul(U(Zn), ·

). Ordinul acestui

grup este chiar ϕ(n), deci (a)ϕ(n) = 1.

Corolarul 1.2.5 (Teorema lui Fermat). Fie p un numar prim si a un numar intreg

nedivizibil cu p. Atunci ap−1 ≡ 1 (mod p).

Definitia 1.2.6. Fie n ≥ 2 un numar natural si a un numar prim cu n. Numim

ordinul lui a modulo n cel mai mic numar k ce satisface congruenta ak ≡ 1 (mod n).

Din teorema lui Euler (1.2.4), astfel de numere exista pentru orice a prim cu n, deci

definitia are sens. In capitolul urmator vom relua aceasta notiune si o vom studia

in amanunt, aici am dat doar definitia.

In continuare, ne vom indrepta atentia acum asupra ecuatiilor de forma f(x) ≡ 0

(mod n). Daca vom fixa S ca fiind un sistem complet de resturi modulo n, prin

numarul solutiilor ecuatiei f(x) ≡ 0 (mod n) ne referim la numarul solutiilor din S

ale acestei ecuatii. Acest numar nu depinde de alegerea lui S, deci in general vom

considera S = {0, 1, . . . , n− 1}.

Propozitia 1.2.7. Fie n ≥ 2 un numar natural si a un numar intreg prim cu

n. Atunci ecuatia ax ≡ b (mod n) are o solutie unica modulo n, si aceasta este

x = b · aϕ(n)−1.

Demonstratie. Ideea demonstratiei are la baza teorema lui Euler (1.2.4), se poate

vedea clar ca ax ≡ b (mod n). Apoi se arata ca orice doua solutii x, y satisfac x ≡ y(mod n).

Corolarul 1.2.8. Fie n ≥ 2 un numar natural si a un numar intreg, astfel incat

(a, n) = d. Atunci ecuatia ax ≡ b (mod n) are solutii daca si numai daca d|b, iar

numarul solutiilor in acest caz este exact d.

Continuam cu un rezultat important in legatura cu numarul solutiilor unei ecuatii

polinomiale de forma f(x) ≡ 0 (mod p), unde f(x) = anXn + . . .+ a1X + a0, iar p

este un numar prim.

11

Teorema 1.2.9 (Teorema lui Lagrange). Fie f(x) = anXn + . . . + a1X + a0 un

polinom si p un numar prim care nu divide an. Atunci congruenta f(x) ≡ 0 (mod p)

are cel mult n solutii.

Demonstratie. Vom da si o demonstratie, bazata pe inductie dupa gradul lui f .

Pentru n = 1, ajungem la ecuatia a1x ≡ −a0 (mod p), cu (a1, p) = 1 (din ipoteza).

Conform propozitiei de mai sus, aceasta ecuatie are exact o solutie, deci pasul initial

de inductie este demonstrat.

Fie acum n ≥ 2 si x0 o solutie a congruentei f(x) ≡ 0 (mod p). Atunci putem

scrie f(X) = (X − x0)g(X) + f(x0). Cum f(x0) ≡ 0 (mod p), congruenta f(x) ≡ 0

(mod p) este echivalenta cu congruenta (x−x0)g(x) ≡ 0 (mod p). Dar p este prim,

deci daca x este o solutie a ecuatiei f(x) ≡ 0 (mod p), atunci avem ca x ≡ x0

(mod p) sau g(x) ≡ 0 (mod p). Avand in vedere sensul numarului de solutii a unei

ecuatii (explicat mai sus), solutiile cu x ≡ x0 (mod p) reprezinta de fapt aceeasi

solutie. Ramane sa ne uitam la solutiile care satisfac g(x) ≡ 0 (mod p); din definitia

lui g, acesta are gradul n − 1, deci conform ipotezei de inductie, el va avea cel

mult n − 1 solutii. Deci ecuatia f(x) ≡ 0 (mod p) are cel mult n solutii, si astfel

demonstratia se incheie.

Aplicand aceasta teorema pentru f(X) = Xp−1−1− (X−1)(X−2) . . . (X−p+ 1),

se obtine o alta teorema clasica:

Teorema 1.2.10 (Wilson). Fie p un numar prim. Atunci (p−1)!+1 ≡ 0 (mod p).

Demonstratie. Ideea demonstratiei este ca polinomul f(X) amintit mai sus are

gradul cel mult p − 2, dar are p − 1 solutii (toate numerele de la 1 la p − 1).

Din teorema lui Lagrange va trebui ca toti coeficientii lui f sa fie divizibili cu p, in

particular si termenul liber al acestuia.

12

1.3 Resturi patratice

Fie p un numar prim si a un numar intreg nedivizibil prin p. Spunem ca a este rest

patratic modulo p daca congruenta x2 ≡ a (mod p) are solutii. Daca a nu este rest

patratic modulo p, atunci il vom numi nerest patratic modulo p.

Definitia 1.3.1 (Simbolul lui Legendre). Fie p ≥ 3 un numar prim, si a un numar

intreg nedivizibil prin p. Vom defini simbolul lui Legendre al lui a in raport cu p,

notat(ab

), astfel:

(a

p

)=

1, daca a este rest patratic modulo p;

−1, daca a nu este rest patratic modulo p.

Se observa ca daca ecuatia x2 ≡ a (mod p) are solutii, atunci ea are exact doua

(daca α este solutie, atunci si −α este solutie). Simbolul lui Legendre poate fi

extins la Z definind

(a

p

)= 0 pentru acei a divizibili prin p. Se vede imediat ca

daca a ≡ b (mod p), atunci

(a

p

)=

(b

p

).

Propozitia 1.3.2. Fie p un numar prim impar. Atunci intr-un sistem redus de

resturi modulo p exista exact p−12 resturi patratice modulo p si implicit exact p−1

2

neresturi patratice modulo p.

Demonstratie. Ideea demonstratiei este sa aratam ca 12, 22, . . . ,(p−12

)2sunt resturi

patratice distincte modulo p, si ca orice alt rest patratic modulo p se afla printre

ele.

Pentru a determina daca un numar a este sau nu rest patratic modulo p, este util

urmatorul criteriu:

Teorema 1.3.3 (Criteriul lui Euler). Fie p un numar prim impar si a un numar

intreg nedivizibil prin p. Atunci

(a

p

)≡ a

p−12 (mod p).

Demonstratie. Ideea demonstratiei este ca solutiile ecuatiei xp−12 ≡ 0 (mod p) sunt

chiar resturile patratice modulo p si numai acestea, in numar de exact p−12 .

Corolarul 1.3.4. Fie p un numar prim impar. Atunci:

13

(−1

p

)=

1, daca p ≡ 1 (mod 4);

−1, daca p ≡ 3 (mod 4).

Tot folosind criteriul lui Euler se poate arata si urmatoarea proprietate a simbolului

lui Legendre:

Propozitia 1.3.5. Fie p ≥ 3 un numar prim si a, b doua numere intregi nedivizibile

prin p. Atunci

(ab

p

)=

(a

p

)·(b

p

).

Demonstratie. Demonstratia este imediata:(ab

p

)≡ (ab)

p−12 ≡ a

p−12 b

p−12 ≡

(a

p

)·(b

p

)(mod p),

si cum simbolul lui Legendre ia valorile ±1 si p ≥ 3, concluzia e evidenta.

Vom da acum un alt criteriu pentru determinarea lui

(a

p

). Fie

S =

{p− 1

2, . . . ,−1, 1, . . . ,

p− 1

2

}sistemul ”celor mai mici” resturi modulo p. Se observa ca S este un sistem redus de

resturi modulo p. Notam S+ si S− submultimile lui S formate din elemente pozitive

respectiv negative. Fie acum a un numar intreg nedivizibil prin p, si l ∈ S+. Atunci

exista un unic al ∈ S astfel incat a · l ≡ al (mod p). Introducem urmatoarea notatie:

γa =∣∣∣{l ∣∣∣ l ∈ S+ si al ∈ S−

}∣∣∣.Atunci are loc urmatorul rezultat:

Lema 1.3.6 (Lema lui Gauss). Fie p un numar prim impar si a un numar intreg

nedivizibil prin p. Fie γa cel definit mai sus. Atunci

(a

p

)= (−1)γa.

Demonstratie. Ideea demonstratiei aici este sa consideram a1, a2, . . . , a p−12∈ S+

astfel incat a · j ≡ ±aj (mod p), pentru orice jinS+. Numarul congruentelor cu

semn minus este chiar γa. Se poate arata ca definitia are sens, si ca aplicatia j 7→ aj

este o bijectie de la S+ la S+. Astfel,∏j∈S+

j =∏j∈S+

aj . Deci:

(p− 1

2

)! =

∏j∈S+

aj ≡ (−1)γa ·∏j∈S+

(a · j) ≡ (−1)γa · ap−12 ·

(p− 1

2

)! (mod p),

14

si apoi din criteriul lui Euler (1.3.3) rezulta concluzia.

Cel mai important rezultat referitor la resturi patratice este legea de reciprocitate

patratica a lui Gauss. Vom enunta mai jos teorema, fara demonstratie:

Teorema 1.3.7 (Legea de reciprocitate patratica). Fie p ≥ 3 un numar prim.

Atunci sunt adevarate urmatoarele:

1)

(−1

p

)= (−1)

p−12 ;

2)

(2

p

)= (−1)

p2−18 ;

3) daca q ≥ 3 este un numar prim diferit de p, atunci:(p

q

)·(q

p

)= (−1)

p−12· q−1

2 .

15

2 Radacini primitive

In acest capitol vom prezenta teoria referitoare la radacini primitive. In prima

parte vom studia amanuntit proprietatile ordinului unui numar modulo n, multe

din propozitii fiind de baza pentru teoria care urmeaza.

In cea de-a doua parte vom introduce notiunea de radacina primitiva si vom vedea

cateva exemple pentru numere mici. De asemenea, incepem sa descoperim primele

proprietati ale acestora.

In partea a treia vom demonstra teorema foarte importanta cum ca orice numar

prim admite o radacina primitiva. Mai departe, in partea a patra, vom extinde

acest rezultat si vom caracteriza complet toate numerele ce admit radacini primi-

tive, si anume 2, 4, pk si 2pk pentru p prim impar si k natural.

In partea a cincea vom analiza ce se intampla modulo 2k pentru k ≥ 3. Vom vedea

ca in acest caz nu exista radacini primitive, dar grupul U(Z2k)

are ca generatori pe

−1 si 5. Stiind acest rezultat vom putea caracteriza structura grupului U(Zn) pentru

orice n natural. In partea a sasea vom discuta despre calculul radacinilor primitive

modulo numere prime vazand ca in general determinarea unei radacini primitive

modulo p este o problema dificila. De asemenea, vom prezenta un algoritm simplu

(dar nu si eficient) pentru determinarea celei mai mici radacini primitive modulo p.

In partea a saptea vom prezenta anumite rezultate referitoare la radacini primi-

tive, niste margini inferioare si superioare, si cel mai notabil conjectura lui Artin.

Pornind de la enuntul conjecturii, vom formula un rezultat mult mai slab (dar totusi

interesant) si il vom demonstra.

16

2.1 Ordinul unui numar modulo n

In capitolul anterior am definit notiunea de ordin al unui numar intreg modulo un

numar dat. Mai jos vom studia pe larg aceasta notiune. Fie n ≥ 2 un numar natural

fixat si a un numar intreg prim cu n. Sa incepem prin a defini multimea:

E ={k ∈ N∗ | ak ≡ 1 (mod n)

}.

Conform teoremei lui Euler (1.2.4), ϕ(n) ∈ E, deci E 6= ∅. In concluzie, E are un cel

mai mic element - acela se va numi ordinul lui a modulo n. Astfel, am reluat definitia

1.2.6 data in capitolul anterior. Vom nota ordinul lui a modulo n cu ordn(a).

Drept exemple, sa luam n = 7 si sa calculam ord7(2) si ord7(3). Pentru a = 2, avem

21 ≡ 2 (mod 7), 22 ≡ 4 (mod 7), 23 ≡ 1 (mod 7),

deci ord7(2) = 3. Daca luam a = 3, vom avea

31 ≡ 3 (mod 7), 32 ≡ 2 (mod 7), 33 ≡ 6 (mod 7),

34 ≡ 4 (mod 7), 35 ≡ 2 (mod 7), 36 ≡ 1 (mod 7),

asadar ord7(3) = 6.

Pentru a caracteriza multimea E introdusa mai sus (si implicit toate solutiile con-

gruentei ax ≡ 1 (mod n) cu a si n date), vom da urmatoarea teorema:

Teorema 2.1.1. Fie n ≥ 2 un numar natural si a un numar intreg prim cu n.

Atunci ak ≡ 1 (mod n) daca si numai daca ordn(a) divide k.

Demonstratie. ” =⇒ ”: Fie k astfel incat ak ≡ 1 (mod n). Sa notam o = ordn(a).

Conform teoremei impartirii cu rest (1.1.7), exista numerele q si r astfel incat k =

qo+ r, cu 0 ≤ r < o. Vom arata ca ar ≡ 1 (mod n). Intr-adevar:

1 ≡ ak ≡ aqo+r ≡ (ao)q · ar ≡ ar (mod n),

deoarece ao ≡ 1 (mod n). In concluzie, ar ≡ 1 (mod n). Dar r < o, deci trebuie sa

avem r = 0, altfel am contrazice definitia lui o = ordn(a). Asadar o|r.”⇐= ”: Din nou notam o = ordn(a) si presupunem ca o|k. Atunci k = oq, si rezulta

imediat ca ak ≡ (aq)o ≡ 1 (mod n).

17

Ca sa continuam exemplul de mai sus, sa luam tot n = 7 si a = 2. Am vazut ca

ord7(2) = 3, asadar putem aplica teorema de mai sus pentru a deduce ca 210 6≡ 1

(mod 7), dar 215 ≡ 1 (mod 7).

O consecinta imediata a teoremei de mai sus este urmatorul rezultat:

Corolarul 2.1.2. Fie n ≥ 2 un numar natural si a un numar intreg prim cu n.

Atunci ordn(a) divide ϕ(n).

Demonstratie. Conform teoremei lui Euler (1.2.4), avem ca aϕ(n) ≡ 1 (mod n).

Aplicand teorema de mai sus, rezulta ca ordn(a) divide ϕ(n).

Putem utiliza acest corolar pentru a calcula valori ale ordinului pentru numere mici.

Sa luam spre exemplu n = 17 si a = 5. Cum divizorii lui ϕ(17) = 16 sunt 1, 2,

4, 8 si 16, din corolarul anterior acestea sunt toate valorile posibile ale lui ord17(5).

Avem

51 ≡ 5 (mod 17), 52 ≡ 8 (mod 17), 54 ≡ 13 (mod 17),

58 ≡ 16 (mod 17), 516 ≡ 1 (mod 17),

deci ord17(5) = 16.

Vom da acum un alt rezultat important care rezulta imediat din teorema 2.1.1:

Teorema 2.1.3. Fie n ≥ 2 un numar natural si a un numar intreg prim cu n.

Atunci ai ≡ aj (mod n) daca si numai daca i ≡ j (mod ordn(a)).

Demonstratie. Sa presupunem ca i > j. Atunci ai ≡ aj (mod n) daca si numai daca

ai−j · aj ≡ aj (mod n), daca si numai daca ai−j ≡ 1 (mod n). Folosind teorema

2.1.1, acest fapt este echivalent cu ordn(a)|i− j, adica i ≡ j (mod ordn(a)).

Sa luam un exemplu: fie n = 14 si a = 3. Avem ca ϕ(14) = 6, deci ord14(3) poate

fi 1, 2, 3 sau 6. Este evident ca ordinul nu poate fi 1, si observam ca

32 ≡ 9 (mod 14), 33 ≡ 13 (mod 14), 36 ≡ 1 (mod 14),

deci ord14(3) = 6. De aici putem trage concluzia ca 35 ≡ 311 (mod 14), deoarece

6 divide 11 − 5. De asemenea, putem trage concluzia ca 39 6≡ 320, deoarece 6 nu

divide 20− 9.

18

Vom incheia aceasta parte cu o teorema care ne permite sa calculam ordinul puterilor

lui a stiind ordinul lui a.

Teorema 2.1.4. Fie n ≥ 2 un numar natural si a un numar intreg prim cu n.

Notam t = ordn(a), si fie u un numar natural. Atunci ordn(au) = t/(t, u).

Demonstratie. Notam s = ordn(au) si d = (t, u). Vom arata ca s si t/d se divid

reciproc, si in concluzie ele vor fi egale.

Cum (au)t/d ≡ (at)u/d ≡ 1 (mod n) (deoarece u/d este un numar intreg), rezulta

din teorema 2.1.1 ca t/d divide s.

Pe de alta parte, aus ≡ (au)s ≡ 1 (mod n), deci tot conform teoremei 2.1.1 rezulta

ca us divide t. Cum d = (t, u), rezulta ca s divide t/d.

Din cele doua relatii de mai sus rezulta ca s = t/d si demonstratia se incheie.

19

2.2 Radacini primitive

Dupa cum am vazut in capitolul anterior, pentru n ≥ 2 natural si a intreg prim cu

n, intotdeauna vom avea ordn(a) = ϕ(n). Ne punem acum intrebarea daca exista

numere a care sa aiba ordinul modulo n chiar egal cu ϕ(n). Vom vedea ca astfel de

numere a exista doar pentru anumite valori ale lui n. De asemenea, intr-o astfel de

situatie, primele ϕ(n) puteri ale lui a vor da un sistem redus de resturi modulo n.

Sa dam deci definitia:

Definitia 2.2.1. Fie n ≥ 2 un numar natural si a un numar intreg prim cu n.

Atunci a se numeste radacina primitiva modulo n daca ordn(a) = ϕ(n).

Dupa cum am vazut intr-un exemplu anterior, ord7(3) = 6 = ϕ(7). Deci 3 este o

radacina primitiva modulo 7. 2 nu este o radacina primitiva modulo 7, deoarece

ord7(2) = 3 6= ϕ(7).

In paragraful anterior am mentionat ca doar anumite valori ale lui n admit astfel

de radacini primitive. In partile cele ce urmeaza, vom caracteriza complet toate

numerele n care admit radacini primitive. Pentru moment, sa luam insa exemplul

n = 8. Numerele intregi mai mici decat 8 care sunt relativ prime cu acesta sunt 1,

3, 5 si 7. Vedem ca ord8(1) = 1 si ord8(3) = ord8(5) = ord8(7) = 2, dar ϕ(8) = 4.

Asadar putem concluziona ca nu exista radacini primitive modulo 8.

Mai sus am mentionat ca daca r este o radacina primitiva modulo n, atunci primele

ϕ(n) puteri ale lui r dau un sistem redus de resturi modulo n. Sa demonstram acest

fapt:

Teorema 2.2.2. Fie n ≥ 2 un numar natural care admite radacini primitive si r o

radacina primitiva modulo n. Atunci numerele

r1, r2, . . . , rϕ(n)

formeaza un sistem redus de resturi modulo n.

Demonstratie. Trebuie sa demonstram doua lucruri: ca fiecare din numerele de mai

sus este relativ prim cu n si ca oricare doua sunt necongruente modulo n.

Cum (r, n) = 1, rezulta imediat ca (rk, n) = 1 pentru orice k natural, deci toate

puterile lui r sunt relativ prime cu n. Sa aratam acum partea a doua, si anume fie

20

ri ≡ rj (mod n), cu 1 ≤ i, j ≤ ϕ(n). Din teorema 2.1.1 rezulta ca ordn(r) = ϕ(n)

divide i− j, dar cum i, j sunt intre 1 si ϕ(n), trebuie ca i = j. Asadar oricare doua

din puterile lui r din enuntul teoremei sunt necongruente modulo n, si demonstratia

se incheie.

Sa presupunem in continuare ca n ≥ 2 admite radacini primitive. Ne punem acum

intrebarea daca exista mai multe radacini primitive, si in caz afirmativ, care este

numarul lor (bineinteles, referindu-ne la valori distincte modulo n). Folosind teo-

rema anterioara si teorema 2.1.4 din partea precedenta, vom raspunde la aceasta

intrebare. Incepem cu urmatorul rezultat:

Propozitia 2.2.3. Fie n ≥ 2 un numar natural si r o radacina primitiva modulo

n. Atunci rk este, la randul sau, radacina primitiva modulo n daca si numai daca(k, ϕ(n)

)= 1.

Demonstratie. Fie k natural. Vom folosi teorema 2.1.4: cum ordn(r) = ϕ(n),

ordn(rk) = ϕ(n)/(k, ϕ(n)

). Pentru ca rk sa fie radacina primitiva modulo n, trebuie

sa aiba ordinul ϕ(n), si concluzia este clara.

Folosind propozitia de mai sus si teorema anterioara (2.2.2), vom putea da urmatorul

rezultat:

Teorema 2.2.4. Fie n ≥ 2 un numar natural ce admite cel putin o radacina primi-

tiva. Atunci exista exact ϕ(ϕ(n)

)radacini primitive modulo n, necongruente oricare

doua.

Demonstratie. Fie r o radacina primitiva modulo n. Atunci conform teoremei 2.2.2,

rezulta ca numerele r, r2, . . . , rϕ(n) formeaza un sistem redus de resturi modulo n.

Din propozitia de mai sus stim ca rk este o radacina primitiva modulo n daca si

numai daca(k, ϕ(n)

)= 1. Cum exista exact ϕ

(ϕ(n)

)astfel de intregi k intre 1 si

ϕ(n), concluzia rezulta imediat.

Sa luam un exemplu. Se poate verifica usor ca 2 este radacina primitiva modulo

11. Cum ϕ(11) = 10, aplicand teorema anterioara rezulta ca exista exact ϕ(10) = 4

radacini primitive modulo 11, si acestea sunt chiar 21, 23, 27, 29, adica 2, 8, 7, 6 re-

spectiv.

21

2.3 Existenta radacinilor primitive modulo numere prime

Pana acum am dat anumite proprietati ale radacinilor primitive in cazul in care ele

exista. Sa analizam acum in ce cazuri exista astfel de radacini primitive. Este natu-

ral sa incepem cu numerele prime. Pe parcursul acestei parti vom lucra deci modulo

p unde p este un numar prim. Rezultatul fundamental pe care il vom demonstra

este ca orice numar prim admite radacini primitive.

Vom incepe cu urmatorul rezultat:

Teorema 2.3.1. Fie p un numar prim si d un divizor al lui p− 1. Atunci ecuatia

xd ≡ 1 (mod p) are exact d solutii necongruente modulo p.

Demonstratie. Notam f(X) = Xd − 1. Fie p− 1 = de. Atunci avem ca

Xp−1 − 1 = Xde − 1 = f(X)(Xd(e−1) +Xd(e−2) + . . .+ 1

)= f(X)g(X),

unde deg g = p − 1 − d. Conform teoremei lui Fermat (1.2.5), polinomul Xp−1 are

exact p− 1 radacini necongruente modulo p. In plus, din descompunerea data mai

sus, orice radacina a lui Xp−1 este o radacina fie a lui f fie a lui g. Aici va interveni

teorema lui Lagrange (1.2.9) demonstrata in capitolul 1: g are cel mult p − 1 − dradacini necongruente modulo p. In concluzie, trebuie ca f sa aiba cel putin d

radacini necongruente modulo p, dar cum deg f = d, rezulta ca ele sunt exact d la

numar.

Avand acest rezultat, impreuna cu propozitia 1.1.19, putem deduce urmatoarea

teorema:

Teorema 2.3.2. Fie p un numar prim si d un divizor al lui p − 1. Atunci exista

exact ϕ(d) elemente necongruente modulo p de ordin d.

Demonstratie. Pentru un divizor d al lui p − 1, vom nota cu N(d) numarul ele-

mentelor necongruente modulo p de ordin d. Deoarece 1, 2, . . . , p − 1 formeaza un

sistem redus de resturi modulo p si orice element are ca ordin un divizor al lui p−1,

rezulta ca

p− 1 =∑d|p−1

N(d).

Reamintim propozitia 1.1.19:

22

p− 1 =∑d|p−1

ϕ(d).

Vom arata acum ca N(d) ≤ ϕ(d) pentru orice divizor d al lui p − 1. Datorita

egalitatii celor doua sume, va trebui ca N(d) = ϕ(d), si deci va rezulta concluzia.

Sa aratam acum ca N(d) ≤ ϕ(d). Daca N(d) = 0 atunci nu e nimic de demonstrat,

deci sa presupunem ca N(d) > 0. Fie asadar z un element de ordin d. Atunci reiese

imediat din teorema 2.1.3 ca numerele z, z2, . . . , zd sunt oricare doua necongruente

modulo p. De asemenea, oricare din aceste numere satisface ecuatia xd ≡ 1 (mod p).

Intr-adevar:

(zk)d ≡ (zd)k ≡ 1 (mod p).

Conform teoremei 2.3.1, rezulta ca aceste numere sunt toate radacinile necongruente

modulo p ale ecuatiei, altfel spus, daca y satisface yd ≡ 1 (mod p) atunci y ≡ zk

(mod p) pentru un anumit k. Cum orice element de ordin d satisface aceasta ecuatie,

rezulta ca toate elementele de ordin d se numara printre primele d puteri ale lui a.

Folosim acum teorema 2.1.4: ordp(ak) = k/(k, d), deci ak are ordin d daca si numai

daca (k, d) = 1. Cum exista exact ϕ(d) astfel de valori k, rezulta ca in acest caz

avem exact ϕ(d) elemente de ordin d.

Asadar, avem ca N(d) ∈ {0, ϕ(d)}, deci N(d) ≤ ϕ(d). Folosind egalitatea sumelor

de mai sus, trebuie ca N(d) = ϕ(d) si deci teorema este demonstrata.

O consecinta imediata a acestei teoreme este chiar rezultatul pe care l-am amintit

la inceputul acestei parti:

Corolarul 2.3.3. Orice numar prim admite o radacina primitiva. Mai precis, daca

p este prim atunci exista exact ϕ(p− 1) radacini primitive modulo p.

Demonstratie. Demonstratia este imediata folosind teorema anterioara. Punand

d = p− 1, rezulta ca exista ϕ(p− 1) elemente de ordin p− 1 modulo p, iar acestea

sunt radacinile primitive modulo p.

23

2.4 Existenta radacinilor primitive in cazul general

In sectiunea precedenta am demonstrat existenta radacinilor primitive modulo nu-

mere prime. In cele ce urmeaza vom caracteriza toate numerele ce admit radacini

primitive. Sa incepem cu studiul puterilor de numere prime impare. Primul rezultat

pe care il vom demonstra este referitor la patrate de numere prime:

Teorema 2.4.1. Fie p ≥ 3 un numar prim si r o radacina primitiva modulo p.

Atunci putem alege o radacina primitiva modulo p2 dintre r si r + p.

Demonstratie. Stim ca ordp(r) = p− 1, deoarece r este radacina primitiva modulo

p. Sa notam n = ordp2(r). Pentru inceput, din corolarul 2.1.2, avem ca n divide

ϕ(p2) = p(p−1). Pe de alta parte, cum rn ≡ 1 (mod p2), rezulta ca rn ≡ 1 (mod p),

si cum p − 1 = ordp(r), rezulta din teorema 2.1.1 ca p − 1 divide n. Asadar n este

fie p(p − 1), fie p − 1. In primul caz demonstratia se incheie, deoarece obtinem

n = ϕ(p2).

Ramane sa analizam cazul n = p − 1. Fie s = r + p. Cum s ≡ r (mod p), rezulta

ca si s este o radacina primitiva modulo p, si efectuand un rationament analog vom

obtine ca ordp2(s) este fie p − 1 fie p(p − 1). Vom arata ca ordp2(s) 6= p − 1, si de

aici va rezulta concluzia.

Vom scrie s = r + p si vom dezvolta binomul sp−1:

sp−1 = (r + p)p−1 = rp−1 + (p− 1)prp−2 +

p−1∑k=2

(p− 1

k

)pkrp−1−k.

Cum termenii din ultima suma (situati la dreapta lui∑

) sunt fiecare divizibili cu

p2, vom obtine:

sp−1 ≡ rp−1 + (p− 1)prp−2 (mod p2),

si apoi tinand cont ca ordp2(r) = p − 1 (conform celor de mai sus) si (p − 1)p =

p2 − p ≡ −p (mod p2), vom obtine ca

sp−1 ≡ 1− prp−2 (mod p2).

De aici putem concluziona ca sp−1 6≡ 1 (mod p2): intr-adevar, sa presupunem con-

trariul. Atunci am obtine ca prp−2 ≡ 0 (mod p2), adica p2 divide prp−2, si de aici

am avea ca p divide rp−2, adica p divide r, contradictie cu presupunerea ca r este

radacina primitiva modulo p (ceea ce implica imediat (r, p) = 1). Asadar, trebuie

24

ca sp−1 6≡ 1 (mod p2), si deci ordp2(s) nu poate fi p− 1. Conform celor de mai sus,

ordp2(s) trebuie deci sa fie p(p− 1), adica s este o radacina primitiva modulo p2, si

demonstratia se incheie.

Sa luam doua exemple ce ilustreaza cele doua cazuri. Fie p = 7. Am vazut intr-o

sectiune anterioara ca r = 3 este o radacina primitiva modulo 7. Folosind ideea din

demonstratia anterioara, avem ca ord49(3) ∈ {6, 42}. Insa 36 6≡ 1 (mod 49), deci

trebuie ca ord49(3) = 42. In concluzie, 3 este o radacina primitiva si modulo 49.

Fie acum p = 487 si r = 10. Se poate verifica ca 10 este radacina primitiva modulo

487, si ca 10486 ≡ 1 (mod 4872). Asadar, 10 nu este radacina primitiva modulo

4872, dar, conform teoremei anterioare, trebuie ca 497 = 10 + 487 sa fie radacina

primitiva modulo 4872.

Teorema anterioara (2.4.1) demonstreaza existenta radacinilor primitive modulo p2

pentru orice numar prim impar p. Vom extinde acest rezultat la orice putere naturala

a lui p astfel:

Teorema 2.4.2. Fie p ≥ 3 un numar prim si r o radacina primitiva modulo p2.

Atunci r este radacina primitiva modulo pk pentru orice k natural.

Demonstratie. Existenta lui r este demonstrata de teorema 2.4.1, mai mult, stim ca

r este radacina primitiva modulo p (deoarece daca s este radacina primitiva modulo

p din care se obtine r conform teoremei 2.4.1, atunci fie s = r fie s = r + p ≡ r

(mod p)). Cum r este radacina primitiva modulo p2, stim ca rp−1 6≡ 1 (mod p2).

Ne propunem sa aratam prin inductie ca pentru orice k ≥ 2 are loc:

rpk−2(p−1) 6≡ 1 (mod pk).

Sa presupunem pentru moment ca acest rezultat este adevarat. Vom proceda analog

cu demonstratia teoremei 2.4.1. Fie n = ordpk(r). Conform corolarului 2.1.2 avem

ca r divide ϕ(pk) = pk−1(p − 1). Cum rn ≡ 1 (mod p), rezulta conform teoremei

2.1.1 ca p−1 = ordp(r) divide n. In concluzie, trebuie ca n = pt(p−1), cu t ≤ k−1

numar natural. Daca am avea t 6= k − 1, atunci trebuie ca t ≤ k − 2, si deci:

rpk−2(p−1) ≡

(rp

t(p−1))pk−2−t

≡ 1 (mod pk),

contradictie cu afirmatia de mai sus. In concluzie, trebuie ca t = p − 1, deci

ordpk(r) = pk−1(p− 1) = ϕ(pk), deci r este radacina primitiva modulo pk.

25

Ramane acum sa demonstram prin inductie afirmatia de mai sus. Pasul initial de

inductie (k = 2) este dat de rp−1 6≡ 1 (mod p2), ceea ce rezulta din alegerea lui r.

Sa presupunem acum ca

rpk−2(p−1) 6≡ 1 (mod pk).

pentru un k ≥ 2. Cum (r, pk−1) = 1, din teorema lui Euler (1.2.4) rezulta ca:

rpk−2(p−1) ≡ rϕ(pk−1) ≡ 1 (mod pk−1).

Asadar rpk−2(p−1) = 1 + dpk−1 pentru un anumit numar intreg d care este prim cu

p (altfel am avea pk−1 divide rpk−2(p−1) − 1, contrazicand ipoteza de inductie). Din

nou vom ridica la puterea p:

rpk−1(p−1) =

(1 + dpk−1

)p= 1 + dpk +

p∑j=2

(p

j

)(dpk−1

)j.

La fel ca in cursul teoremei 2.4.1, vedem ca suma din partea dreapta (termenii situati

la dreapta lui∑

) sunt divizibili cu pk+1. Intr-adevar, vom avea ca j(k− 1) ≥ k+ 1

pentru orice j, k ≥ 2, mai putin pentru j = 2, k = 2. In acest caz, vom folosi faptul

ca coeficientul binomial(p2

)este divizibil cu p.

In concluzie,

rpk−1(p−1) ≡ 1 + dpk (mod pk+1),

si, cum (d, p) = 1, rationand analog ca in teorema 2.4.1 vom obtine ca

rpk−1(p−1) 6≡ 1 (mod pk+1),

acest fapt demonstrand inductia, si, totodata, teorema.

Dintr-un exemplu anterior am vazut ca r = 3 este radacina primitiva modulo 7,

dar si modulo 72. Asadar, conform teoremei anterioare, 3 este radacina primitiva

modulo 7k pentru orice k natural.

Pana acum am analizat cazul puterilor de numere prime impare. Sa vedem ce se

intampla cu puterile lui 2. Vom observa imediat ca 2 si 4 admit radacini primitive,

dar dupa cum am vazut intr-un exemplu anterior, 8 nu admite astfel de radacini.

Un rezultat mai general este dat de urmatoarea teorema:

26

Teorema 2.4.3. Daca a este un numar intreg impar si k ≥ 3 este un numar natural,

atunci

aϕ(2k)/2 = a2

k−2 ≡ 1 (mod 2k).

Demonstratie. Vom folosi inductia. Pentru k = 3, avem de aratat ca a2 ≡ 1

(mod 8). Cum a este impar, exista un numar intreg b astfel incat a = 2b + 1.

Atunci

a2 = (2b+ 1)2 = 4b2 + 4b+ 1 = 4b(b+ 1) + 1,

si din faptul ca 2 divide b(b+ 1), obtinem ca 8 divide a2 − 1, deci a2 ≡ 1 (mod 8).

Astfel, pasul initial de inductie este demonstrat.

Sa presupunem acum ca

a2k−2 ≡ 1 (mod 2k)

pentru un k ≥ 3 natural. Atunci exista un numar intreg d astfel incat

a2k−2

= 1 + d · 2k.

Ridicand la patrat egalitatea anterioara vom obtine:

a2k−1

= 1 + d · 2k+1 + d2 · 22k ≡ 1 (mod 2k+1),

si astfel inductia este demonstrata.

Aceasta teorema are o consecinta imediata:

Corolarul 2.4.4. Fie k ≥ 3 natural. Atunci nu exista radacini primitive modulo

2k.

Demonstratie. Presupunem prin absurd ca ar exista o astfel de radacina r, adica

ord2k(r) = ϕ(2k) = 2k−1. Conform teoremei anterioare, avem insa ca rϕ2k/2 ≡ 1

(mod 2k), contradictie cu definitia ordinului. Deci nu pot exista astfel de radacini

primitive.

Desi ultimul rezultat afirma ca nu exista radacini primitive modulo 2k, exista insa

elemente care au ordinul ϕ(2k)/2 (care este cel mai mare ordin posibil pe care l-ar

putea avea). Acest fapt este dat de teorema urmatoare:

Teorema 2.4.5. Fie k ≥ 3 un numar natural. Atunci are loc urmatoarea egalitate:

27

ord2k(5) = ϕ(2k)/2 = 2k−2.

Demonstratie. Conform teoremei 2.4.3 avem ca

52k−2 ≡ 1 (mod 2k),

deci ord2k(5) divide 2k−2. Daca am arata ca ord2k(5) nu divide 2k−3, atunci am

terminat, deoarece ar urma ca ord2k(5) = 2k−2. Pentru aceasta, vom folosi teorema

2.1.1: vom arata ca:

52k−3 6≡ 1 (mod 2k).

De fapt, vom arata un rezultat mai tare, si anume

52k−3 ≡ 1 + 2k−1 (mod 2k).

Vom folosi inductia. Cazul k = 3 se verifica imediat: 5 ≡ 1+4 (mod 8). Presupunem

acum relatia de mai sus adevarata pentru un k ≥ 3 natural. Atunci exista un numar

intreg d astfel incat:

52k−3

= (1 + 2k−1) + d · 2k.

Ridicand la patrat, vom obtine:

52k−2

= (1 + 2k−1)2 + 2(1 + 2k−1)d · 2k + d2 · 22k.

Mai departe

52k−2 ≡ (1 + 2k−1)2 ≡ 1 + 2k + 22k−2 ≡ 1 + 2k (mod 2k+1),

si pasul de inductie este demonstrat. Astfel, am aratat ca ord2k(5) = ϕ(2k)/2 si

demonstratia se incheie.

Cu toate rezultatele pana acum am determinat ca orice putere a unui numar prim

impar admite o radacina primitiva, in timp ce singurele puteri ale lui 2 ce admit

radacini primitive sunt 2 si 4. Acum vom incerca sa vedem ce se intampla in cazul

numerelor care sunt produse de cel putin doua numere prime. Vom incepe prin a

da un rezultat care caracterizeaza numerele ce nu admit radacini primitive (in afara

de puterile lui 2)

Teorema 2.4.6. Fie n un numar natural care nu este putere a unui numar prim si

nici dublul unei puteri a unui numar prim. Atunci n nu admite radacini primitive.

28

Demonstratie. Il vom descompune pe n in factori primi. Fie deci:

n = pa11 · pa22 · . . . · p

akk .

Presupunem prin absurd ca n admite o radacina primitiva r. Atunci (r, n) = 1 si

ordn(r) = ϕ(n). De aici rezulta ca (r, paii ) = 1 pentru orice 1 ≤ i ≤ k, si conform

teoremei lui Euler (1.2.4) rezulta ca

rϕ(paii ) ≡ 1 (mod paii ).

Fie U cel mai mic multiplu comun al numerelor ϕ(pa11 ), ϕ(pa22 ), . . ., ϕ(pakk ). Cum

ϕ(paii ) divide U , rezulta conform teoremei 2.1.1 ca

rU ≡ 1 (mod paii ),

si cum numerele paii sunt prime intre ele rezulta ca

rU ≡ 1 (mod n),

si mai departe, din nou aplicand teorema 2.1.1, rezulta ca ϕ(n) divide U .

Dar numerele paii sunt prime intre ele iar ϕ este o functie aritmetica multiplicativa,

deci

ϕ(n) = ϕ(pa11 ) · ϕ(pa22 ) · . . . · ϕ(pakk ),

deci produsul numerelor ϕ(paii ) divide cel mai mic multiplu comun al lor. Acest

lucru este posibil doar cand cele doua valori sunt egale, adica atunci cand toate

numerele ϕ(paii ) sunt prime intre ele.

Dar ϕ(pm) = pm−1(m − 1), iar acest numar este par pentru orice p ≥ 3 prim, sau

in cazul p = 2 si m ≥ 2. In concluzie, printre pi nu poate aparea decat un singur

factor prim impar. Cum am presupus ca n nu este putere a unui numar prim, n are

cel putin doi factori primi distincti, deci al doilea factor prim trebuie sa fie 2. Dar

exponentul la care apare 2 trebuie sa fie chiar 1 conform celor spuse anterior. In

concluzie n = 2pm, si acest fapt contrazice ipoteza ca n sa nu fie dublul unei puteri

a unui numar prim.

Asadar am obtinut o contradictie, deci nu poate exista o radacina primitiva modulo

n, si demonstratia se incheie.

Deja am epuizat aproape toate cazurile. Am vazut ca numerele 2, 4, pk cu p ≥ 3 prim

admit radacini primitive, numerele 2k pentru k ≥ 3 nu admit radacini primitive, si

29

orice numar care nu intra in categoria celor deja mentionate si nu este de forma 2pk

cu p ≥ 3 prim nu admite radacini primitive. Ramane, deci, sa studiam numerele de

forma 2pk.

Teorema 2.4.7. Fie p ≥ 3 un numar prim impar si n = 2pk. Atunci n admite

radacini primitive. In particular, daca r este o radacina primitiva modulo pk, atunci

numarul impar dintre r si r + pt va fi radacina primitiva modulo 2pk.

Demonstratie. Enuntul teoremei ne da forma radacinii primitive pe care o cautam.

Fie deci r o radacina primitiva modulo pk. Atunci si r+pk este o radacina primitiva

modulo pk, si cum unul din aceste numere este impar, putem presupune, fara a

restrange generalitatea, ca r este impar.

Cum r este radacina primitiva modulo pk, rezulta ca

rϕ(pk) ≡ 1 (mod pk),

si ϕ(pk) este cel mai mic numar natural cu aceasta proprietate. Cum ϕ(2pk) =

ϕ(2) · ϕ(pk) = ϕ(pk), si r este impar, rezulta ca

rϕ(2pk) ≡ 1 (mod pk),

si de asemenea

rϕ(2pk) ≡ 1 (mod 2).

Din cele de mai sus reiese ca

rϕ(2pk) ≡ 1 (mod 2pk),

si evident ϕ(2pk) = ϕ(pk) este cel mai mic numar cu aceasta proprietate. In con-

cluzie, r este radacina primitiva modulo 2pk, si demonstratia se incheie.

Putem strange toate rezultatele de mai sus sub forma urmatoarei teoreme:

Teorema 2.4.8. Fie n ≥ 2 un numar natural. Atunci n admite radacini primitive

daca si numai daca n are una din formele

2, 4, pk sau 2pk

unde p ≥ 3 este un numar prim si k este un numar natural.

30

2.5 Structura grupului U(Zn)

In aceasta sectiune vom folosi rezultatele anterioare pentru a caracteriza grupul

U(Zn) pentru n ≥ 2 natural. Vom folosi o abordare mai algebrica, deci vom enunta

mai jos anumite rezultate pe care le vom folosi. Mai multe detalii pot fi gasite in [1]

sau [3].

Propozitia 2.5.1. Inelul Zn definit in primul capitol este de fapt inelul factor Z/nZ.

Teorema 2.5.2 (Teorema fundamentala de izomorfism pentru inele). Fie A si B

doua inele si f : A→ B un morfism de inele. Atunci aplicatia

F : A/ ker(f)→ f(B)

este un izomorfism de inele. Asadar A/ ker(f) ∼= Im (f).

Vom folosi aceasta teorema cat si teorema chineza a resturilor (1.2.3) pentru a stabili

urmatorul rezultat:

Teorema 2.5.3. Fie n = pa11 · pa22 · . . . · p

akk un numar intreg descompus in factori

primi. Atunci are loc urmatorul izomorfism:

Zn ∼= Zpa11 × Zpa22 × . . .× Zpakk .

Demonstratie. Fie functia f : Z→ Zpa11 × Zpa22 × . . .× Zpakk , data prin:

f(x) = (x1, x2, . . . , xk),

unde x ≡ xi (mod paii ) pentru orice 1 ≤ i ≤ k, iar clasele sunt luate corespunzator.

Se poate verifica imediat ca f este un morfism de inele. Sa determinam intai ker(f).

ker(f) ={x ∈ Z | f(x) = (0, . . . , 0)

},

adica x ≡ 0 (mod paii ) pentru orice i. Acest lucru este echivalent cu x ≡ 0 (mod n),

deci ker(f) = nZ.

Vom arata ca f este surjectiva. Fie deci (x1, x2, . . . , xk) un element din codomeniu.

Conform teoremei chineze a resturilor (1.2.3), exista un x ∈ Z astfel incat x ≡ xi

(mod paii ) pentru orice i. In concluzie

f(x) = (x1, x2, . . . , xk),

31

si acest lucru demonstreaza surjectivitatea lui f . Aplicand acum teorema de izomor-

fism enuntata mai sus, rezulta concluzia.

Corolarul 2.5.4. Fie n = pa11 · pa22 · . . . · p

akk un numar intreg descompus in factori

primi. Atunci

U(Zn) ∼= U(Zpa11

)× U

(Zpa22

)× . . .× U

(Zpakk

).

Cum scopul nostru este sa determinam structura grupului U(Zn), aceasta ultima

teorema arata ca este suficient sa determinam structura grupului U(Zpk)

unde p este

prim. Conform sectiunii precedente, pentru p ≥ 3 si k natural, exista o radacina

primitiva modulo pk. Acest fapt inseamna ca grupul U(Zpk)

este ciclic pentru p ≥ 3,

generatorii sai fiind chiar radacinile primitive. Ramane deci sa ne indreptam atentia

asupra grupului U(Z2k), unde k ≥ 3 este numar natural.

Pentru inceput, reamintim teorema 2.4.5, care spune ca ord2k(5) = 2k−2. Vom arata

acum ca

Propozitia 2.5.5. Fie k ≥ 3 natural. Atunci oricare ar fi s natural:

5s 6≡ −1 (mod 2k)

Demonstratie. Presupunem prin absurd ca exista un astfel de s. Atunci 2k divide

5s + 1, si implicit 4 divide 5s + 1. Insa 5 ≡ 1 (mod 4), deci 5s ≡ 1 (mod 4), in

conlcuzie 4 divide si 5s − 1. De aici ar rezulta ca 4 divide 2 = (5s + 1) − (5s − 1),

evident o contradictie. In concluzie, s nu poate exista.

Din aceasta ultima propozitie si din teorema 2.4.5, putem trage urmatoarea con-

cluzie:

Teorema 2.5.6. Fie k ≥ 3 un numar natural. Atunci numerele:

5, 52, . . . , 52k−2

,−5,−52, . . . ,−52k−2

formeaza un sistem redus de resturi modulo 2k.

Demonstratie. Se observa imediat ca oricare din numerele mentionate este relativ

prim cu 2k. Numarul lor este 2k−1 = ϕ(2k). Ramane doar sa aratam ca oricare

doua sunt necongruente modulo 2k. Cum ordinul lui 5 este 2k−2, nu putem avea

congruente de forma 5j ≡ 5l (mod 2k) sau −5j ≡ −5l (mod 2k) cu j 6= l. Singura

32

posibilitate ar fi 5j ≡ −5l (mod 2k). Presupunem prin absurd ca exista j 6= l cu

aceasta proprietate. Avem si ca −5j ≡ 5l (mod 2k), deci putem presupune fara a

restrange generalitatea ca j > l. In acest caz:

5j−l ≡ −1 (mod 2k),

contradictie cu propozitia anterioara. In concluzie j si l nu pot exista, si acesta a

fost singurul caz ramas. Asadar teorema este demonstrata.

Corolarul 2.5.7. Fie k ≥ 3 un numar natural. Atunci grupul U(Z2k)

este generat

de −1 si 5.

Astfel, am caracterizat si grupurile U(Z2k)

pentru k ≥ 3. Vom folosi notatia⟨r⟩n

pentru a nota subgrupul lui U(Zn) generat de r. In cazul in care r este o radacina

primitiva, vom avea evident ca⟨r⟩n

= U(Zn), si conform teoremei anterioare avem

ca U(Z2k)

=⟨−1, 5

⟩2k

pentru k ≥ 3. Vom pune cap la cap toate rezultatele

anterioare in urmatoarea teorema:

Teorema 2.5.8 (Structura lui U(Zn)). Fie n = 2e · pa11 · pa22 · . . . · p

akk , unde pi sunt

numere prime distincte, ai > 0 si e ≥ 0. Fie ri radacini primitive modulo paii pentru

i ≤ k. Atunci are loc urmatorul izomorfism:

U(Zn) ∼=⟨−1, 5

⟩2e×⟨r1

⟩pa11

×⟨r2

⟩pa22

× . . .×⟨rk

⟩pakk

.

Se observa ca in cazul e ∈ {0, 1} grupul⟨−1, 5

⟩2e

este trivial, iar in cazul e = 2 el

coincide cu⟨−1⟩22

.

Demonstratie. Folosind corolarul 2.5.4 avem ca

U(Zn) ∼= U(Z2e

)× U

(Zpa11

)× U

(Zpa22

)× . . .× U

(Zpakk

).

Din observatiile anterioare rezulta forma dorita pentru fiecare din grupurile din

membrul drept.

33

2.6 Calculul radacinilor primitive

Pana acum am caracterizat toate numerele n care admit radacini primitive si am dat

si structura generala a grupului U(Zn). Observam, insa, ca demonstratiile pentru

existenta acestor radacini nu sunt constructive, ci pur existentiale - nu ni se indica

nicio metoda de calcul pentru determinarea acestor radacini. Din pacate, nu este

cunoscut un algoritm eficient pentru a determina radacinile primitive.

Mai jos, vom prezenta un algoritm destul de simplu pentru a gasi cea mai mica

radacina primitiva modulo p unde p ≥ 3 este numar prim. Vom da intai rezultatul

care sta la baza algoritmului:

Propozitia 2.6.1. Fie p un numar prim si q1, q2, . . . , qk toti divizorii primi distincti

ai lui p− 1. Atunci r este radacina primitiva modulo p daca si numai daca

r(p−1)/qi 6≡ 1 (mod p),

oricare ar fi 1 ≤ i ≤ k.

Demonstratie. ” =⇒ ”: Daca r este radacina primitiva, atunci p − 1 este cel mai

mic numar pentru care rt ≡ 1 (mod p) si rezultatul este evident.

”⇐= ”: Fie un astfel de r cu proprietatea ca

r(p−1)/qi 6≡ 1 (mod p),

pentru orice i. Notam t = ordp(r). Vom arata ca t = p− 1. Este evident ca t divide

p − 1, asadar putem scrie p − 1 = tu, cu u natural. Presupunem prin absurd ca

t 6= p− 1, si acest fapt implica u > 1. Cum u divide p− 1, exista un indice i astfel

incat qi divide u. Putem deci scrie u = qiv, si apoi p − 1 = tqiv. Asadar t divide

(p− 1)/qi, si conform teoremei 2.1.1 avem ca

r(p−1)/qi ≡ 1 (mod p)

contradictie. Deci trebuie ca t = p − 1, asadar r este radacina primitiva modulo

p.

Folosind acest rezultat, putem determina cea mai mica radacina primitiva modulo

p printr-o cautare directa. Incercam, pe rand, numerele 2, 3, 4, . . . si vedem daca

gasim unul care satisface conditia din propozitia anterioara. Primul numar astfel

gasit este chiar radacina primitiva cautata. Iata algoritmul mai jos:

34

1. Daca p = 2, atunci afiseaza 1 si incheie. Altfel, seteaza a←− 2.

2. (Descompunerea in factori) Calculeaza q1, q2, . . . , qk divizorii primi ai

lui p− 1.

3. (Ridicare la putere) Verifica daca a(p−1)/qi 6≡ 1 (mod p) pentru fiecare

1 ≤ i ≤ k. In caz afirmativ, afiseaza a si incheie.

4. (Incrementeaza a) Seteaza a←− a+ 1.

Fara a intra in detalii, mentionam ca descompunerea in factori primi a unui numar

intreg este o problema ”dificila”, in sensul ca nu este cunoscut niciun algoritm eficient

care sa realizeze descompunerea numerelor foarte mari. De aceea, nici algoritmul de

mai sus nu poate fi considerat eficient.

35

2.7 Inegalitati referitoare la radacini primitive. Conjectura lui

Artin

Vom incepe aceasta sectiune prin a enunta anumite rezultate referitoare la cea mai

mica radacina primitiva modulo p. Fie deci gp cea mai mica radacina primitiva

modulo p. Conform [5], au loc urmatoarele rezultate:

Teorema 2.7.1 (Pillai, 1944). Exista o constanta pozitiva C si o infinitate de nu-

mere prime p astfel incat gp > C ln ln p.

Acest rezultat a fost imbunatatit de Fridlander (1949) si Sali (1950):

Teorema 2.7.2. Exista o constanta pozitiva C si o infinitate de numere prime p

astfel incat gp > C ln p.

Pe de alta parte, exista urmatoarea margine superioara pentru gp:

Teorema 2.7.3 (Burgess, 1962). Oricare ar fi ε > 0 exista o constanta pozitiva C

astfel incat, pentru orice numar p prim suficient de mare, sa aiba loc:

gp < Cpε+1/4

Teorema 2.7.4 (Grosswald, 1981). Pentru orice numar prim p > ee24

are loc

gp < p0.499.

Un alt rezultat datorat lui Powell si Kearnes (1984) afirma ca

Teorema 2.7.5. Oricare ar fi numarul natural M > 0, exista o infinitate de numere

prime p astfel incat M < gp < p−M .

Mai jos, vom da un tabel cu gp pentru toate numerele prime p < 100.

p gp p gp p gp p gp p gp

2 1 13 2 31 3 53 2 73 5

3 2 17 3 37 2 59 2 79 3

5 2 19 2 41 6 61 2 83 2

7 3 23 5 43 3 67 2 89 3

11 2 29 2 47 5 71 7 97 5

Dupa cum se vede, 2 apare destul de des in acest tabel. Acest fapt ne duce la

intrebarea naturala: exista o infinitate de numere prime p astfel incat 2 este radacina

primitiva modulo p? Sau, mai general, daca exista o infinitate de numere prime p

astfel incat a este radacina primitiva modulo p?

36

Conjectura 2.7.6 (Conjectura lui Artin). Fie a un numar intreg diferit de −1 si

care nu este patrat perfect. Atunci a este radacina primitiva modulo p pentru o

infinitate de numere p.

Conjectura nu a fost demonstrata nici pana acum. De fapt, nu este cunoscut niciun

numar intreg a pentru care conjectura sa fie adevarata. Conform [6], Hooley a

demonstrat in 1967 ca ipoteza lui Riemann generalizata implica aceasta conjectura

de mai sus. In [5] se precizeaza ca Roger Heath-Brown a stabilit in 1985 ca daca

x, y, z sunt numere intregi cu proprietatea ca singurele valori a, b, c intregi pentru

care xaybzc = 1 sunt a = b = c = 0, atunci conjectura lui Artin este adevarata

pentru cel putin unul dintre x, y, z. In particular, exista cel mult doua numere

prime pentru care conjectura lui Artin nu este adevarata.

Sa incercam sa inlocuim infinitate de numere prime p cu oricat de multe numere

prime p. Altfel spus, exista numere intregi a astfel incat a este radacina primitiva

modulo oricat de multe numere prime p? Raspunsul este afirmativ, iar rezultatul

este imediat conform teoremei chineze a resturilor (1.2.3):

Propozitia 2.7.7. Fie N > 0 natural. Atunci exista un numar natural a si nu-

merele prime distincte p1, p2, . . . , pN astfel incat a este radacina primitiva modulo

pi pentru orice 1 ≤ i ≤ N .

Demonstratie. Vom arata ca numerele p1, . . . , pN pot fi alese chiar arbitrar. Fie

deci N astfel de numere prime, si consideram ri radacina primitiva modulo pi. Cum

(pi, pj) = 1 pentru orice i 6= j, conform teoremei chineze a resturilor (1.2.3) exista

un numar intreg a ce satisface congruentele a ≡ ri (mod pi) pentru orice 1 ≤ i ≤ N .

Acest a este numarul cautat.

Vom incerca sa intarim putin rezultatul de mai sus punand conditia ca a sa fie mai

mic decat fiecare din numerele prime considerate. Astfel, prezentam urmatoarea

propozitie:

Propozitia 2.7.8. Fie N > 0 natural. Atunci exista un numar natural a si nu-

merele prime distincte p1, p2, . . . , pN astfel incat a este radacina primitiva modulo

pi pentru orice 1 ≤ i ≤ N , si, in plus, a ≤ pi pentru orice 1 ≤ i ≤ N .

Demonstratie. Presupunem prin absurd ca nu este adevarata concluzia. Pentru un

numar natural a, vom nota n(a) numarul de numere prime mai mari decat a pentru

37

care a este radacina primitiva. Astfel, exista M > 0 cu proprietatea ca n(a) < M ,

oricare ar fi a natural. Vom considera multimea:

R(n) ={

(a, p) | 1 ≤ a ≤ p ≤ n, ordp(a) = p− 1}

,

altfel spus multimea perechilor (a, p) pentru care a este radacina primitiva modulo

p, iar p ≤ n unde n este fixat. Vom numara elementele lui R(n) in doua moduri.

Pe de o parte, fiecare numar a mai mic decat n va aparea in cel mult n(a) perechi,

deci avem:

∣∣R(n)∣∣ ≤ n∑

a=1

n(a) < nM .

Pe de alta parte, pentru fiecare p ≤ n prim exista exact ϕ(p − 1) numere mai mici

decat p care sunt si radacini primitive modulo p. Asadar:∣∣R(n)∣∣ =

∑p≤n,p prim

ϕ(p− 1).

Combinand ultimele doua relatii, obtinem ca∑p≤n,p prim

ϕ(p− 1) < nM, (1)

oricare ar fi n > 0 natural. Ideea acum este sa il facem pe n suficient de mare, ca

sa putem analiza comportarea asimptotica a sumei din membrul stang.

Vom avea nevoie urmatoarele leme:

Lema 2.7.9. Fie a > 0 un numar real. Atunci are loc egalitatea:

limn→∞

1

na+1

(n∑k=1

ka

)=

1

a+ 1.

Demonstratia lemei. Fie sirul an = 1a + 2a + . . . + na, si bn = na+1. Ideea este sa

aplicam lema lui Cesaro-Stolz. Intai vom arata ca:

limn→∞

an+1 − anbn+1 − bn

= limn→∞

(n+ 1)a

(n+ 1)a+1 − na+1=

1

a+ 1(2)

Pentru a demonstra (2), o vom aduce intai la o alta forma:

(n+ 1)a

(n+ 1)a+1 − na+1=

(n+ 1− n

(n

n+ 1

)a)−1,

38

deci dupa ce dam factor comun pe n in membrul drept, putem vedea ca este suficient

sa aratam ca:

limn→∞

n

(1−

(n

n+ 1

)a)= a (3)

Vom nota x = 1/n. Atunci putem scrie relatia de mai sus ca:

limx→0

1− (1 + x)−a

x= a.

Vom aplica teorema lui L’Hopital pentru f(x) = 1 − (1 + x)−a si g(x) = x. Se

observa ca atat f cat si g au limita 0 in x = 0. Cum avem

limx→0

f ′(x)

g′(x)= lim

x→0−(−a) · (1 + x)−a−1 = a,

rezulta si ca limx→0

f(x)/g(x) = a, si deci si (3) este adevarata. In concluzie (2) este

adevarata, si deci lema este demonstrata.

Vom da acum doua leme. Prima este folosita in demonstratia celei de a doua, iar a

doua face referire la cresterea lui ϕ(n) in raport cu n.

Lema 2.7.10. Fie f : N → R+ o functie aritmetica multiplicativa cu proprietatea

ca limpm→∞

f(pm)

= 0 unde p parcurge multimea numerelor prime. Mai explicit, vom

considera subsirul numerelor naturale formate din toate numerele de forma pm cu

p prim. Limita la infinit a valorilor lui f in punctele acestui subsir este 0. Atunci

limn→∞

f(n) = 0.

Demonstratie. Pentru inceput, oricare ar fi ε > 0 exista N(ε) astfel incat daca

pm > N(ε), atunci f(pm)< ε. Particularizand pentru ε = 1, vedem ca exista

B > 0 astfel incat daca pm > B, atunci f(pm)≤ 1. Multimea numerelor de forma

pm care sunt mai mici sau egale cu B este finita, presupunem ca ea are C elemente.

Urmeaza de aici ca exista un A > 0 astfel incat f(pm)< A pentru orice p si m,

deoarece putem alege un A care sa fie mai mare decat toate valorile lui f in cele C

elemente mai mici decat B, si A > 1.

Fie 0 < ε < 1 (si implicit N(ε) ≥ B) si n = pa11 · pa22 · . . . · p

akk . Vom reveni mai jos

asupra alegerea convenabila a lui n. Acum vom evalua f(n):

f(n) = f (pa11 ) · (pa22 ) · . . . ·(pakk)< AC ·

∏paii >N(ε)

f (paii ) < AC · ε,

39

daca exista cel putin un i pentru care paii > N(ε). Intr-adevar, ne vom uita la toate

elementele paii si pozitia lor relativa la B si N(ε). Pentru cele mai mici decat B,

valoarea lui f in ele este mai mica decat A, si acestea sunt cel mult C la numar.

Pentru cele intre B si N(ε), valoarea lui f in ele este cel mult 1. Pentru cele mai

mari decat N(ε), valoarea lui f in ele este mai mica decat ε < 1.

Acum ramane sa revenim la n si sa facem precizarea ca exista o alta constanta M(ε)

cu proprietatea ca pentru orice n ≥ M(ε), n are proprietatea ca cel putin unul din

factorii sai paii este mai mare decat N(ε). Astfel, demonstratia se incheie.

Lema 2.7.11. Oricare ar fi ε > 0, de la un rang incolo are loc ϕ(n) > n1−ε.

Demonstratia lemei. Vom defini functia

f(n) =n1−ε

ϕ(n)

Evident functia f este multiplicativa. Daca p este un numar prim, atunci

f(pm)

=pm(1−ε)

pm−1(p− 1)=

1

pmε(1− p−1

) ≤ 1

(pm)ε(1− 2−1),

deoarece p ≥ 2, si se observa imediat ca limpm→∞

f(pm)

= 0. In concluzie, folosind lema

anterioara, rezulta ca limn→∞

f(n) = 0, deci exista un n0 natural astfel incat pentru

orice n ≥ n0 are loc inegalitatea f(n) < 1, si astfel demonstratia se incheie.

Avem acum uneltele necesare sa estimam suma din membrul stang din (1). Fie

ε > 0 arbitrar, fixat (si suficient de mic). Atunci conform lemei 2.7.11 avem ca

exista un n0 natural astfel incat pentru orice n ≥ n0, ϕ(n) > n1−ε.

Pentru i < j, vom folosi urmatoarea notatie:

Sϕ(i, j) =∑

i≤p≤j,p primϕ(p− 1).

Astfel, (1) spune ca Sϕ(1, n) < nM pentru orice n natural. Din nou, pentru i < j

vom folosi si notatia:

P (i, j) =∑

i≤p≤j,p prim(p− 1)1−ε.

Fie α = Sϕ(1, n0)/P (1, n0) si γ = min(1, α

). Fie acum un n ≥ n0 arbitrar. Avem

urmatorul sir de inegalitati:

Sϕ(1, n) = Sϕ(1, n0) + Sϕ(n0 + 1, n) ≥ αP (1, n0) + P (n0 + 1, n) ≥ γP (1, n).

40

Astfel, din relatia de mai sus si din (1) rezulta ca pentru orice n > n0 are loc:∑p≤n,p prim

(p− 1)1−ε = P (1, n) < γ−1Mn.

Fie acum p1 < p2 < . . . < pk < . . . sirul numerelor prime. Alegem m suficient de

mare astfel incat pm > n0, si punem n = pm. Cum pentru orice j avem ca pj−1 ≥ j,relatia de mai sus devine

m∑j=1

j1−ε <m∑j=1

(pj − 1)1−ε = P (1, pm) < γ−1Mpm.

Vom scrie acest fapt ca

1

m2−ε

m∑j=1

j1−ε

< γ−1M · pmm2−ε . (4)

Este cunoscut faptul ca exista c1, c2 ∈ (0,+∞) astfel incat pentru orice m natural

sa aiba loc:

c1 <pm

m lnm< c2.

Acest fapt este demonstrat in [4]. De fapt, este adevarat chiar ca limm→∞

pmm lnm

= 1,

acest fapt fiind o teorema celebra cunoscuta sub numele de teorema numarului prim

(mai multe detalii despre istoria acestui rezultat pot fi gasite in [5]). Nu avem nevoie

insa de acest rezultat (foarte puternic!). Este suficienta doar marginea superioara

(si anume c2).

Cum ε > 0 a fost ales suficient de mic (in particular, ε < 1), rezulta ca

limm→∞

pmm2−ε = lim

m→∞

pmm lnm

· lnm

m1−ε = 0.

Aplicand acest fapt in (4), rezulta ca

limm→∞

1

m2−ε

m∑j=1

j1−ε

= 0.

Acest ultim rezultat este o contradictie insa, deoarece conform lemei 2.7.9 avem ca

limm→∞

1

m2−ε

m∑j=1

j1−ε

=1

2− ε.

41

Asadar am obtinut o contradictie, deci presupunerea ca n(a) < M pentru orice

numar natural a nu poate fi adevarata. Astfel demonstratia se incheie.

42

3 Exemple si aplicatii

In aceasta ultim capitol vom da si niste aplicatii ale teoriei prezentate. Vom avea trei

parti. Prima parte studiaza congruentele binome xk ≡ a (mod n). Vom da conditii

necesare si suficiente pentru ca acestea sa aiba solutie, determinand totodata si

numarul solutiilor, acoperind toate cazurile referitoare la forma numarului n.

In cea de a doua parte vom prezenta niste probleme cu un grad mai ridicat de

dificultate care se rezolva folosind metode specifice radacinilor primitive.

Cea de-a treia parte poate fi privita ca o ”curiozitate matematica”, iar cu ajutorul

teoriei radacinilor primitive putem descrie complet evenimentul, si anume numerele

ciclice.

43

3.1 Congruente binome

In aceasta sectiune ne vom ocupa de rezolvarea congruentelor binome de forma

xk ≡ a (mod n) unde a si n sunt relativ prime. Reamintim intai corolarul 1.2.8 din

primul capitol:

Propozitia 3.1.1. Fie n ≥ 2 un numar natural si a un numar intreg, astfel incat

(a, n) = d. Atunci congruenta ax ≡ b (mod n) are solutii daca si numai daca d|b,iar numarul solutiilor in acest caz este exact d.

Revenind la congruenta xk ≡ a (mod n), vom analiza intai cazul cand n admite

radacini primitive. Are loc urmatorul rezultat:

Teorema 3.1.2. Fie n ≥ 2 un numar natural ce admite radacini primitive. Atunci

congruenta xk ≡ a (mod n) admite solutii daca si numai daca

aϕ(n)/d ≡ 1 (mod n),

unde d =(k, ϕ(n)

). In acest caz, congruenta are exact d solutii.

Demonstratie. Fie r o radacina primitiva modulo n. Atunci exista s astfel incat

a ≡ rs (mod n). De asemenea, punem x = rz si vom lucra cu z in loc de x.

Conform teoremei 2.1.3 avem ca

rzk ≡ rs (mod n)

daca si numai daca zk ≡ s (mod ϕ(n)). Conform propozitiei enuntate la inceputul

acestei sectiuni, aceasta ultima congruenta are solutie daca si numai daca d divide

s. Vom arata ca acest lucru este echivalent cu

aϕ(n)/d ≡ 1 (mod n).

Vom nota e =(ϕ(n), s

). Conform teoremei 2.1.4, ordn(a) = ordn(rs) = ϕ(n)/e.

Conform teoremei 2.1.1, avem ca

aϕ(n)/d ≡ 1 (mod n)

daca si numai daca ordn(a) = ϕ(n)/e divide ϕ(n)/d, care mai departe este echivalent

cu d divide e. Cum d divide ϕ(n), faptul ca d divide e este echivalent cu faptul ca

d divide s. Astfel, am demonstrat echivalenta intre d|s si aϕ(n)/d ≡ 1 (mod n).

Tot conform propozitiei enuntate la inceputul sectiunii, avem ca daca congruenta

44

zk ≡ s (mod ϕ(n))

are solutii, atunci ea are exact d solutii. Astfel, demonstratia se incheie.

Mai departe, vom analiza cazul in care n = 2e pentru e ≥ 3.

Teorema 3.1.3. Fie e ≥ 3 un numar natural si a un numar intreg impar. Daca k

este impar, atunci congruenta xk ≡ a (mod 2e) are solutie unica. Daca n este par,

atunci congruenta xk ≡ a (mod 2e) are solutie daca si numai daca a ≡ 1 (mod 4)

si

a2e−2/d ≡ 1 (mod 2e),

unde d = (2e−2, n). In acest caz, numarul solutiilor este 2d.

Demonstratie. Reamintim teorema 2.5.6:numerele

5, 52, . . . , 52e−2,−5,−52, . . . ,−52

e−2

formeaza un sistem redus de resturi modulo 2e. Asadar, exista s, t astfel incat

a ≡ (−1)s5t (mod 2e).

Cautam solutii de forma x = (−1)y5z. Astfel, congruenta xk ≡ a (mod 2e) devine

(−1)ky5kz ≡ (−1)s5t (mod 2e).

Procedand analog ca in demonstratia teoremei 2.5.6, sau direct, folosindu-ne de

structura grupului U(Z2e), vom avea ca ultima congruenta are loc daca si numai

daca

(−1)ky ≡ (−1)s (mod 2e) si 5kz ≡ 5t (mod 2e).

Putem vedea imediat ca ord2e(−1) = 2 si am demonstrat in capitolul 2 (teorema

2.4.5) ca ord2e(5) = 2e−2. In concluzie, conform teoremei 2.1.3,

(−1)ky ≡ (−1)s

este echivalent cu ky ≡ s (mod 2), iar

5kz ≡ 5t (mod 2e)

45

este echivalent cu kz ≡ t (mod 2e−2). Asadar, x = (−1)y5z este solutie a congru-

entei xk ≡ a (mod 2e) daca si numai daca

ky ≡ s (mod 2) si kz ≡ t (mod 2e−2).

Daca k este impar, atunci (k, 2) = (k, 2e−2) = 1. Deci

ky ≡ s (mod 2) si kz ≡ t (mod 2e−2)

au ambele solutie unica, asadar exista o solutie unica x pentru congruenta din enunt.

Daca k este par, atunci (k, 2) = 2, si avem (k, 2e−2) = d. Congruenta

ky ≡ s (mod 2)

are solutii daca si numai daca s este par, ceea ce este echivalent cu

a ≡ 5t (mod 2e).

Mai departe, vedem ca a ≡ 5t (mod 2e) daca si numai daca a ≡ 1 (mod 4): intr-

adevar, implicatia directa este imediata iar daca a ≡ 1 (mod 4), folosind din nou

scrierea

a ≡ (−1)s5t (mod 2e)

vedem ca trebuie ca (−1)s ≡ 1 (mod 4), adica s sa fie par, deci

a ≡ 5t (mod 2e).

In concluzie, congruenta ky ≡ s (mod 2) are solutie daca si numai daca a ≡ 1

(mod 4). In acest caz, ea are chiar doua solutii.

Ne uitam acum la congruenta kz ≡ t (mod 2e−2). Tot conform propozitiei enuntate

la inceputul acestei sectiuni, ea are solutie daca si numai daca d divide t, si in acest

caz, ea are chiar d solutii. Ne intereseaza doar cazul cand a ≡ 1 (mod 4), adica

atunci cand a ≡ 5t (mod 2e). Vom arata ca d divide t daca si numai daca

a2e−2/d ≡ 1 (mod 2e),

iar rationamentul este analog cu cel din demonstratia teoremei anterioare. Fie e =

(2e−2, t). Atunci conform teoremei 2.1.4 avem ca ord2e(a) = 2e−2/e. Atunci

a2e−2/d ≡ 1 (mod 2e)

46

este echivalent cu 2e−2/e divide 2e−2/d, care mai departe este echivalent cu d divide

e. Cum d divide 2e−2, afirmatia din urma este echivalenta cu d divide t. Asadar

congruenta kz ≡ t (mod 2e−2) are solutie daca si numai daca a2e−2/d ≡ 1 (mod 2e).

In particular, exista d solutii in acest caz.

Punand cap la cap cele doua rezultate, vedem ca 2 solutii pentru y si d solutii pentru

z vor da 2d solutii pentru x = (−1)s5t, iar astfel de solutii exista daca si numai daca

a ≡ 1 (mod 4) si

a2e−2/d ≡ 1 (mod 2e),

si deci demonstratia se incheie.

Acum putem da un rezultat general folosind teorema chineza a resturilor (teorema

1.2.3). Fie n = 2e · pa11 · . . . · pamm . Atunci congruenta xk ≡ a (mod n) are solutie

daca si numai daca congruentele

xk ≡ a (mod 2e), xk ≡ a (mod pa11 ), . . . , xk ≡ a (mod pamm )

au toate solutii. Insa pentru oricare din congruentele de mai sus putem folosi una din

cele doua teoreme demonstrate anterior, si astfel problema este complet rezolvata.

47

3.2 Probleme in care apar radacinile primitive

Mai jos vom prezenta anumite probleme care se leaga de radacini primitive. Primele

doua chiar dau niste exemple concrete de radacini primitive modulo niste numere

prime cu forma speciala. Celelalte patru au la baza probleme date la diferite

olimpiade, in a caror solutie intervine direct notiunea de radacina primitiva.

Propozitia 3.2.1. Fie p un numar prim astfel incat p ≡ 3 (mod 8) si p−12 = q este

prim. Atunci 2 este radacina primitiva modulo p.

Demonstratie. Avem ca ϕ(p) = p − 1 = 2q. Cum ordp(2) este un divizor al lui

2q, acesta poate fi 2, q sau 2q. Cum p > 3, rezulta imediat ca ordp(2) nu poate

fi 2 deoarece 22 6≡ 1 (mod p). Vom arata ca nu poate fi nici q. Conform legii de

reciprocitate patratica (teorema 1.3.7) obtinem ca 2 nu este rest patratic modulo p,

si deci(2p

)= −1. Conform criteriului lui Euler (teorema 1.3.3) avem ca

2q ≡(

2

p

)(mod p),

asadar 2q ≡ −1 (mod p), deci ordp(2) 6= q. Ramane deci ca ordp(2) = 2q si demon-

stratia se incheie.

Ca exemplu, putem lua p = 83 si q = 41. Conform propozitiei de mai sus, 2 este

radacina primitiva modulo 83.

Propozitia 3.2.2. Fie p = 22n

+ 1 un numar prim Fermat prim (unde n ≥ 1).

Atunci 3 este radacina primitiva modulo p.

Demonstratie. Ideea este asemanatoare cu cea de la propozitia anterioara. Avem ca

ϕ(p) = p− 1 = 22n, deci ordinul lui 3 este o putere a lui 2. Vom arata ca 32

n−1 6≡ 1

(mod p), si de aici va rezulta ca ordp(3) = 22n, adica chiar concluzia.

Cum p ≡ 1 (mod p), obtinem conform legii de reciprocitate patratica (teorema

1.3.7) ca (3

p

)·(p

3

)= 1.

Pe de alta parte, p ≡ 42n−1

+ 1 ≡ 2 (mod 3), deci(p3

), deoarece 2 nu este rest

patratic modulo 3. In concluzie, trebuie ca(3p

)= −1, asadar 32

n−1 ≡ −1 (mod p),

si demonstratia se incheie.

48

Propozitia 3.2.3 (Olimpiada China, adaptare). Fie p si m numere naturale astfel

incat p este prim si (m, p− 1) = 1. Atunci exista un n natural astfel incat numarul

nm −m este divizibil cu p.

Demonstratie. Daca m este multiplu de p atunci luam n = p. Altfel, putem pre-

supune ca (m, p) = 1, si putem aplica direct teorema 3.1.2. Atat pe post de a cat

si pe post de k il avem pe m. Avem ca d = (m, p − 1) = 1 iar ap−1 ≡ 1 (mod p)

conform teoremei lui Fermat (corolarul 1.2.5), deci ecuatia xm ≡ m (mod p) are

solutii. Alegem n ca fiind o astfel de solutie.

Propozitia 3.2.4 (Olimpiada Argentina, adaptare). Fie p un numar prim astfel

incat p− 1 este divizibil cu 3, si fie numerele intregi a1, a2, . . . , as astfel incat ai ≥ 2

si

r∑j=1

as = p− 1.

Atunci exista o partitie A1, A2, . . . , As a multimii{

1, 2, . . . , p− 1}

astfel incat Ai sa

aiba ai elemente si suma elementelor sale este divizibila cu p.

Demonstratie. Pentru inceput, vom arata ca putem partitiona multimea numerelor

de la 1 la p − 1 in submultimi avand fiecare cate 3 elemente si suma acestora sa

fie divizibila cu p, cu proprietatea ca daca{a1, a2, a3

}apare in partitie, atunci si{

p− a1, p− a2, p− a3}

apare in partitie.

Fie r o radacina primitiva modulo p. Notam q = p−13 . Vom considera partitia data

de multimile Bk ={xk, yk, zk

}, unde xk, yk, zk sunt date de:

xk ≡ rk (mod p)

yk ≡ rk+q (mod p)

zk ≡ rk+2q (mod p)

Avem ca

rk + rk+q + rk+2q = rk(1 + rq + r2q

)= rk · r

p−1 − 1

rq − 1,

iar membrul drept este divizibil cu p deoarece rp−1 ≡ 1 (mod p) dar rq 6≡ 1 (mod p).

Observam ca Bk+(p−1)/2 ={p− xk, p− yk, p− zk

}. Intr-adevar, vom arata ca

rk ≡ −rk+p−12 (mod p).

49

Acest fapt este echivalent cu r(p−1)/2 ≡ −1 (mod p), iar acest fapt este adevarat,

deoarece stim ca r(p−1)/2 ≡ ±1 (mod p) iar ordp(r) = p− 1 deci semnul nu poate fi

+.

Vom construi multimile Ai pe baza unui algoritm. Ne uitam intai la numerele

a1, a2, . . . , ak. Cum suma lor este para, numarul de numere ai impare trebuie sa fie

par. Vom imparti aceste ai-uri in perechi arbitrare. Pentru fiecare pereche Ai, Aj

vom alege un k oarecare si vom pune elementele din Bk in Ai, si elementele din

Bk+(p−1)/2 in Aj , evident, alegand cate un k diferit la fiecare pas.

Astfel, pana acum am construit multimile disjuncte A1, A2, . . . , As astfel incat Ai

este vida daca ai este par si |Ai| = 3 daca ai este impar. Ramane acum sa completam

fiecare din multimile Ai cu perechi{a, p − a

}(evident alegand cate un a diferit

la fiecare pas), pana cand |Ai| = ai. Adaugand cate 2 elemente de fiecare data,

paritatea lui |Ai| nu se schimba, si deci vom putea realiza acest lucru. La final,

multimile A1, A2, . . . , As vor fi disjuncte oricare doua si

s∑j=1

|Aj | = p− 1,

deci ele dau partitia dorita.

Propozitia 3.2.5 (Olimpiada Vietnam, adaptare). Fie p ≥ 5 un numar prim.

Pentru n ≥ 1 natural consideram multimea:

Tn ={p(i+ j) + (p− 1)

(ni + nj

)| 1 ≤ i, j ≤ p− 1

}.

Atunci Tn nu contine numere congruente modulo p(p−1) daca si numai daca n este

radacina primitiva modulo p.

Demonstratie. ” =⇒ ”: Fie n astfel incat Tn nu contine numere congruente modulo

p(p−1). Vom arata ca n este radacina primitiva modulo p. Presupunem prin absurd

ca nu este asa. Se verifica imediat ca n nu poate fi divizibil cu p, un contraexemplu

fiind construit luand i = j = p − 1 si i′ = 1, j′ = p − 2. Ramane deci cazul cand

ordp(n) = d cu d < p− 1. Cum d divide p− 1, vom avea ca d ≤ p−12 ≤ p− 3. Atunci

vom alege numerele

a = p((d+ 1) + 2

)+ (p− 1)

(nd+1 + n2

)corespunzator lui i = d+ 1 ≤ p− 1 si j = 2, si

50

b = p((d+ 2) + 1

)+ (p− 1)

(nd+2 + n1

),

corespunzator lui i = d+ 2 ≤ p− 1 si j = 1. Avem ca

a− b = (p− 1)((nd+1 − n1

)−(nd+2 − n2

))= (p− 1)n(1− n)

(nd − 1

),

si cum d = ordp(n) avem ca nd ≡ 1 (mod p), si deci p(p − 1) divide a − b, adica

a ≡ b (mod p(p − 1)). Pe de alta parte, se observa imediat ca a − b 6= 0. Dar din

constructia lor, avem a, b ∈ Tn, contradictie. Astfel, trebuie ca ordp(n) = p−1, deci

n trebuie sa fie radacina primitiva modulo p.

” ⇐= ”: Fie n radacina primitiva modulo p, si fie 1 ≤ i, j, i′, j′ ≤ p − 1 astfel incat

p(p− 1) divide numarul:

p(i+ j − i′ − j′) + (p− 1)(ni + nj − ni′ − nj′

).

Este suficient sa aratam ca{i, j}

={i′, j′

}.

Din faptul ca p−1 divide numarul de mai sus rezulta ca ni+nj ≡ ni′+nj′

(mod p)

si apoi urmeaza ca i+ j ≡ i′ + j′ (mod p− 1). Din teorema 2.1.3 rezulta ca

ni+j−j′ ≡ ni′ (mod p).

Folosind acest fapt rezulta printr-un calcul imediat ca

nj′(

1− ni−j′)(nj−j

′ − 1)≡ ni + nj − ni′ − nj′ ≡ 0 (mod p).

deci trebuie ca ni−j′ ≡ 1 (mod p) sau nj−j

′ ≡ 1 (mod p). Cum

0 ≤ |i− j′|, |j − j′| ≤ p− 2,

iar ordp(n) = p − 1, trebuie ca i = j′ sau j = j′. Presupunem fara a restrange

generalitatea ca j = j′. Mai departe trebuie ca i ≡ i′ (mod p− 1), si cum

1 ≤ i, i′ ≤ p− 1,

rezulta ca i = i′, si demonstratia se incheie.

Propozitia 3.2.6 (Olimpiada Romania, adaptare). Fie Dn cel mai mare divizor

comun al numerelor 1n − 1, 2n − 2, . . . , nn − n. Atunci

Dn =∏

p−1|n−1p prim

p

51

Demonstratie. Vom arata intai ca Dn nu are factori primi p > n. Presupunem

prin absurd ca p este un astfel de factor. Consideram f(X) = Xn−1 − 1 de grad

n−1. Conform teoremei lui Lagrange (1.2.9), avem ca congruenta f(x) ≡ 0 (mod p)

admite cel mult n−1 solutii necongruente modulo p. Dar toate numerele de la 1 la n

satisfac aceasta congruenta, deoarece p > n, iar ele sunt oricare doua necongruente.

Cum numarul lor este n, am obtinut o contradictie. Asadar Dn nu poate avea factori

primi p > n.

Vom arata acum ca un numar prim p ≤ n divide Dn daca si numai daca p−1 divide

n − 1. Fie p un numar prim astfel incat p − 1 divide n − 1. Vom demonstra ca

an ≡ a (mod p) pentru orice 1 ≤ a ≤ n. Daca (a, p) = 1 atunci conform teoremei

lui Fermat (corolarul 1.2.5) rezulta ca ap−1 ≡ 1 (mod p), si cum p− 1 divide n− 1,

rezulta si ca an−1 ≡ 1 (mod p). Daca a este multiplu de p este evident. In concluzie,

un astfel de p divide toate numerele an − a, si de aici p divide Dn.

Fie acum p un divizor al luiDn. Alegem a o radacina primitiva modulo p (astfel incat

1 ≤ a ≤ n). Cum p divide an−a, trebuie ca an−1 ≡ 1 (mod p). Dar ordp(a) = p−1,

deci conform teoremei 2.1.1 rezulta ca p− 1 divide n− 1.

In final, daca p divide Dn, cum Dn divide p(pn−1−1), rezulta ca p2 nu poate divide

Dn. Din toate cele mentionate mai sus, rezulta concluzia.

52

3.3 Numere ciclice

Vom finaliza aceasta lucrare cu o sectiune care tine oarecum de ”matematica distrac-

tiva”. Totusi, la final vom utiliza chiar notiunea de radacina primitiva, prezentand

astfel o aplicatie interesanta care nu este ”pur teoretica”. Incepem prin a ne uita la

numarul 142 857. Acesta este un numar celebru, deoarece sunt satisfacute relatiile

142 857 × 1 = 142 857

142 857 × 2 = 285 714

142 857 × 3 = 428 571

142 857 × 4 = 571 428

142 857 × 5 = 714 285

142 857 × 6 = 857 142

Este natural acum sa ne intrebam daca mai exista astfel de numere si de unde

provine aceasta proprietate.

Sa numim un numar cu L cifre ciclic daca are proprietatea ca prin inmultirea sa cu

numerele 1, 2, . . . , L − 1 se obtin permutari circulare ale cifrelor sale. Precizam ca

este permis ca un numar sa aiba primele cifre 0, daca este indeplinita conditia din

enunt. Mai jos vom caracteriza aceste numere ciclice.

Observam ca numarul 142 857 reprezinta de fapt perioada zecimala a lui 1/7. Legatura

cu radacinile primitive este data de urmatorul rezultat:

Propozitia 3.3.1. Perioada zecimala a lui 1/p este un numar ciclic daca si numai

daca 10 este radacina primitiva modulo p.

Demonstratie. Fie p un numar prim. Putem elimina din start cazul p = 3 deoarece

acesta nu satisface niciuna din conditii. Asadar p > 3. Vom scrie 1/p = 0, (a1a2 . . . aL).

Observam imediat ca pentru orice 1 ≤ j ≤ p−1 numarul j/p este periodic si perioada

sa este chiar j · a1a2 . . . aL. Vom arata ca L = ordp(10). Avem ca partea zecimala a

lui 10k/p coincide cu partea zecimala a lui 1/p daca si numai daca numarul 10k−1p

este intreg, echivalent cu 10k ≡ 1 (mod p). Cum cel mai mic numar k pentru care

partea zecimala a lui 10k/p coincide cu partea zecimala a lui 1/p este L, iar cel mai

mic numar k pentru care 10k ≡ 1 (mod p) este ordp(10), rezulta afirmatia facuta.

” =⇒ ”: Fie 1/p un numar ciclic. Folosim notatia de mai sus. Atunci stim ca

numerele 1/p, 2/p, . . . , L/p vor avea drept perioada permutarile circulare ale lui

a1a2 . . . aL. Observam insa ca pentru orice k, perioada lui 10k este, de asemenea,

53

o permutare circulara a lui a1a2 . . . aL, fiind chiar ak+1ak+2 . . . aLa1 . . . ak−1. Dar

perioada lui i/p coincide cu perioada lui j/p daca si numai daca i ≡ j (mod p), deci

modulo p trebuie sa aiba loc egalitatea de multimi{1, 2, . . . , L

}={

1, 10, 102, . . . , 10L−1}

.

Vom arata ca L = p− 1. Stim ca L = ordp(10). Atunc

(10− 1)L−1∑j=0

10j ≡ 10L − 1 ≡ 0 (mod p)

si cum p > 3 trebuie ca p sa divida suma 1 + 10 + 102 + . . .+ 10L−1. Din egalitatea

de multimi, vom avea ca:

L∑j=1

j ≡L−1∑j=0

10j ≡ 0 (mod p),

deci p divide L(L+1)2 . Cum L < p, trebuie ca L = p− 1. Deci ordp(10) = p− 1 si de

aici 10 este radacina primitiva modulo p.

”⇐= ”: Fie p prim astfel incat 10 este radacina primitiva modulo p. Atunci{1, 2, . . . , p− 1

}={

1, 10, 102, . . . , 10p−2}

,

si facand acelasi rationament ca mai sus obtinem ca numerele 1/p, 2/p, . . . , (p−1)/p

vor avea drept perioade permutari circulare ale perioadei lui 1/p. Asadar perioada

lui 1/p este numar ciclic.

Vom preciza ca, de fapt, rezultatul de mai sus caracterizeaza complet numerele

ciclice. Se poate demonstra ca orice numar ciclic este perioada unui astfel de 1/p.

Cel mai mic numar ciclic este 142 857, corespunzator lui p = 7. Urmatorul p este

17, de aici obtinem numarul ciclic 0 588 235 294 117 647. Observam ca acesta incepe

cu 0 (pentru a satisface conditia de ciclicitate). Singurul numar ciclic care nu are

prima cifra 0 este chiar 142 857. Intr-adevar, celelalte numere ciclice sunt perioade

ale unor numere 1/p, unde p e prim si 10 este radacina primitiva modulo p. Se

poate verifica imediat ca singurul p < 10 care satisface aceasta conditie este p = 7,

deci orice numar ciclic diferit de 142 857 este perioada unui numar mai mic decat

1/10 = 0, 1. Asadar prima zecimala dupa virgula a sa trebuie sa fie 0.

54

Bibliografie

[1] Tiberiu Dumitrescu. Algebra. Editura Universitatii, Bucuresti, 2006.

[2] William J. LeVeque. Elementary Theory of Numbers. Dover Publications, New

York, 1990.

[3] William J. LeVeque. Fundamentals of Number Theory. Dover Publications, New

York, 1996.

[4] Alexandru Victor, Niculaie Gosoniu. Elemente de Teoria Numerelor. Editura

Universitatii, Bucuresti, 1999.

[5] Paulo Ribenboim. The New Book of Prime Number Records. Springer, 1996.

[6] W. Stein. Elementary Number Theory. http://modular.fas.harvard.edu/ent/ent.pdf,

2004.

55