276062004

1.6. Funkcja Eulera, jej własności i zastosowania 13

Własność 1.6.2 (podstawowe własności funkcji Eulera). (1) </?(l) = 1, (zero jest względnie pierwsze z jedynką).

(2)    Niech p - liczba pierwsza. Wtedy: ip(p) = p — 1 = p( 1 — ^), (tylko zero nie jest względnie pierwsze z p).

(3)    Niech p - liczba pierwsza, k £ N. Wtedy ip(p^k) =p^k — p^k~^x = p^k(l — 1), gdyż mamy p^k~^l liczb całkowitych takich, że 0 ^ l < p^k, które są podzielne przez p.

Udowodnimy teraz, że funkcja g> jest funkcją multliplikatywną (uwaga: nie jest to funkcja całkowicie multiplikatywna - tzn. jej multiplikatywność ogranicza się do względnie pierwszych argumentów, takie rozróżnienie w teorii liczb jest bardzo ważne). W dowodzie wykorzystamy twierdzenie chińskie o resztach.

Twierdzenie 1.6.3 (multiplikatywność funkcji Eulera). Z: m, n £ N - względnie pierwsze. T: ip(mń) =    .

Dowód. Niech /:={/■;£ [0,m) : NWD(k,m) = 1}, «/:={/£ [0,n) : NWD(i,n) = 1}

A := {s £ [0, m-n) : NWD(s, m-n) = 1}.

Wtedy oczywiście #(/ x J) = tp(m)ip(n), zaś #(A) = <p(mn). Skonstruujemy bijekcję między zbiorami I x J i A.

Zgodnie z twierdzeniem chińskim o resztach dla dowolnej pary liczb (k,l) £ / x J istnieje dokładnie jedna liczba Zk,i taka, że 0 ^ z^i < mn oraz

Zk,i = A;(mod m) Zkj — l (mod n)

(jedyność wynika z żądania, aby 0 ^ Zkj. < mn). Liczba ta jest względnie pierwsza z m (bo k była) oraz z n (bo l była) stąd jest względnie pierwsza z mn.

Mamy więc dobrze określone odwzorowanie:

$ : / x J 9 (fc, l) —> z_k,i £ A.

(1)    $ jest injekcją.

Niech bowiem z^i — Zk\v i na przykład 0 ^ k < k' < m. Wtedy m\{z^i — k) i m\(zk_ti — k') skąd m\(k' — k), co prowadzi do sprzeczności.

(2)    $ jest surjekcją.

Jeśli bowiem z £ A, to z — <f>(k,l) gdzie k z(mod m) zaś l z(mod n). Łatwo sprawdzić, że (k, l) £ I x J.

□

Wobec tego tp(m)(p(ri) = #(/) • #(</) = #(/ x J) = #(A) = <p(mn).

dla dowolnego n £

Wniosek 1.6.4. ip(n) =n f|

pin, per