Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera

22.12.2023

Największy wspólny dzielnik

Definicja H1
Niech będą dane dwie liczby całkowite $a$ i $b$ niebędące jednocześnie zerami. Największym wspólnym dzielnikiem^[1] liczb $a$ i $b$ będziemy nazywali liczbę całkowitą $D$ taką, że

$D ∣ a i D ∣ b$
$d ∣ a i d ∣ b ⟹ d ⩽ D$

gdzie $d$ jest dowolną liczbą całkowitą.

Uwaga H2
Tak zdefiniowaną liczbę $D$ będziemy oznaczali przez $gcd (a, b)$ . Ponieważ $1 ∣ a$ i $1 ∣ b$ , to z definicji wynika natychmiast, że $gcd (a, b) ⩾ 1$ .

Zadanie H3
Pokazać, że

d ∣ gcd (a, b) ⟺ d ∣ a i d ∣ b

Rozwiązanie

$⟹$

Z założenia $d ∣ gcd (a, b)$ . Z definicji największego wspólnego dzielnika $gcd (a, b) ∣ a$ , zatem $d ∣ a$ . Analogicznie pokazujemy, że $d ∣ b$ .

$⟸$

Z założenia $a = r d$ , $b = s d$ . Z lematu Bézouta (zobacz C73) istnieją takie liczby całkowite $x, y$ , że

gcd (a, b) = a x + b y = r d x + s d y = d (r x + s y)

Zatem $d ∣ gcd (a, b)$ .
□

Twierdzenie H4
Jeżeli liczby całkowite $a, b$ nie są jednocześnie równe zero i $gcd (a, b) = a x + b y$ , to $gcd (x, y) = 1$ .

Dowód

Z lematu Bézouta (zobacz C73) wiemy, że liczby całkowite $x, y$ zawsze istnieją. Niech $gcd (a, b) = d > 0$ , zatem $a = d k$ i $b = d m$ , czyli

(d k) x + (d m) y = d

Co oznacza, że $k x + m y = 1$ , ale $gcd (x, y)$ jest dzielnikiem $k x + m y$ (bo jest dzielnikiem $x$ i $y$ ), zatem $gcd (x, y) ∣ 1$ , czyli $gcd (x, y) = 1$ . Co należało pokazać.
□

Twierdzenie H5
Niech $a, b, k \in Z$ . Prawdziwy jest wzór

gcd (a + k b, b) = gcd (a, b)

Dowód

Niech $d_{1} = gcd (a + k b, b)$ i $d_{2} = gcd (a, b)$ .

Z definicji $d_{1} ∣ (a + k b)$ i $d_{1} ∣ b$ , zatem $a + k b = x d_{1}$ i $b = y d_{1}$ , czyli $a + k x d_{1} = x d_{1}$ , skąd natychmiast wynika, że $d_{1} ∣ a$ . Ponieważ $d_{1} ∣ b$ , to $d_{1} ∣ d_{2}$ (zobacz H2).

Z definicji $d_{2} ∣ a$ i $d_{2} ∣ b$ , zatem $d_{2} ∣ (a + k b)$ i $d_{2} ∣ b$ , czyli $d_{2} ∣ d_{1}$ .

Ponieważ $d_{1} ∣ d_{2}$ i $d_{2} ∣ d_{1}$ , to $| d_{1} | = | d_{2} |$ . Co kończy dowód.
□

Twierdzenie H6
Niech $a, b, m \in Z$ . Prawdziwa jest następująca równoważność

gcd (a, m) = 1 i gcd (b, m) = 1 ⟺ gcd (a b, m) = 1

Dowód

$⟹$

Niech $gcd (a b, m) = d$ . Z definicji $d ∣ a b$ i $d ∣ m$ . Gdyby było $d > 1$ , to istniałaby liczba pierwsza $p$ taka, że $p ∣ d$ i mielibyśmy $p ∣ a b$ i $p ∣ m$ . Jeżeli $p ∣ a b$ , to $p ∣ a$ lub $p ∣ b$ (zobacz C74). W przypadku, gdy $p ∣ a$ dostajemy $gcd (a, m) ⩾ p > 1$ , wbrew założeniu, że $gcd (a, m) = 1$ . Analogicznie pokazujemy sprzeczność, gdy $p ∣ b$ .

$⟸$

Niech $gcd (a, m) = d$ . Z definicji $d ∣ a$ i $d ∣ m$ , zatem również $d ∣ a b$ i $d ∣ m$ . Mamy stąd

1 = gcd (a b, m) ⩾ d ⩾ 1

Czyli musi być $d = 1$ . Analogicznie pokazujemy, że $gcd (b, m) = 1$ .
□

Twierdzenie H7
Dla $a, b, m \in Z$ jest

gcd (a b, m) ∣ gcd (a, m) \cdot gcd (b, m)

Dowód

Wprowadźmy oznaczenia

r = gcd (a b, m)

s = gcd (a, m)

t = gcd (b, m)

Z lematu Bézouta (zobacz C73) istnieją takie liczby $x, y, X, Y$ , że

s = a x + m y

t = b X + m Y

Zatem

s t = (a x + m y) (b X + m Y) = a b x X + a m x Y + m b y X + m^{2} y Y

ale $r ∣ a b$ i $r ∣ m$ , skąd otrzymujemy, że $r ∣ s t$ . Co należało pokazać.
□

Twierdzenie H8
Jeżeli liczby $a, b$ są względnie pierwsze, to

gcd (a b, m) = gcd (a, m) \cdot gcd (b, m)

Dowód

Wprowadźmy oznaczenia

r = gcd (a b, m)

s = gcd (a, m)

t = gcd (b, m)

Z założenia $gcd (a, b) = 1$ . Ponieważ $s ∣ a$ oraz $t ∣ b$ , to $gcd (s, t) = 1$ , zatem (zobacz C75)

s ∣ a i t ∣ b ⟹ s t ∣ a b

s ∣ m i t ∣ m ⟹ s t ∣ m

Wynika stąd, że $s t ∣ gcd (a b, m)$ , czyli $s t ∣ r$ . Z poprzedniego twierdzenia wiemy, że $r ∣ s t$ , zatem $| r | = | s t |$ . Co kończy dowód.
□

Twierdzenie H9
Jeżeli liczby $b, m$ są względnie pierwsze, to

gcd (a b, m) = gcd (a, m)

Dowód

Wprowadźmy oznaczenia

r = gcd (a b, m)

s = gcd (a, m)

Z lematu Bézouta istnieją takie liczby $x, y$ , że

r = a b x + m y

Ale $s ∣ a$ i $s ∣ m$ , zatem $s ∣ r$ .

Z założenia $gcd (b, m) = 1$ , zatem z twierdzenia H7 wynika natychmiast, że $r ∣ s$ . Ponieważ $s ∣ r$ i $r ∣ s$ , to $| r | = | s |$ . Co należało pokazać.
□

Twierdzenie H10
Jeżeli liczby $a, b$ nie są jednocześnie równe zero i $m \neq 0$ , to

gcd (a m, b m) = | m | \cdot gcd (a, b)

Dowód

Oznaczmy $d = gcd (a, b)$ i $D = gcd (a m, b m)$ . Pokażemy, że $d m ∣ D$ .

\begin{array}{llll} d = gcd (a, b) & ⟹ & d ∣ a i d ∣ b & (zobacz H3) \\ ⟹ & d m ∣ a m i d m ∣ b m \\ ⟹ & d m ∣ gcd (a m, b m) & (zobacz H3) \\ ⟹ & d m ∣ D \end{array}

Pokażemy, że $D ∣ d m$ .

\begin{array}{llll} d = gcd (a, b) & ⟹ & d = a x + b y & (lemat Bézouta C73) \\ ⟹ & d m = a m x + b m y \\ ⟹ & D ∣ d m \end{array}

Ostatnia implikacja korzysta z tego, że $D ∣ a m$ i $D ∣ b m$ (zobacz H3). Ponieważ $d m ∣ D$ i $D ∣ d m$ , to $| D | = | d m |$ . Co należało pokazać.
□

Zadanie H11
Pokazać, że $a ∣ b$ wtedy i tylko wtedy, gdy $a ∣ gcd (a, b)$ .

Rozwiązanie

$⟹$

Zakładając, że $a ∣ b$ , dostajemy

\begin{array}{llll} a ∣ b & ⟹ & b = k a \\ ⟹ & gcd (a, b) = gcd (a, k a) = | a | \cdot gcd (1, k) = | a | & (zobacz H10) \\ ⟹ & a ∣ gcd (a, b) \end{array}

$⟸$

Jeżeli $a ∣ gcd (a, b)$ , to $a ∣ b$ (zobacz H3). Co należało pokazać.
□

Zadanie H12
Niech $gcd (a, d) = 1$ . Pokazać, że $d ∤ a b$ wtedy i tylko wtedy, gdy $d ∤ b$ .

Rozwiązanie

Korzystając z rezultatu pokazanego w zadaniu H11, dostajemy

\begin{array}{llll} d ∤ a b & ⟺ & d ∤ gcd (d, a b) \\ ⟺ & d ∤ gcd (d, b) & (zobacz H9) \\ ⟺ & d ∤ b \end{array}

Co należało pokazać.
□

Twierdzenie H13
Jeżeli dodatnie liczby $a, b$ są względnie pierwsze, to każdy dzielnik $d$ iloczynu $a b$ można przedstawić jednoznacznie w postaci $d = d_{1} d_{2}$ , gdzie $d_{1} ∣ a,$ $d_{2} ∣ b$ $i gcd (d_{1}, d_{2}) = 1$ .

Dowód

Niech $d_{1} = gcd (d, a)$ i $d_{2} = gcd (d, b)$ . Z twierdzenia H8 mamy

d_{1} d_{2} = gcd (d, a) \cdot gcd (d, b) = gcd (d, a b) = d

Bo z założenia $d ∣ a b$ . Z definicji największego wspólnego dzielnika i zadania H3 dostajemy

gcd (d_{1}, d_{2}) = e ⟹ e ∣ d_{1} i e ∣ d_{2}

⟹ e ∣ gcd (d, a) i e ∣ gcd (d, b)

⟹ e ∣ a i e ∣ b

⟹ e ∣ gcd (a, b)

⟹ gcd (a, b) ⩾ e

Gdyby było $gcd (d_{1}, d_{2}) = e > 1$ , to mielibyśmy $gcd (a, b) ⩾ e > 1$ . Wbrew założeniu, że $gcd (a, b) = 1$ . Co kończy dowód.
□

Twierdzenie H14
Jeżeli $a, m, n \in Z_{+}$ , to

gcd (a^{m} - 1, a^{n} - 1) = a^{gcd (m, n)} - 1

Dowód

Pokażemy najpierw, że jeżeli $d$ jest dzielnikiem lewej strony dowodzonej równości, to jest również dzielnikiem prawej strony i odwrotnie.

$⟹$

Z założenia $d$ jest dzielnikiem $gcd (a^{m} - 1, a^{n} - 1)$ , czyli $d ∣ (a^{m} - 1)$ i $d ∣ (a^{n} - 1)$ , co możemy zapisać w postaci

a^{m} \equiv 1 (\mod d) oraz a^{n} \equiv 1 (\mod d)

Z lematu Bézouta (zobacz C73) wiemy, że istnieją takie liczby $x, y$ , że $gcd (m, n) = m x + n y$ . Łatwo znajdujemy, że

a^{gcd (m, n)} \equiv a^{m x + n y} \equiv (a^{m})^{x} \cdot (a^{n})^{y} \equiv 1^{x} \cdot 1^{y} \equiv 1 (\mod d)

Czyli $d | (a^{gcd (m, n)} - 1)$ .

$⟸$

Z założenia $d | (a^{gcd (m, n)} - 1)$ , czyli

a^{gcd (m, n)} \equiv 1 (\mod d)

Zatem

a^{m} \equiv {[a^{gcd (m, n)}]}^{\frac{m}{gcd (m, n)}} \equiv 1 (\mod d)

Podobnie otrzymujemy

a^{n} \equiv 1 (\mod d)

Zatem $d$ dzieli $a^{m} - 1$ i $a^{n} - 1$ , czyli

d ∣ gcd (a^{m} - 1, a^{n} - 1)

W szczególności wynika stąd, że

$gcd (a^{m} - 1, a^{n} - 1) | (a^{gcd (m, n)} - 1)$

$(a^{gcd (m, n)} - 1) | gcd (a^{m} - 1, a^{n} - 1)$

Czyli $| gcd (a^{m} - 1, a^{n} - 1) | = | a^{gcd (m, n)} - 1 |$ . Co kończy dowód.
□

Uwaga H15
W dowodzie twierdzenia H14 pominęliśmy milczeniem fakt, że jedna z liczb $x, y$ może być (i często jest) ujemna. Choć rezultat jest prawidłowy, to nie wiemy, co oznacza zapis

a^{- 1000} \equiv 1^{- 10} \equiv 1 (\mod d)

Omówimy ten problem w następnej sekcji. Zauważmy, wyprzedzając materiał, że z kongruencji

a^{m} \equiv 1 (\mod d) oraz a^{n} \equiv 1 (\mod d)

wynika, że $gcd (a, d) = 1$ i liczba $a$ ma element odwrotny modulo $d$ .

Element odwrotny modulo $m$

Twierdzenie H16
Niech $m \in Z_{+}$ . Dla liczby $a \in Z$ istnieje taka liczba $x$ , że

a x \equiv 1 (\mod m)

wtedy i tylko wtedy, gdy $gcd (a, m) = 1$ .

Dowód

$⟹$

Z założenia istnieje taka liczba $x$ , że

a x \equiv 1 (\mod m)

Zatem dla pewnego $k \in Z$ jest

a x = 1 + k m

Czyli $a x - k m = 1$ . Wynika stąd, że $gcd (a, m)$ dzieli $1$ , co oznacza, że $gcd (a, m) = 1$ .

$⟸$

Z założenia $gcd (a, m) = 1$ . Z lematu Bézouta (zobacz C73) wynika, że istnieją takie liczby całkowite $x, y$ , że

a x + m y = 1

Zatem modulo $m$ dostajemy

a x \equiv 1 (\mod m)

Co kończy dowód.
□

Definicja H17
Niech $m \in Z_{+}$ . Liczbę $x$ taką, że

a \cdot x \equiv 1 (\mod m)

będziemy nazywali elementem odwrotnym liczby $a$ modulo $m$ i oznaczali jako $a^{- 1}$ .

Uwaga H18
Oznaczenie elementu odwrotnego ma naturalne uzasadnienie. Zauważmy, że jeżeli $b ∣ a$ oraz $b$ ma element odwrotny modulo $m$ , to prawdziwa jest kongruencja

\frac{a}{b} \equiv a b^{- 1} (\mod m)

Istotnie

\frac{a}{b} = \frac{a}{b} \cdot 1 \equiv \frac{a}{b} \cdot b b^{- 1} \equiv a b^{- 1} (\mod m)

W PARI/GP odwrotność liczby $a$ modulo $m$ znajdujemy, wpisując Mod(a, m)^(-1).

Twierdzenie H19
Niech $a, k \in Z$ , $m \in Z_{+}$ . Poniższa tabelka przedstawia elementy odwrotne do elementu $a$ w przypadku niektórych modułów $m$ . W szczególności, jeżeli moduł $m$ jest liczbą nieparzystą, to $2^{- 1} \equiv \frac{m + 1}{2} (\mod m)$ .

	postać modułu $m$	odwrotność elementu $a$	uwagi
$1.$	$m = 2$	$1$	liczba $a$ jest liczbą nieparzystą
$2.$	$m = 4$	$R_{4} (a)$
$3.$	$m = 8$	$R_{8} (a)$
$4.$	$m = a k - 1$	$\frac{m + 1}{a}$
$5.$	$m = a k + 1$	$- \frac{m - 1}{a}$
$6.$	$m = a k - 2$	$\frac{m + 1}{2} \cdot \frac{m + 2}{a}$	liczby $a, m$ są liczbami nieparzystymi
$7.$	$m = a k + 2$	$\frac{m - 1}{2} \cdot \frac{m - 2}{2}$	liczby $a, m$ są liczbami nieparzystymi

Dowód

Punkty 1. - 3.

Ponieważ dla liczb nieparzystych jest

a^{2} \equiv 1 (\mod 2)

a^{2} \equiv 1 (\mod 4)

a^{2} \equiv 1 (\mod 8)

to liczba nieparzysta $a$ jest swoją odwrotnością modulo $2$ , $4$ i $8$ . Ponieważ element odwrotny jest definiowany modulo, zatem możemy napisać

a^{- 1} \equiv R_{2} (a) (\mod 2)

a^{- 1} \equiv R_{4} (a) (\mod 4)

a^{- 1} \equiv R_{8} (a) (\mod 8)

W pierwszym przypadku wynik jest oczywisty, bo $R_{2} (a) = 1$ .

Punkt 4.

Zauważmy, że

gcd (a, m) = gcd (a, a k - 1) = gcd (a, - 1) = 1

oraz $a ∣ (m + 1)$ . Zatem

a \cdot a^{- 1} = a \cdot \frac{m + 1}{a} = m + 1 \equiv 1 (\mod m)

Punkt 5.

Zauważmy, że

gcd (a, m) = gcd (a, a k + 1) = gcd (a, 1) = 1

oraz $a ∣ (m - 1)$ . Zatem

a \cdot a^{- 1} = a \cdot [- (\frac{m - 1}{a})] = - m + 1 \equiv 1 (\mod m)

Punkt 6.

Ponieważ zakładamy, że $2 ∣ (m + 1)$ , to $m$ musi być liczbą nieparzystą, czyli $a$ też musi być liczbą nieparzystą. Zauważmy, że

gcd (a, m) = gcd (a, a k - 2) = gcd (a, - 2) = 1

oraz $a ∣ (m + 2)$ . Zatem

a \cdot a^{- 1} = a \cdot (\frac{m + 1}{2} \cdot \frac{m + 2}{a}) = \frac{m + 1}{2} \cdot (m + 2) \equiv \frac{m + 1}{2} \cdot 2 \equiv m + 1 \equiv 1 (\mod m)

Podobnie pokazujemy punkt 7. Co kończy dowód.
□

Twierdzenie H20
Niech $a, b \in Z$ , $m \in Z_{+}$ i liczba $a$ ma element odwrotny modulo $m$ . Jeżeli liczby $u_{1}, u_{2}, \dots, u_{r}$ są liczbami różnymi modulo $m$ , to liczby

1.

a u_{1}, a u_{2}, \dots, a u_{r}

2.

a u_{1} + b, a u_{2} + b, \dots, a u_{r} + b

są liczbami różnymi modulo $m$ . Jeżeli ponadto liczby $u_{1}, u_{2}, \dots, u_{r}$ są względnie pierwsze z $m$ , to również liczby

3.

u_{1}^{- 1}, u_{2}^{- 1}, \dots, u_{r}^{- 1}

są liczbami różnymi modulo $m$ .

Dowód

Punkt 1.

Przypuśćmy dla uzyskania sprzeczności, że istnieją takie różne wskaźniki $i, j$ , że

a u_{i} \equiv a u_{j} (\mod m)

Z założenia liczba $a$ ma element odwrotny modulo $m$ , zatem mnożąc obie strony kongruencji przez $a^{- 1}$ , otrzymujemy

u_{i} \equiv u_{j} (\mod m)

dla $i \neq j$ , wbrew założeniu, że liczby $u_{1}, u_{2}, \dots, u_{r}$ są różne modulo $m$ . Dowód punktu 2. jest analogiczny.

Punkt 3.

Przypuśćmy dla uzyskania sprzeczności, że istnieją takie różne wskaźniki $i, j$ , że

u_{i}^{- 1} \equiv u_{j}^{- 1} (\mod m)

u_{j} u_{i}^{- 1} \equiv 1 (\mod m)

u_{j} u_{i}^{- 1} u_{i} \equiv u_{i} (\mod m)

u_{j} \equiv u_{i} (\mod m)

Ponownie otrzymujemy $u_{i} \equiv u_{j} (\mod m)$ dla $i \neq j$ , wbrew założeniu, że liczby $u_{1}, u_{2}, \dots, u_{r}$ są różne modulo $m$ . Co należało pokazać.
□

Zadanie H21
Niech $p$ będzie liczbą pierwszą. Pokazać, że dla $k \in [0, p - 1]$ prawdziwa jest kongruencja

(\binom{p - 1}{k}) \equiv (- 1)^{k} (\mod p)

Rozwiązanie

Zauważmy, że modulo $p$ mamy

(\binom{p - 1}{k}) = \frac{(p - 1)!}{k! \cdot (p - 1 - k)!}

= \frac{(p - 1) (p - 2) \cdot \dots \cdot (p - k)}{k!}

\equiv (p - 1) (p - 2) \cdot \dots \cdot (p - k) \cdot (k!)^{- 1}

\equiv (- 1)^{k} \cdot k! \cdot (k!)^{- 1}

\equiv (- 1)^{k} (\mod p)

Co należało pokazać.
□

Zadanie H22
Niech $A$ i $B$ będą zbiorami skończonymi. Pokazać, że jeżeli $A \subseteq B i | A | = | B |$ , to $A = B$ .

Rozwiązanie

Pierwszy sposób

Z definicji zbiory $A$ i $B$ są równe wtedy i tylko wtedy, gdy jednocześnie spełnione są warunki

$x \in A ⟹ x \in B$
$x \in B ⟹ x \in A$

Z założenia $A \subseteq B$ , zatem warunek 1. jest spełniony. Przypuśćmy, że istnieje taki element $x$ , że $x \in B$ , ale $x \notin A$ . Jeśli tak, to

| B | = | A | + 1

Co jest sprzeczne z założeniem, że $| A | = | B |$ .

Uwaga
Łatwo zauważyć, że wybierając z trzech warunków $A \subseteq B$ , $B \subseteq A$ i $| A | = | B |$ dowolne dwa, zawsze otrzymamy z nich trzeci. Oczywiście nie dotyczy to zbiorów nieskończonych. Przykładowo liczby parzyste stanowią podzbiór liczb całkowitych, liczb parzystych jest tyle samo, co liczb całkowitych^[2], ale zbiór liczb całkowitych nie jest podzbiorem zbioru liczb parzystych.

Drugi sposób

Ponieważ zbiór $A$ jest z założenia podzbiorem zbioru $B$ , to zbiór $B$ można przedstawić w postaci sumy zbioru $A$ i pewnego zbioru $C$ takiego, że żaden element zbioru $C$ nie jest elementem zbioru $A$ . Zatem

B = A \cup C i A \cap C = \emptyset

Ponieważ zbiory $A$ i $C$ są rozłączne, to wiemy, że

| A \cup C | = | A | + | C |

Czyli

| B | = | A \cup C | = | A | + | C |

Skąd wynika, że $| C | = 0$ , zatem zbiór $C$ jest zbiorem pustym i otrzymujemy natychmiast $B = A$ . Co należało pokazać.

Uwaga (przypadek zbiorów skończonych)
Najczęściej prawdziwe jest jedynie oszacowanie $| A \cup C | ⩽ | A | + | C |$ , bo niektóre elementy mogą zostać policzone dwa razy. Elementy liczone dwukrotnie to te, które należą do iloczynu zbiorów $| A |$ i $| C |$ , zatem od sumy $| A | + | C |$ musimy odjąć liczbę elementów iloczynu zbiorów $| A |$ i $| C |$ . Co daje ogólny wzór^[3]

| A \cup C | = | A | + | C | - | A \cap C |

□

Definicja H23
Niech elementy każdego ze zbiorów $A = {a_{1}, a_{2}, \dots, a_{r}}$ oraz $B = {b_{1}, b_{2}, \dots, b_{r}}$ będą różne modulo $m$ . Powiemy, że zbiory $A, B$ są równe modulo $m$ , jeżeli dla każdego $k = 1, \dots, r$ istnieje takie $j = 1, \dots, r$ , że prawdziwa jest kongruencja $a_{k} \equiv b_{j} (\mod m)$ .

Twierdzenie H24
Niech elementy każdego ze zbiorów $A = {a_{1}, a_{2}, \dots, a_{r}}$ oraz $B = {b_{1}, b_{2}, \dots, b_{r}}$ będą różne modulo $m$ . Zbiory $A, B$ są równe modulo $m$ wtedy i tylko wtedy, gdy zbiory $A^{'} = {R_{m} (a_{1}), R_{m} (a_{2}), \dots, R_{m} (a_{r})}$ i $B^{'} = {R_{m} (b_{1}), R_{m} (b_{2}), \dots, R_{m} (b_{r})}$ są równe.

Dowód

$⟹$

Ponieważ elementy każdego ze zbiorów $A, B$ są różne modulo $m$ , to elementy zbiorów $A^{'}$ i $B^{'}$ są wszystkie różne. Czyli $| A^{'} | = | B^{'} | = r$ . Ponieważ warunek

a_{k} \equiv b_{j} (\mod m)

oznacza, że reszty z dzielenia liczb $a_{k}$ i $b_{j}$ przez $m$ są równe, to z założenia dla każdego $k = 1, \dots, r$ istnieje takie $j = 1, \dots, r$ , że

R_{m} (a_{k}) = R_{m} (b_{j})

A to oznacza, że każdy element zbioru $A^{'}$ należy do zbioru $B^{'}$ , czyli $A^{'} \subseteq B^{'}$ . Wynika stąd, że $A^{'} = B^{'}$ (zobacz H22). Co należało pokazać.

$⟸$

Ponieważ zbiory $A^{'}, B^{'}$ są równe, to zbiór $A^{'}$ jest podzbiorem zbioru $B^{'}$ , czyli dla każdego elementu $R_{m} (a_{k}) \in A^{'}$ istnieje taki element $R_{m} (b_{j}) \in B^{'}$ , że

R_{m} (a_{k}) = R_{m} (b_{j})

Ponieważ równość reszt oznacza równość modulo, zatem

a_{k} \equiv b_{j} (\mod m)

Wynika stąd, że dla każdego $k = 1, \dots, r$ istnieje takie $j = 1, \dots, r$ , że prawdziwa jest kongruencja

a_{k} \equiv b_{j} (\mod m)

czyli zbiory $A, B$ są równe modulo $m$ . Co kończy dowód.
□

Twierdzenie H25
Niech będą dane zbiory $A = {1, 2, \dots, p - 1}$ , $B = {b_{1}, b_{2}, \dots, b_{p - 1}}$ , gdzie $p$ jest liczbą pierwszą. Jeżeli wszystkie elementy zbioru $B$ są różne modulo $p$ i żadna z liczb $b_{k} \in B$ nie jest podzielna przez $p$ , to zbiory $A, B, C = {b_{1}^{- 1}, b_{2}^{- 1}, \dots, b_{p - 1}^{- 1}}$ są równe modulo $p$ .

Dowód

Z definicji zbioru $A$ wszystkie elementy tego zbioru są różne modulo $p$ . Łatwo zauważamy, że

A = {1, 2, \dots, p - 1} = {R_{p} (1), R_{p} (2), \dots, R_{p} (p - 1)} = A^{'}

Ponieważ wszystkie liczby $b_{k} \in B$ , gdzie $k = 1, \dots, p - 1$ są różne modulo $p$ i nie są podzielne przez $p$ , to reszty $R_{p} (b_{1}), R_{p} (b_{2}), \dots, R_{p} (b_{p - 1})$ są wszystkie dodatnie i różne, a ponieważ jest ich $p - 1$ , czyli dokładnie tyle, ile jest różnych i dodatnich reszt z dzielenia przez liczbę $p$ , to zbiór tych reszt jest identyczny ze zbiorem dodatnich reszt z dzielenia przez $p$ , czyli ze zbiorem $A$ . Zatem mamy

A = A^{'} = {R_{p} (b_{1}), R_{p} (b_{2}), \dots, R_{p} (b_{p - 1})} = B^{'}

Na mocy twierdzenia H24 zbiory $A$ i $B$ są równe modulo $p$ .

Z twierdzenia H20 wiemy, że wszystkie liczby $b_{k}^{- 1} \in C$ są różne modulo $p$ . Zauważmy, że każda z tych liczb jest względnie pierwsza z $p$ , zatem nie może być podzielna przez $p$ . Wynika stąd, że reszty $R_{p} (b_{1}^{- 1}), R_{p} (b_{2}^{- 1}), \dots, R_{p} (b_{p - 1}^{- 1})$ są wszystkie dodatnie i różne, a ponieważ jest ich $p - 1$ , czyli dokładnie tyle, ile jest różnych i dodatnich reszt z dzielenia przez liczbę $p$ , to zbiór tych reszt jest identyczny ze zbiorem dodatnich reszt z dzielenia przez $p$ , czyli ze zbiorem $A$ . Zatem mamy

A = A^{'} = {R_{p} (b_{1}^{- 1}), R_{p} (b_{2}^{- 1}), \dots, R_{p} (b_{p - 1}^{- 1})} = C^{'}

Na mocy twierdzenia H24 zbiory $A$ i $C$ są równe modulo $p$ . Ponieważ $A^{'} = B^{'}$ i $A^{'} = C^{'}$ , to $B^{'} = C^{'}$ i ponownie na mocy twierdzenia H24 zbiory $B$ i $C$ są równe modulo $p$ . Co należało pokazać.
□

Zadanie H26
Niech $p$ będzie liczbą pierwszą nieparzystą. Pokazać, że suma $\sum_{k = 1}^{p - 1} \frac{(p - 1)!}{k}$ jest podzielna przez $p$ .

Rozwiązanie

Zauważmy najpierw, że modulo $p$ następujące sumy są równe

\sum_{k = 1}^{p - 1} k \equiv \sum_{k = 1}^{p - 1} k^{- 1} (\mod p)

Istotnie, jeśli przyjmiemy w twierdzeniu H25, że zbiór $B = {1, 2, \dots, p - 1}$ , to zbiór $C$ będzie zbiorem liczb, które są odwrotnościami liczb $1, 2, \dots, p - 1$ modulo $p$ i możemy napisać

\sum_{x \in B} x \equiv \sum_{y \in C} y (\mod p)

bo

gdy $x$ przebiega kolejne wartości $b_{k}$ , to $x$ przyjmuje kolejno wartości $1, 2, \dots, p - 1$

gdy $y$ przebiega kolejne wartości $b_{k}^{- 1}$ , to $y$ (modulo $p$ ) przyjmuje wszystkie wartości ze zbioru $A = {1, 2, \dots, p - 1}$ , czyli liczba $y$ (modulo $p$ ) przyjmuje wszystkie wartości $1, 2, \dots, p - 1$ , ale w innej kolejności

Ponieważ kolejność sumowania tych samych składników nie wpływa na wartość sumy, to prawdziwa jest wyżej wypisana równość sum modulo $p$ .

Zatem modulo $p$ otrzymujemy

\sum_{k = 1}^{p - 1} \frac{(p - 1)!}{k} \equiv \sum_{k = 1}^{p - 1} (p - 1)! \cdot k^{- 1}

\equiv (p - 1)! \cdot \sum_{k = 1}^{p - 1} k^{- 1}

\equiv (p - 1)! \cdot \sum_{k = 1}^{p - 1} k

\equiv (p - 1)! \cdot \frac{(p - 1) p}{2}

\equiv (p - 1)! \cdot \frac{p - 1}{2} \cdot p

\equiv 0 (\mod p)

Należy zauważyć, że dla liczby pierwszej nieparzystej $p$ liczba $\frac{p - 1}{2}$ jest liczbą całkowitą.
□

Funkcje multiplikatywne

Definicja H27
Powiemy, że funkcja $f (n)$ określona w zbiorze liczb całkowitych dodatnich jest funkcją multiplikatywną, jeżeli $f (1) = 1$ i dla względnie pierwszych liczb $a, b$ spełniony jest warunek $f (a b) = f (a) f (b)$ .

Uwaga H28
Założenie $f (1) = 1$ możemy równoważnie zastąpić założeniem, że funkcja $f (n)$ nie jest tożsamościowo równa zero. Gdyby $f (n)$ spełniała jedynie warunek $f (a b) = f (a) f (b)$ dla względnie pierwszych liczb $a, b$ , to mielibyśmy

a)

f (n)

jest tożsamościowo równa zeru wtedy i tylko wtedy, gdy

f (1) = 0

b)

f (n)

nie jest tożsamościowo równa zeru wtedy i tylko wtedy, gdy

f (1) = 1

Ponieważ $f (1) = f (1 \cdot 1) = f (1) f (1)$ , zatem $f (1) = 0$ lub $f (1) = 1$ .

Jeżeli $f (1) = 0$ , to dla dowolnego $n$ mamy

f (n) = f (n \cdot 1) = f (n) f (1) = 0

Czyli $f (n)$ jest funkcją tożsamościowo równą zero.

Jeżeli $f (n)$ nie jest funkcją tożsamościowo równą zero, to istnieje taka liczba $a \in Z_{+}$ , że $f (a) \neq 0$ . Zatem

f (a) = f (a \cdot 1) = f (a) f (1)

I dzieląc obie strony przez $f (a) \neq 0$ , dostajemy $f (1) = 1$ .

Przykład H29
Ponieważ $gcd (1, c) = 1$ , to $gcd (n, c)$ rozpatrywana jako funkcja $n$ , gdzie $c$ jest ustaloną liczbą całkowitą, jest funkcją multiplikatywną (zobacz H8).

Twierdzenie H30
Jeżeli funkcja $f (n)$ jest funkcją multiplikatywną, to funkcja

F (n) = \sum_{d ∣ n} f (d)

gdzie sumowanie przebiega po wszystkich dzielnikach dodatnich liczby $n$ , jest również funkcją multiplikatywną.

Dowód

Ponieważ

F (1) = \sum_{d ∣ 1} f (d) = f (1) = 1

to funkcja $F (n)$ spełnia pierwszy warunek definicji H27.

Niech $a, b$ będą względnie pierwszymi liczbami dodatnimi. Każdy dzielnik dodatni iloczynu $a b$ można zapisać w postaci $d = d_{1} d_{2}$ , gdzie $d_{1} ∣ a$ , $d_{2} ∣ b$ oraz $gcd (d_{1}, d_{2}) = 1$ (zobacz H13). Niech zbiory

S_{a} = {d \in Z_{+} : d ∣ a}

S_{b} = {d \in Z_{+} : d ∣ b}

S_{a b} = {d \in Z_{+} : d ∣ a b}

będą zbiorami dzielników dodatnich liczb $a, b$ i $a b$ . Dla przykładu

S_{5} = {1, 5}

S_{7} = {1, 7}

S_{35} = {1, 5, 7, 35}

Dla dowolnego $d_{1} \in S_{a}$ i $d_{2} \in S_{b}$ musi być $gcd (d_{1}, d_{2}) = 1$ , bo gdyby było $gcd (d_{1}, d_{2}) = g > 1$ , to

g ∣ d_{1} i d_{1} ∣ a ⟹ g ∣ a

g ∣ d_{2} i d_{2} ∣ b ⟹ g ∣ b

Zatem $g ∣ gcd (a, b)$ i mielibyśmy $gcd (a, b) ⩾ g > 1$ , wbrew założeniu.

Przekształcając, otrzymujemy

F (a b) = \sum_{d ∣ a b} f (d)

= \sum_{d \in S_{a b}} f (d)

= \underset{d_{2} \in S_{b}}{\sum_{d_{1} \in S_{a}}} f (d_{1} d_{2})

= \underset{d_{2} \in S_{b}}{\sum_{d_{1} \in S_{a}}} f (d_{1}) f (d_{2})

= \sum_{d_{1} \in S_{a}} f (d_{1}) \sum_{d_{2} \in S_{b}} f (d_{2})

= \sum_{d_{1} ∣ a} f (d_{1}) \sum_{d_{2} ∣ b} f (d_{2})

= F (a) F (b)

Co należało pokazać.
□

Funkcja Eulera $φ (n)$

Definicja H31
Funkcja Eulera $φ (n)$ ^[4] jest równa ilości liczb całkowitych dodatnich nie większych od $n$ i względnie pierwszych z $n$ .

Twierdzenie H32
Funkcja Eulera $φ (n)$ jest multiplikatywna, czyli dla względnie pierwszych liczb $m, n$ jest $φ (m n) = φ (m) φ (n)$ .

Dowód

Niech $m, n$ będą dodatnimi liczbami całkowitymi takimi, że $gcd (m, n) = 1$ . Twierdzenie jest prawdziwe dla $n = 1$ , zatem nie zmniejszając ogólności, możemy założyć, że $n > 1$ . Wypiszmy w tabeli wszystkie liczby od $1$ do $m n$ .

$1$	$2$	$\dots$	$k$	$\dots$	$m$
$m + 1$	$m + 2$	$\dots$	$m + k$	$\dots$	$2 m$
$2 m + 1$	$2 m + 2$	$\dots$	$2 m + k$	$\dots$	$3 m$
$\dots$	$\dots$	$\dots$	$\dots$
$(n - 1) m + 1$	$(n - 1) m + 2$	$\dots$	$(n - 1) m + k$	$\dots$	$n m$

1. Natychmiast widzimy, że w pierwszym wierszu mamy $φ (m)$ liczb względnie pierwszych z $m$ . Tak samo jest w każdym kolejnym wierszu, bo (zobacz H5)

gcd (r m + k, m) = gcd (k, m)

Zatem mamy dokładnie $φ (m)$ kolumn liczb względnie pierwszych z $m$ .

2. Załóżmy, że liczba $k$ jest jedną z liczb względnie pierwszych z $m$ , czyli $gcd (k, m) = 1$ . Przy tym założeniu $k$ -ta kolumna (pokazana w tabeli) jest kolumną liczb względnie pierwszych z $m$ .

3. Zauważmy, że reszty z dzielenia liczb wypisanych w $k$ -tej kolumnie przez $n$ są wszystkie różne. Gdyby tak nie było, to dla pewnych $i, j$ , gdzie $0 ⩽ i, j ⩽ n - 1$ , różnica liczb $i m + k$ oraz $j m + k$ byłaby podzielna przez $n$ . Mielibyśmy

n ∣ ((i m + k) - (j m + k))

Skąd wynika natychmiast

n ∣ (i - j) m

Ponieważ założyliśmy, że $gcd (n, m) = 1$ , to musi być $n ∣ (i - j)$ (zobacz C74), ale

0 ⩽ | i - j | ⩽ n - 1

Czyli $n$ może dzielić $i - j$ tylko w przypadku, gdy $i = j$ . Wbrew naszemu przypuszczeniu, że istnieją różne liczby dające takie same reszty przy dzieleniu przez $n$ .

4. Ponieważ w $k$ -tej kolumnie znajduje się dokładnie $n$ liczb i reszty z dzielenia tych liczb przez $n$ są wszystkie różne, to reszty te tworzą zbiór $S = {0, 1, \dots, n - 1}$ . Wynika stąd, że liczby wypisane w $k$ -tej kolumnie mogą być zapisane w postaci

a_{r} = b_{r} \cdot n + r

gdzie $r = 0, 1, \dots, n - 1$ i $b_{r} \in Z$ .

Zauważmy, że następujące ilości liczb są sobie równe

ilość liczb w $k$ -tej kolumnie względnie pierwszych z $n$

ilość liczb $r$ względnie pierwszych z $n$ , gdzie $r = 0, \dots, n - 1$ , bo $gcd (b_{r} \cdot n + r, n) = gcd (r, n)$

ilość liczb $r$ względnie pierwszych z $n$ , gdzie $r = 1, \dots, n$ , bo $gcd (n, n) = gcd (0, n) = | n | > 1$

Ostatnia ilość liczb jest równa $φ (n)$ , co wynika wprost z definicji funkcji $φ (n)$ .

5. Zbierając: mamy w wypisanej tabeli dokładnie $φ (m) φ (n)$ liczb $u \in [1, m n]$ , dla których jednocześnie jest

gcd (u, m) = 1 i gcd (u, n) = 1

Z twierdzenia H6 wynika, że w tabeli jest dokładnie $φ (m) φ (n)$ liczb $u \in [1, m n]$ , dla których jest

gcd (u, m n) = 1

Zatem $φ (m n) = φ (m) φ (n)$ . Co należało pokazać.
□

Twierdzenie H33
Dla dowolnej liczby całkowitej dodatniej $n$ jest

φ (n) = n \cdot \prod_{p | n} (1 - \frac{1}{p})

gdzie iloczyn obliczamy po wszystkich liczbach pierwszych $p$ , będących dzielnikami liczby $n$ .

Dowód

Ponieważ wszystkie liczby naturalne mniejsze od liczby pierwszej $p$ są jednocześnie pierwsze względem $p$ , to $φ (p) = p - 1$ .

Równie łatwo znajdujemy wartość funkcji $φ (n)$ w przypadku gdy $n$ jest potęgą liczby pierwszej $n = p^{k}$ . Wystarczy zauważyć, że w ciągu kolejnych liczb

1, 2, 3, 4, \dots, p^{k} - 1, p^{k}

jedynymi liczbami, które nie są pierwsze względem $p^{k}$ , są te, które dzielą się przez $p$ i jest ich $p^{k - 1}$ , co widać natychmiast po ich bezpośrednim wypisaniu

1 \cdot p, 2 \cdot p, 3 \cdot p, \dots, (p^{k - 1} - 1) \cdot p, p^{k - 1} \cdot p

Zatem

φ (p^{k}) = p^{k} - p^{k - 1} = p^{k} (1 - \frac{1}{p})

Ponieważ $φ (n)$ jest funkcją multiplikatywną, to dla $n = p_{1}^{α_{1}} \cdot \dots \cdot p_{s}^{α_{s}}$ otrzymujemy

φ (n) = \prod_{k = 1}^{s} φ (p_{k}^{α_{k}})

= \prod_{k = 1}^{s} p_{k}^{α_{k}} (1 - \frac{1}{p_{k}})

= [\prod_{k = 1}^{s} p_{k}^{α_{k}}] \cdot [\prod_{k = 1}^{s} (1 - \frac{1}{p_{k}})]

= n \cdot \prod_{k = 1}^{s} (1 - \frac{1}{p_{k}})

= n \cdot \prod_{p | n} (1 - \frac{1}{p})

Co należało pokazać.
□

Twierdzenie H34
Niech $n \in Z_{+}$ . Jeżeli $q$ jest liczbą pierwszą, to

φ (q n) = {\begin{aligned} (q - 1) φ (n) & gdy q ∤ n \\ q φ (n) & gdy q ∣ n \end{aligned}

Dowód

Jeżeli $q ∤ m$ , to $gcd (q, m) = 1$ , zatem $φ (q m) = φ (q) φ (m) = (q - 1) φ (m)$ . Jeżeli $q ∣ m$ , to liczby $m$ oraz $q m$ mają taki sam zbiór dzielników pierwszych, zatem

φ (q m) = q m \prod_{p ∣ q m} (1 - \frac{1}{p}) = q \cdot [m \prod_{p ∣ m} (1 - \frac{1}{p})] = q φ (m)

Co należało pokazać.
□

Zadanie H35
Niech $q \in P$ i $a, b, m, n \in Z_{+}$ . Pokazać, że

$φ (q^{a + b}) = q^{a} φ (q^{b})$

$φ (n^{m}) = n^{m - 1} φ (n)$

Rozwiązanie

Punkt 1.

φ (q^{a + b}) = (q - 1) q^{a + b - 1} = q^{a} \cdot (q - 1) q^{b - 1} = q^{a} φ (q^{b})

Punkt 2.

Niech $n = p_{1}^{α_{1}} \cdot \dots \cdot p_{s}^{α_{s}}$

φ (n^{m}) = φ (p_{1}^{m α_{1}} \cdot \dots \cdot p_{s}^{m α_{s}})

= φ (p_{1}^{m α_{1}}) \cdot \dots \cdot φ (p_{s}^{m α_{s}})

= φ (p_{1}^{(m - 1) α_{1} + α_{1}}) \cdot \dots \cdot φ (p_{s}^{(m - 1) α_{s} + α_{s}})

= p_{1}^{(m - 1) α_{1}} φ (p_{1}^{α_{1}}) \cdot \dots \cdot p_{s}^{(m - 1) α_{s}} φ (p_{s}^{α_{s}})

= p_{1}^{(m - 1) α_{1}} \cdot \dots \cdot p_{s}^{(m - 1) α_{s}} \cdot φ (p_{1}^{α_{1}} \cdot \dots \cdot p_{s}^{α_{s}})

= n^{m - 1} φ (n)

Co należało pokazać.
□

Twierdzenie H36
Niech $m, n \in Z_{+}$ . Jeżeli $m ∣ n$ , to $φ (m) ∣ φ (n)$ .

Dowód

Niech $n = p_{1}^{α_{1}} \cdot \dots \cdot p_{s}^{α_{s}}$ . Ponieważ założyliśmy, że $m ∣ n$ , to $m$ musi być postaci $m = p_{1}^{β_{1}} \cdot \dots \cdot p_{s}^{β_{s}}$ , gdzie $0 ⩽ β_{i} ⩽ α_{i}$ , dla $i = 1, \dots, s$ . Łatwo zauważamy, że

jeżeli $β_{i} = 0$ , to $φ (p_{i}^{β_{i}}) = 1$ i dzieli $φ (p_{i}^{α_{i}})$

jeżeli $1 ⩽ β_{i} ⩽ α_{i}$ , to $(p_{i} - 1) p_{i}^{β_{i} - 1} ∣ (p_{i} - 1) p_{i}^{α_{i} - 1}$ , zatem $φ (p_{i}^{β_{i}}) ∣ φ (p_{i}^{α_{i}})$

Skąd natychmiast wynika, że $φ (p_{1}^{β_{1}}) \cdot \dots \cdot φ (p_{s}^{β_{s}})$ dzieli $φ (p_{1}^{α_{1}}) \cdot \dots \cdot φ (p_{s}^{α_{s}})$ , czyli $φ (m) ∣ φ (n)$ .

Zauważmy, że twierdzenie odwrotne nie jest prawdziwe, bo $φ (7) ∣ φ (19)$ , ale $7 ∤ 19$ .
□

Zadanie H37
Dla $n ⩾ 3$ wartości $φ (n)$ są liczbami parzystymi.

Rozwiązanie

Jeżeli liczba $n ⩾ 3$ jest podzielna przez liczbę pierwszą nieparzystą $p$ , zaś $k$ jest wykładnikiem, z jakim $p$ wchodzi do rozwinięcia $n$ na czynniki pierwsze, to

φ (n) = φ (p^{k} \cdot \frac{n}{p^{k}}) = (p - 1) p^{k - 1} \cdot φ (\frac{n}{p^{k}})

zatem $φ (n)$ jest liczbą parzystą, ponieważ $p - 1$ jest liczbą parzystą.

Jeżeli żadna liczba nieparzysta nie dzieli $n$ , to liczba $n$ jest postaci $n = 2^{a}$ i $φ (n) = 2^{a - 1}$ , ale z założenia $n ⩾ 3$ , zatem $a ⩾ 2$ i $φ (n)$ jest liczbą parzystą.
□

Twierdzenie H38
Jeżeli $n$ jest liczbą złożoną, to $φ (n) ⩽ n - \sqrt{n}$ .

Dowód

Pierwszy sposób
Niech $n = a b$ , gdzie $1 < a ⩽ b < n$ . Liczby $1 \cdot a, 2 \cdot a, 3 \cdot a, \dots, b \cdot a$ są nie większe od $n$ i nie są względnie pierwsze z $n$ , zatem

φ (n) ⩽ n - b

Ponieważ $b ⩾ a$ , to $b^{2} ⩾ a b = n$ i $b ⩾ \sqrt{n}$ . Wynika stąd, że

φ (n) ⩽ n - b ⩽ n - \sqrt{n}

Drugi sposób
Niech $q$ oznacza najmniejszy dzielnik pierwszy liczby złożonej $n$ , zatem $q^{2} ⩽ n$ , czyli $q ⩽ \sqrt{n}$ , a stąd $\frac{n}{q} ⩾ \sqrt{n}$ i

φ (n) = n \cdot \prod_{p | n} (1 - \frac{1}{p}) ⩽ n (1 - \frac{1}{q}) = n - \frac{n}{q} ⩽ n - \sqrt{n}

Co należało pokazać.
□

Twierdzenie H39
Dla $n ⩾ 1$ prawdziwe jest oszacowanie $φ (n) > \frac{\sqrt{n}}{2}$ .

Dowód

Dla $k ⩾ 3$ jest

{(1 - \frac{1}{k})}^{2} > \frac{1}{k}

Wynika stąd, że jeżeli $m ⩾ 3$ jest liczbą nieparzystą, to

φ (m)^{2} = m^{2} \prod_{p | m} {(1 - \frac{1}{p})}^{2} > m^{2} \prod_{p | m} \frac{1}{p} ⩾ m

bo

\prod_{p | m} p ⩽ m

Czyli dla nieparzystych liczb $m ⩾ 3$ mamy

φ (m) > \sqrt{m} > \frac{\sqrt{m}}{2}

Jeżeli $d = 2^{a}$ , gdzie $a ⩾ 1$ , to

φ (d) = φ (2^{a}) = 2^{a - 1} > \frac{\sqrt{2^{a}}}{2} = \frac{\sqrt{d}}{2}

W przypadku ogólnym, gdy $n$ jest iloczynem liczby nieparzystej $m ⩾ 3$ i potęgi liczby $2$ , dostajemy

φ (n) = φ (2^{a} m) = φ (2^{a}) φ (m) > \frac{\sqrt{2^{a}}}{2} \cdot \sqrt{m} = \frac{\sqrt{2^{a} m}}{2} = \frac{\sqrt{n}}{2}

Oczywiście nierówność $φ (n) > \frac{\sqrt{n}}{2}$ jest również prawdziwa dla $n = 1$ . Co należało pokazać.
□

Zadanie H40
Pokazać, że dla $n ⩾ 7$ prawdziwe jest oszacowanie $φ (n) > \sqrt{n}$ .

Rozwiązanie

Zauważmy, że

n - 1 > \sqrt{n} dla n ⩾ 3

n - 1 > \sqrt{2 n} dla n ⩾ 4

Zatem dla liczby pierwszej $p$ i $k ⩾ 1$ jest

φ (p^{k}) = (p - 1) p^{k - 1} > \sqrt{p} \cdot p^{k - 1} = p^{k - \frac{1}{2}} ⩾ p^{\frac{k}{2}} = \sqrt{p^{k}} dla p ⩾ 3

φ (p^{k}) = (p - 1) p^{k - 1} > \sqrt{2 p} \cdot p^{k - 1} = \sqrt{2} \cdot p^{k - \frac{1}{2}} ⩾ \sqrt{2} \cdot p^{\frac{k}{2}} = \sqrt{2 p^{k}} dla p ⩾ 5

1. Przypadek, gdy $n ⩾ 3$ jest liczbą nieparzystą

Liczba $n$ jest iloczynem czynników pierwszych nieparzystych, zatem

φ (n) = φ (p_{1}^{α_{1}} \cdot \dots \cdot p_{s}^{α_{s}}) = φ (p_{1}^{α_{1}}) \cdot \dots \cdot φ (p_{s}^{α_{s}}) > \sqrt{p_{1}^{α_{1}}} \cdot \dots \cdot \sqrt{p_{s}^{α_{s}}} = \sqrt{n}

2. Przypadek, gdy $n = 2^{a} m$ i $q ∣ m,$ gdzie $q ⩾ 5$

Z założenia $n = 2^{a} m = 2^{a} q^{b} r$ , gdzie $r ⩾ 1$ jest liczbą nieparzystą. Zauważmy, że $φ (r) ⩾ \sqrt{r}$ , bo może być $r = 1$ .

φ (n) = φ (2^{a} q^{b} r)

= φ (2^{a}) φ (q^{b}) φ (r)

> 2^{a - 1} \sqrt{2 q^{b}} \sqrt{r}

= 2^{a - \frac{1}{2}} \sqrt{q^{b}} \sqrt{r}

⩾ 2^{\frac{a}{2}} \sqrt{q^{b} r}

= \sqrt{2^{a} q^{b} r}

= \sqrt{n}

3. Przypadek, gdy $n = 2^{a} m$ i $q ∤ m,$ gdzie $q ⩾ 5$

Jeżeli żadna liczba pierwsza $q ⩾ 5$ nie dzieli $m$ , to możliwe są tylko dwie sytuacje: $n = 2^{a}$ i $n = 2^{a} 3^{b}$ .

3a. Przypadek, gdy $n = 2^{a}$

φ (n) = φ (2^{a}) = 2^{a - 1} > \sqrt{2^{a}} = \sqrt{n} dla a ⩾ 3

Twierdzenie nie jest prawdziwe dla $n = 2$ i $n = 4$ (gdy $a = 1$ lub $a = 2$ ).

3b. Przypadek, gdy $n = 2^{a} 3^{b}$

φ (n) = φ (2^{a} 3^{b}) = φ (2^{a}) φ (3^{b}) = 2^{a - 1} \cdot 2 \cdot 3^{b - 1} = 2^{a} 3^{b - 1} = \sqrt{2^{a} 3^{b}} \cdot \frac{\sqrt{2^{a} 3^{b}}}{3} > \sqrt{2^{a} 3^{b}}

Ostatnia nierówność jest prawdziwa, o ile $\sqrt{2^{a} 3^{b}} > 3$ , czyli gdy $2^{a} 3^{b} > 9$ , co ma miejsce, gdy $a ⩾ 2$ lub $b ⩾ 2$ .

Twierdzenie nie jest prawdziwe dla $n = 6$ (gdy $a = 1$ i $b = 1$ ).

Zbierając uzyskane wyniki, otrzymujemy: oszacowanie $φ (n) > \sqrt{n}$ nie jest prawdziwe dla $n = 1, 2, 4, 6$ . Co należało pokazać.
□

Zadanie H41
Pokazać, że dla $n ⩾ 2$ prawdziwe jest oszacowanie $φ (n) > \frac{n}{3 \log n}$ . Korzystając z tego wyniku, pokazać, że $φ (n) > n^{2 / 3}$ dla $n ⩾ 43$ oraz że $φ (n) > n^{3 / 4}$ dla $n ⩾ 211$ .

Rozwiązanie

Niech $n = q_{1}^{α_{1}} \cdot \dots \cdot q_{s}^{α_{s}}$ , a $n^{'} = q_{1} \cdot \dots \cdot q_{s}$ oznacza liczbę, będącą iloczynem dokładnie tych samych czynników pierwszych, jakie występują w liczbie $n$ , natomiast $n^{*} = p_{1} \cdot \dots \cdot p_{s}$ oznacza liczbę, będącą iloczynem dokładnie tej samej ilości czynników pierwszych, przy czym $p_{i}$ oznacza teraz $i$ -tą liczbę pierwszą.

Ponieważ

\frac{φ (n)}{n} = \prod_{p ∣ n} (1 - \frac{1}{p})

to

\frac{φ (n)}{n} = \frac{φ (n^{'})}{n^{'}} ⩾ \frac{φ (n^{*})}{n^{*}} = \prod_{i = 1}^{s} (1 - \frac{1}{p_{i}}) ⩾ \prod_{k = 2}^{p_{s}} (1 - \frac{1}{k}) = \frac{1}{p_{s}}

Ostatnia równość wynika z prostego wzoru

\prod_{k = 2}^{m} (1 - \frac{1}{k}) = \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{3}{4} \cdot \dots \cdot \frac{m - 2}{m - 1} \cdot \frac{m - 1}{m} = \frac{1}{m}

Musimy oszacować wartość liczby $p_{s}$ . Z twierdzenia B31 wynika, że dla $m ⩾ 2$ jest $P (m) ⩾ 2^{m / 2}$ , gdzie funkcja $P (m)$ jest równa iloczynowi wszystkich liczb pierwszych nie większych od $m$ . Zatem dla $p_{s} ⩾ 2$ jest

n^{*} = p_{1} \cdot \dots \cdot p_{s} = P (p_{s}) ⩾ 2^{p_{s} / 2}

Logarytmując, otrzymujemy

p_{s} ⩽ \frac{2 \log n^{*}}{\log 2}

Ponieważ $n ⩾ n^{'} ⩾ n^{*}$ , to

\frac{φ (n)}{n} ⩾ \frac{1}{p_{s}} ⩾ \frac{\log 2}{2 \log n^{*}} ⩾ \frac{\log 2}{2 \log n} > \frac{1}{3 \log n}

Ostatecznie otrzymujemy

φ (n) > \frac{n}{3 \log n}

Co należało pokazać.

Rozwiązując drugą część zadania, wystarczy znaleźć, dla jakich $n$ prawdziwa jest nierówność

\frac{n}{3 \log n} > n^{2 / 3}

Przebieg funkcji $\frac{n}{3 \log n}$ i $n^{2 / 3}$ przedstawiliśmy na wykresie

Punkt przecięcia tych funkcji znajdujemy, wpisując w PARI/GP polecenie

solve(n = 10, 10^5, n/(3*log(n)) - n^(2/3))

Otrzymujemy

n = 29409.965

Zatem $\frac{n}{3 \log n} > n^{2 / 3}$ dla $n > 2.95 \cdot 10^{4}$ .

Poleceniem

for(n = 1, 3*10^4, if( eulerphi(n) <= n^(2/3), print(n) ))

sprawdzamy, że oszacowanie $φ (n) > n^{2 / 3}$ jest prawdziwe dla $n ⩾ 43$ .

Postępując analogicznie jak wyżej, znajdujemy, dla jakich $n$ prawdziwa jest nierówność

\frac{n}{3 \log n} > n^{3 / 4}

Wpisując w PARI/GP polecenie

solve(n = 10, 10^7, n/(3*log(n)) - n^(3/4))

otrzymujemy

n = 4447862.680

Zatem $\frac{n}{3 \log n} > n^{3 / 4}$ dla $n > 4.45 \cdot 10^{6}$

Poleceniem

for(n = 1, 5*10^6, if( eulerphi(n) <= n^(3/4), print(n) ))

sprawdzamy, że oszacowanie $φ (n) > n^{3 / 4}$ jest prawdziwe dla $n ⩾ 211$ . Co należało pokazać.
□

Twierdzenie H42
Niech $n \in Z_{+}$ . Liczba $n$ jest liczbą pierwszą wtedy i tylko wtedy, gdy $φ (n) = n - 1$ .

Dowód

Dla liczb złożonych $n ⩾ 4$ nigdy nie będzie $φ (n) = n - 1$ , bo

φ (n) ⩽ n - \sqrt{n} ⩽ n - 2

Dla $n = 1, 2, 3$ sprawdzamy bezpośrednio: $φ (1) = 1 \neq 1 - 1$ , $φ (2) = 1 = 2 - 1$ , $φ (3) = 2 = 3 - 1$ . Co kończy dowód.
□

Twierdzenie H43
Dla dowolnej liczby całkowitej dodatniej $n$ jest

n = \sum_{d ∣ n} φ (d) = \sum_{d ∣ n} φ (\frac{n}{d})

gdzie sumowanie przebiega po wszystkich dzielnikach dodatnich liczby $n$ .

Dowód

Ponieważ $φ (n)$ jest funkcją multiplikatywną, to funkcja

F (n) = \sum_{d ∣ n} φ (d)

też jest funkcją multiplikatywną (zobacz H30). Łatwo sprawdzamy, że twierdzenie jest prawdziwe dla $n = 1$ . Niech $n > 1$ . Jeżeli $n = p^{α}$ jest potęgą liczby pierwszej, to otrzymujemy

F (p^{α}) = \sum_{d ∣ p^{α}} φ (d)

= φ (1) + φ (p) + φ (p^{2}) + \dots + φ (p^{α}) =

= 1 + (p - 1) + p (p - 1) + \dots + p^{α - 1} (p - 1) =

= 1 + (p - 1) + (p^{2} - p) + \dots + (p^{α} - p^{α - 1})

= p^{α}

Jeżeli $n$ jest postaci $n = p_{1}^{α_{1}} \cdot \dots \cdot p_{s}^{α_{s}}$ , to

F (n) = F (p_{1}^{α_{1}} \cdot \dots \cdot p_{s}^{α_{s}}) =

= F (p_{1}^{α_{1}}) \cdot \dots \cdot F (p_{s}^{α_{s}}) =

= p_{1}^{α_{1}} \cdot \dots \cdot p_{s}^{α_{s}}

= n

Niech $1 < d_{1} < d_{2} < \dots < n$ będą dzielnikami liczby $n$ . Zauważmy, że kiedy $d$ przebiega zbiór dzielników ${1, d_{1}, d_{2}, \dots, n}$ , to $e = \frac{n}{d}$ przebiega wszystkie te liczby tylko w odwrotnej kolejności. Zatem

\sum_{d ∣ n} φ (d) = \sum_{d ∣ n} φ (\frac{n}{d})

Co należało pokazać.
□

Zadanie H44
Niech $n ⩾ 2$ . Pokazać, że suma liczb całkowitych dodatnich nie większych od $n$ i względnie pierwszych z $n$ jest równa $\frac{1}{2} n φ (n)$ .

Rozwiązanie

Łatwo sprawdzamy, że wzór jest prawdziwy dla $n = 2$ i odtąd będziemy przyjmowali, że $n ⩾ 3$ . Zatem wartości $φ (n)$ są liczbami parzystymi i niech $c = \frac{1}{2} φ (n)$ . Zauważmy, że jeżeli liczba $a$ jest względnie pierwsza z $n$ , to liczba $n - a$ jest również względnie pierwsza z $n$ , bo $gcd (a, n) = gcd (n - a, n)$ . Wypiszmy wszystkie liczby całkowite dodatnie nie większe od $n$ i względnie pierwsze z $n$ w kolejności rosnącej, a pod spodem w kolejności malejącej

$1$	$a_{2}$	$\dots$	$a_{c}$	$n - a_{c}$	$\dots$	$n - a_{2}$	$n - 1$
$n - 1$	$n - a_{2}$	$\dots$	$n - a_{c}$	$a_{c}$	$\dots$	$a_{2}$	$1$

Suma liczb w każdej kolumnie jest równa $n$ . Ponieważ ilość liczb względnie pierwszych z $n$ jest równa $φ (n)$ , to podwojona suma liczb całkowitych nie większych od $n$ i pierwszych względem $n$ wynosi $n φ (n)$ . Co należało pokazać.
□

Zadanie H45
Pokazać, że dla liczb naturalnych nieparzystych $n ⩾ 5$ prawdziwe jest oszacowanie $φ (n) > π (n)$ .

Rozwiązanie

1. Jeżeli $n ⩾ 5$ jest liczbą pierwszą, to liczbami pierwszymi względem $n$ są wszystkie liczby pierwsze mniejsze od $n$ oraz liczby $1, 4$ . Zatem

φ (n) ⩾ π (n) - 1 + 2 > π (n)

.

2. Jeżeli $n = p^{a}$ , gdzie $a ⩾ 2$ , jest potęgą liczby pierwszej nieparzystej, to $n ⩾ 9$ i liczbami pierwszymi względem $n$ są wszystkie liczby pierwsze nie większe od $n$ (oprócz liczby $p$ ) oraz liczby $1, 4, 8$ . Zatem

φ (n) ⩾ π (n) - 1 + 3 > π (n)

.

3. Jeżeli $n$ ma więcej niż jeden dzielnik pierwszy nieparzysty, to $n = q_{1}^{α_{1}} \cdot \dots \cdot q_{s}^{α_{s}}$ , gdzie $s ⩾ 2$ . Zauważmy, że

n = q_{1}^{α_{1}} \cdot \dots \cdot q_{s}^{α_{s}} ⩾ q_{1} \cdot \dots \cdot q_{s} ⩾ 3 \cdot 5^{s - 1} > 2^{2 s - 1}

Liczbami pierwszymi względem $n$ są wszystkie liczby pierwsze nie większe od $n$ (oprócz liczb $q_{1}, \dots, q_{s}$ ) oraz liczby $1, 2^{2}, 2^{3}, \dots, 2^{2 s - 1}$ . Zatem

φ (n) ⩾ π (n) - s + 2 s - 1 = π (n) + s - 1 > π (n)

Co należało pokazać.
□

Zadanie H46
Pokazać, że dla liczb naturalnych $n ⩾ 91$ prawdziwe jest oszacowanie $φ (n) > π (n)$ .

Rozwiązanie

Ponieważ $p_{2 s} > 1$ i $p_{2 s} ⩾ p_{s + 1}$ , to z zadania A40 natychmiast wynika nierówność

p_{1} p_{2} \cdot \dots \cdot p_{s} > p_{s + 1} p_{2 s}

która jest prawdziwa dla $n ⩾ 4$ .

Pokażemy najpierw, że dla każdej liczby naturalnej mającej nie mniej niż cztery dzielniki pierwsze nierówność $φ (n) > π (n)$ jest zawsze prawdziwa.

Przez $p_{1}, p_{2}, \dots, p_{k}, \dots$ oznaczymy kolejne liczby pierwsze. Niech $n ⩾ 2$ będzie liczbą naturalną i $n = q_{1}^{α_{1}} \cdot \dots \cdot q_{s}^{α_{s}}$ , gdzie $q_{i}$ oznaczają dowolne (nie muszą być kolejne) liczby pierwsze.

Wśród kolejnych $2 s$ liczb pierwszych znajduje się przynajmniej $s$ liczb pierwszych różnych od każdej z liczb $q_{1}, \dots, q_{s}$ . Jeśli oznaczymy te liczby (w rosnącej kolejności) przez $r_{1}, \dots, r_{s}$ , to łatwo zauważymy, że prawdziwe są dla nich następujące oszacowania

dla najmniejszej liczby $r_{1} ⩽ p_{s + 1}$

dla wszystkich liczb $r_{j} ⩽ p_{2 s}$ dla $j = 1, \dots, s$ .

Korzystając z wypisanej na początku dowodu nierówności, dla $s ⩾ 4$ mamy

n = q_{1}^{α_{1}} \cdot \dots \cdot q_{s}^{α_{s}} ⩾ q_{1} \cdot \dots \cdot q_{s} ⩾ p_{1} \cdot \dots \cdot p_{s} > p_{s + 1} p_{2 s} ⩾ r_{1} \cdot r_{j}

gdzie $j = 1, \dots, s$ .

Wynika stąd, że jeśli $s ⩾ 4$ , to liczbami pierwszymi względem $n$ są wszystkie liczby pierwsze nie większe od $n$ (oprócz liczb pierwszych $q_{1}, \dots, q_{s}$ ) oraz liczby $1$ i $r_{1} r_{j}$ , gdzie $j = 1, \dots, s$ . Zatem

φ (n) ⩾ π (n) - s + s + 1 > π (n)

Co mieliśmy pokazać.

Uwzględniając rezultat pokazany w zadaniu H45, pozostaje sprawdzić przypadki gdy $n = 2^{a}$ , $n = 2^{a} p^{b}$ , $n = 2^{a} p^{b} q^{c}$ , gdzie $a, b, c \in Z_{+}$ .

1. Niech $n = 2^{a}$ . Jeśli $n ⩾ 16$ , to liczbami pierwszymi względem $n$ są wszystkie liczby pierwsze nie większe od $n$ (oprócz liczby $2$ ) oraz liczby $1, 9, 15$ . Zatem

φ (n) ⩾ π (n) - 1 + 3 > π (n)

2. Niech $n = 2^{a} p^{b}$ , zaś $r$ będzie najmniejszą liczbą pierwszą nieparzystą różną od $p$ . Oczywiście $r \in {3, 5}$ i jeśli tylko $n > 5^{3} = 125$ , to liczbami pierwszymi względem $n$ są wszystkie liczby pierwsze nie większe od $n$ (oprócz liczb pierwszych $2$ i $p$ ) oraz liczby $1, r^{2}, r^{3}$ . Zatem

φ (n) ⩾ π (n) - 2 + 3 > π (n)

3. Niech $n = 2^{a} p^{b} q^{c}$ , zaś $r$ będzie najmniejszą liczbą pierwszą nieparzystą różną od $p$ oraz różną od $q$ . Oczywiście $r \in {3, 5, 7}$ i jeśli $n > 7^{4} = 2401$ , to liczbami pierwszymi względem $n$ są wszystkie liczby pierwsze nie większe od $n$ (oprócz liczb pierwszych $2$ , $p$ i $q$ ) oraz liczby $1, r^{2}, r^{3}, r^{4}$ . Zatem

φ (n) ⩾ π (n) - 3 + 4 > π (n)

Zbierając: pozostaje sprawdzić bezpośrednio przypadki, gdy $n$ jest liczbą parzystą i $n ⩽ 2401$ . W GP/PARI wystarczy napisać polecenie

for(n = 1, 2500, if( eulerphi(n) <= primepi(n), print(n) ))

Nierówność $φ (n) > π (n)$ nie jest prawdziwa dla $n \in {2, 3, 4, 6, 8, 10, 12, 14, 18, 20, 24, 30, 42, 60, 90}$ . Co kończy dowód.
□

Zadanie H47
Pokazać, że $φ (n) = 2^{a}$ wtedy i tylko wtedy, gdy $n = 2^{b} q_{1} \cdot \dots \cdot q_{s}$ , gdzie $q_{1}, \dots, q_{s}$ są liczbami pierwszymi Fermata: $3, 5, 17, 257, 65537$ .

Rozwiązanie

W przypadku, gdy $2 ∣ n$ , łatwo zauważamy, że liczba $2$ może występować w dowolnej potędze, bo $φ (2^{b}) = 2^{b - 1}$ .

W przypadku, gdy $p ∣ n$ , gdzie $p$ jest liczbą pierwszą nieparzystą, mamy $φ (p^{k}) = (p - 1) p^{k - 1}$ i równie łatwo zauważmy, że musi być $k = 1$ , a liczba $p - 1$ musi być potęgą liczby $2$ . Zatem liczba pierwsza $p$ musi być postaci $p = 2^{t} + 1$ , co jest możliwe tylko wtedy, gdy $t$ jest potęgą liczby $2$ (zobacz H48), czyli $p$ musi być liczbą pierwszą Fermata. Co należało pokazać.
□

Uzupełnienie

Twierdzenie H48
Niech $a, n \in Z_{+}$ i $a ⩾ 2$ . Jeżeli liczba $a^{n} + 1$ jest liczbą pierwszą, to $a$ jest liczbą parzystą i $n = 2^{m}$ .

Dowód

Gdyby liczba $a$ była nieparzysta, to liczba $a^{n} + 1 ⩾ 4$ byłaby parzysta i nie mogłaby być liczbą pierwszą.

Niech wykładnik $n = x y$ będzie liczbą złożoną, a $x$ będzie liczbą nieparzystą. Wtedy

a^{n} + 1 = (a^{y})^{x} + 1

Oznaczając $b = a^{y}$ oraz $x = 2 k + 1$ , otrzymujemy

a^{n} + 1 = (a^{y})^{x} + 1 = b^{x} + 1 = b^{2 k + 1} + 1 = (b + 1) \cdot (1 - b + b^{2} - b^{3} + \dots + b^{2 k - 2} - b^{2 k - 1} + b^{2 k})

Zatem w takim przypadku $a^{n} + 1$ jest liczbą złożoną. Wynika stąd, że wykładnik $n$ nie może zawierać czynników nieparzystych, czyli musi być $n = 2^{m}$ . Co należało pokazać.
□

Przypisy

↑ Wikipedia, Największy wspólny dzielnik, (Wiki-pl), (Wiki-en)
↑ Wikipedia, Moc zbioru, (Wiki-pl), (Wiki-en)
↑ Wikipedia, Zasada włączeń i wyłączeń, (Wiki-pl), (Wiki-en)
↑ Wikipedia, Funkcja φ, (Wiki-pl), (Wiki-en)

[GCD1-1] Wikipedia, Największy wspólny dzielnik, (Wiki-pl), (Wiki-en)

[cardinality1-2] Wikipedia, Moc zbioru, (Wiki-pl), (Wiki-en)

[sumazbiorow-3] Wikipedia, Zasada włączeń i wyłączeń, (Wiki-pl), (Wiki-en)

[Euler1-4] Wikipedia, Funkcja φ, (Wiki-pl), (Wiki-en)

[1]

[2]

[3]

[4]

Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera

Spis treści