9467141764

Twierdzenie. (Własności funkcji Eulera)

(1)    Jeśli p jest liczbą pierwszą, to

<p(p)=p-i-

(2)    Jeśli a € N i p jest liczbą pierwszą, to

V (P“) = (p - 1)

lub równoważnie

V (P°) =

(3) Jeśli au, o;₂, • ••,<*& £ N i n = p"¹ p£² ••• Pk^k> gdzie pi, P2,...,Pk są różnymi liczbami pierwszymi, to

P1

Pk

(4) Jeśli n = pi P2 ... Pk, gdzie Pi, P21 ■■■■.Pk są różnymi liczbami pierwszymi, to V (n) = (Pi ~ 1) (P2 ~ 1) ... (Pk ~ 1) •

(5) Jeśli «!, a₂,    £ N i n = p"¹ p₂² ... p^', gdzie p_l5 p₂, ...,Pfc są różnymi liczbami

pierwszymi, to

<p(n) = cp(j>r) Ip(p?) ■■■‘fipT).

(7) Jeśli m, n € N i (m,n) = 1, to

<p (m n) = ip (m) <p (n).

(8) Jeśli ni, n₂, ...,nt € N i jeśli (n^nj) = 1 dla i ^ j (i,j £ {1,2, ...&}) (tzn. liczby nj, n₂, ..., Ti* są parami względnie pierwsze), to

<p (ni n₂ ... n_fc) = <p (ni) <p (n₂) ... <p (n_fc).

5. Kongruencje

Definicja kongruencji. O dwóch liczbach całkowitych a i 6 mówimy, że przystają do siebie modulo m (m € N), jeśli m \ (a — b).

Jeśli liczby a i b przystają do siebie modulo m, to piszemy a = b (modm). Czyli

a = b(modm) -*=> 3 a — b = km.

ke z

Relacja = nazywa się kongruencją w zbiorze liczb całkowitych.

Twierdzenie. Niech a, ó, c, d będą dowolnymi liczbami całkowitymi. Niech m będzie dowolną liczbą naturalną. Wówczas

7

1

a = a (modm) (zwrotność relacji =).