Teoria numerelor [PDF]

Zitiervorschau

MINISTERUL EDUCAŢIEI Şl ÎNVĂŢĂMÎNTULUI

Prof. dr. CONSTANTIN P. POPOVICI

TEORIA NUMERELOR EDITURA DIDACTICĂ SI PEDAGOGICĂ, BUCUREŞTI 1973

Referent : A c a d . Tiberiu Popoviciu

Prefaţă

Redactor : Avram Pop Tehnoredactor : A n a Timpâu Coperta : Victor W e g e m a n

In acest volum au fost cuprinse lecţiile de teoria numerelor pe care le-am ţinut studenţilor, începînd din 1961, în cadrul unui curs spe­ cial, al cărui conţinui a suferit modificări, ajungind la forma sub care este prezentat pentru publicare. Scopul acestor lecţii era de a da demonstraţiile, cu mijloacele teoriei analitice elementare a nu­ merelor, a legii asimptotice a distribuţiei numerelor prime şi a teo­ remei lui Dirichlet referitoare la infinitatea numerelor prime. Din această cauză, aceste lecţii au cuprins toate cele necesare din teoria elementară a numerelor şi din teoria analitică elementară a nume­ relor. Din teoria elementară a numerelor au fost tratate relaţia de con­ gruenţă

în inelul

numerelor

întregi

si

inelul

numerelor

m-în-

tregi, rezolvarea congruenţelor şi a sistemelor de congruenţe cu o necunoscută, clase de resturi, teoremele lui Euler, Fermat şi Wilson, rădăcini primitive,

indici modulo m, funcţii

numerice, formule de

inversare a sumelor, numărul numerelor prime, caractere modulo m, resturi patratice, infinitatea

numerelor prime. Constituite înVprimele

12 capitole, aceste lecţii de teorie elementară a numerelor pot privite ca formînd

o parte independentă 3

de restul volumului

fi,

con-

tinind un ansamblu de cunoştinţe pe care trebuie să le aibă orice matematician. Capitolul 12, referitor la infinitatea numerelor prime, cuprinde şi cercetări originale ale autorului. Din teoria analitică elementară a numerelor au fost expuse com­ portarea asimptotică şi evaluări asimptotice ale cltorva funcţii nu­ merice. Aceste cunoştinţe au servit la demonstrarea legii asimptotice a distribuţiei numerelor prime şi a teoremei lui Dirichlet referitoare la infinitatea numerelor prime. Metodele teoriei analitice elemen­ tare a numerelor sint relativ simple şi deosebit de eficace, moliv pentru care am ţinut să le fac cunoscute studenţilor noştri, măcar in legătură cu cele două teoreme tratate în ultimele două capitole 15 şi 16. Acest volum, cel puţin în ceea ce priveşte teoria elementară a nu­ merelor, poale servi drept o carte de referinţă şi pentru profesorii de liceu care se pregătesc în vederea obţinerii gradelor în învăţămînt sau care conduc cercuri de matematică pentru elevi.

Simboluri şi notaţii Simbol sau notaţie

Semnificaţia lui divide nu divide

V =>

sau implică este echivalent cu (echivalenţă logică) este echivalent cu (relaţie de echivalenţă) nu este echivalent cu este asociat cu nu este asociat cu este egal cu nu este egal cu este congruent cu nu este congruent cu este mai mic decit este cel mult egal cu este mai mare decit este cel puţin egal cu plus minus sumă produs

Si

Autorul

< >

+ £

n

e ^ cp ni sign Ca •ă indf a ind a mod m ,| a | {a] {a} {a, b)

aparţine nu a p a r ţ i n e indicatorul Iui Euler /i-factorial signum clasă de echivalenţă clasă de resturi indice al lui a modulo m în r a p o r t cu baza g indice al lui a modulo m în r a p o r t cu baza g nrodulo m valoarea absolută a lui a p a r t e a întreagă a lui a p a r t e a fracţionară a lui a cel mai mare divizor c o m u n al lui a şi b

{a, b] S

9

7T

X

(j)

ii

K(j)

u(l) + u ( 2 ) + . . . + u ( s ) f(d1)+... +f(dt), u n d e {dv. . ., dt} divizorilor pozitivi ai lui n

s M)

este

mulţimea

fw+m)+...+f([x])

E fW

m)+f(2)

l/t^X

+

...+f([x])

00

«>*

n=[*]+l

.a=0, (5, d) o | ± l = > o = ± l (« = ± 1 trebuie înţeles în sensul că a = l sau a=—l). (6) a\b&b\a=Şb = jza (b = ^za trebuie înţeles în sensul că b=a sau b= — a). (7, a) a\b1&a\b2=)a\b1+b2 (a\b1±bî trebuie înţeles în sensul că a\b1-\~bs sau a\b1— b2), (7, b) a\b=)a\cb oricare ar fi numărul întreg c, (7, c) a\b1&a\ 6 2 =>a|c 1 6 a +c 2 i 2 oricare ar fi numerele întregi cx şi c». (8) a\b&b^0^)\a\^\b\. Relaţia de divizibilitate în inelul numerelor întregi permite definirea relaţiei de asociere în inelul numerelor întregi. 1.1.3. Definiţia relaţiei de asociere în inelul numerelor întregi (a) Numerele întregi a şi b sînt asociate dacă a\b&b\a. Pentru a arăta că numerele întregi a şî b sînt asociate, vom scrie a^b. Putem defini relaţia de asociere în inelul numerelor întregi în felul următor : (b) Numerele întregi a şi b sînt asociate dacă b — -±a. (c) Numerele întregi a şi b sînt asociate dacă |a| = |ft|. (d) Numerele întregi a şi b sînt asociate dacă \a\ sg \b\_& \b\ ^ \a\. Aceste patru definiţii sînt echivalente. Relaţia de asociere în inelul numerelor întregi are următoarele proprietăţi: . , ., , (1) reflexivitate: a~a, i; (2) simetrie: a = 6=>fi = a, :, (3) tranzitivitate: a^b&b^c=)a^c. , iu , 11

Avînd aceste trei proprietăţi relaţia de asociere în inelul nume­ relor întregi este relaţie de echivalenţă în inelul numerelor întregi. Observaţie. Din definiţia (b) a relaţiei de asociere în inelul numerelor întregi se constată că numărul întreg a este asociat numai cu a şi —a. Deci numerele întregi asociate cu un număr întreg a se obţin din a prin înmulţire cu unităţile inelului nume­ relor întregi, deoarece a=l-a şi — a = ( — 1)-a, prin unităţile inelului numerelor întregi înţelegîndu-se acele numere întregi care divid pe 1 şi care sînt numai 1 şi —1 datorită proprietăţii (5, d, a relaţiei de divizibilitate în inelul numerelor întregi. După această parte introductivă putem da definiţia relaţiei de congruenţă în inelul numerelor întregi.

1.2. Prima definiţie a relaţiei de congruentă în inelul numerelor întregi Două numere întregi a şi b sînt congruente modulo m, unde m este un număr întreg, dacă: m\a—b. Pentru a arăta că numerele întregi a şi b sînt congruente mo­ dulo m, se scrie a = 6(mod m). Numărul întreg m se numeşte modulul relaţiei de congruenţă. Relaţia de congruenţă, în inelul numerelor întregi, are urmă­ toarele proprietăţi : (1) reflexivitate: a~a (mod m), oricare ar fi numărul întrega. (2) simetrie: a = b (mod m)=)b = a (mod m). (3) tranzitivitate: a = b (mod m)&b=c (mod m)=)a~c (mod m). (4, a) a = b (mod m)&c = d (mod m)=>a+c = 6-4-d (mod m), (4, b) a = b (mod m)&c = d (mod m)=$a—c = b — d (mod m), (4, c) a = b-\-c (mod m)=>a— c = b (mod m). (5, a) a = 6 (mod m)&c = d (mod m)=)ac = bd (mod m), (5, b) a = b (mod m)=$ac = bc (mod mc), oricare ar fi numărul întreg c, (5, c) ac = bc (mod mc)&c=£0=>a = fc (mod m), (5, d) a = b (mod m)=)ac=bc (mod m), oricare ar fi numărul întreg c, (5, e) ac = bc (mod m)&(c, m ) ^ l = > a = 6 (mod m). Prin (c, m) a fost notat cel mai mare divizor comun al nume­ relor întregi c şi m. (6, a) « = 6 (mod 0)a = 6, ( trebuie citit, „este echivalent cu") 12

(6, b) a = b (mod ^ 1 ) oricare ar fi numerele întregi a şi b (a = fi (mod ± 1 ) trebuie înţeles în sensul că a~b (mod 1) sau a = b (mod —1)). (7) a = b (mod m)&/î|m=>a = 6 (mod n). (8, a) a = b (mod m)&(a, m)~d=)(b, m ) ~ d, (8, b) a = b (mod m)&,m\a=)m\b, (8, c) a = b (mod m)&(a, m)ş±l=)(b, m ) s l . Aceste, proprietăţi ale relaţiei de congruenţă în inelul nume­ relor întregi se demonstrează în felul următor : (1) m|0 oricare, ar fi numărul întreg m. Apoi a— a = 0 , oricare ar li numărul întreg a, deci m|a—a, de unde a = a (mod m). (2) a = b (mod m) înseamnă m|a—b. Deci m|(— l)(a—b), de unde m|b— a sau 6 = « (mod m). (3) « = /) (mod m) înseamnă m\a—-b, iar &=c (mod m) înseamnă m\b — c. Deci m\{a—b)-\-{b—c), de unde. ;n|a— c sau a=c (mod m). (4, a) a = b (mod m) înseamnă m\a—b, iar c — d (mod m) în­ seamnă m|c—a". Deci J?I|(«— 6)+(c— d) de unde ;n|(a +c)— (b-\~d) sau «-f-c = ft-fa' (mod m). (4, b) a = b (mod m) înseamnă m\a—b, iar c = rf (mod m) în­ seamnă m|c—d. Deci m|(a—/;) — (c—a"), de unde m|(a—c)—(b—d) sau a—c~b—d (mod m). (4, c) a = b-\-c (mod /n) înseamnă m\a— (fi-f-c). Deci m|(a— — c)— /> sau a—c = b (mod 7?Î). (5, a) a = 6 (mod m) înseamnă m\a—b, iar c=rf (mod m) în­ seamnă rn|c—d. Deci m|c(a—b)-\-b(c—d) de unde m\ac—bd sau ac = bd (mod m). (5, b) a~b (mod m) înseamnă m\a—b. Deci mc|(a—b)c oricare ar fi numărul întreg c. Rezultă mc[ac— bc sau ac = bc (mod mc) oricare ar fi numărul întreg c. (5, c) ac=bc (mod m) înseamnă mc|ac—fie. Deci mc[(a—b)c. Dacă c^O rezultă m\a— b sau « = fi (mod m). (5, d) « = 6 (mod m) înseamnă m\a—b. Deci m\c(a—b) oricare ar fi numărul întreg c. Rezultă m\ac—bc sau ac = bc (mod m) oricare ar fi numărul întreg c. (5, e) ac = bc (mod m) înseamnă m\ac—bc. Deci m|(a—b)c. Dacă (c, m ) ^ l rezultă m\a—b sau a = 6 (mod m). (6, a) a = b (mod 0) înseamnă 0\a— b. Dar 0|a—6a = 6. în adevăr, dacă 0\a—b rezultă a— 6 = 0 sau a = b. Dacă a = 6 rezultă a — 6 = 0 şi din cauză că 0|0 se obţine 0\a—b sau a = b (mod m)_ 13

(6, b) Oricare ar fi numerele întregi a, b, diferenţa a— b este un număr întreg, deci l\a—b sau a = b (mod 1) ori — l|a— b sau a = b (mod—1). (7) a = b (mod m) înseamnă m\a—b. Apoi n\m&m\a-pS=Şn\a— b, deci a = b (mod n). (8, a) a = 6 (mod m) înseamnă m\a— b. Deci există un număr întreg k astfel încît a—b=mk. Vom nota rfg(ff, m), D ^ ( 6 , m) şi vom demonstra că D s d , adică d^(b, m). Avem d|er, d|m, deci d\l -a + (—k)m, de unde d|6, deoarece b=a—mk. Din d|6, d|/n rezultă d\D, deoarece d s ( 6 , m). Avem şi D|6, şi D|m, deci D\l-b+k-m, de unde B|a, deoarece a = b+mk. Din D|a, D|m rezultă D\d, deoarece D s ( a , m). Din d|D, Z>|d rezultă D ^ d . (8, b) m|a=>me(«, m). Deci a = b (modm)&m\a=)m^(b, m), conform proprietăţii (8, a) a relaţiei de congruenţă în inelul numerelor întregi, de unde m\b. (8, c) Această proprietate este un caz particular al proprie­ tăţii (8, a) a relaţiei de congruenţă în inelul numerelor întregi în cazul cînd d—i.

1.3. A doua definiţie a relaţiei de congruenţă în inelul numerelor întregi Două numere întregi a şi b sînt congruente modulo m, unde meste un număr întreg diferit de zero, dacă există numere întregi qx, 0. Aşadar 124

formează mulţimea M şi fiecare din ele apare o singură dată în suma; considerată, conform cu modul în care este definită această sumă. Perechile (m, c) după care se face suma 2 ( 2 h(m, c)\ formează

şi reciproc. Demonstraţie.

Dacă g(x)=

2

P(n)fl-) 125

•atunci V

M } p
i r H «?«, "?' cel mai mic multiplu comun al mai multor numere fiind produsul factorilor primi comuni şi necomuni la puterea cea mai marc, fie­ care factor prim fiind luat o singură dată. în ceea ce priveşte funcţia vF(.x) avem T(.T)=

2

A(n)=

2

log

p,

OCj

a

r

=log (p«i . . .

r

2 a,- log p,-= ,

(2) v F(:r)==\ ° g x log p, suma fiind extinsă la toate numerele -fcJU'pg P\ prime pozitive, diferite două cile două, cel mult egale cu un număr real x. Într-adevăr, din demonstraţia proprietăţii precedente rezultă Jos

log V

130

diferite

Definiţie. Numărul numerelor naturale cel mult egale cu un număr real x şi care nu se divid cu nici unul din primele r numere prime pozitive este o funcţie numerică care se notează cu