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

Z Henryk Dąbrowski
Przejdź do nawigacji Przejdź do wyszukiwania
22.12.2023



Największy wspólny dzielnik

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

  1.   [math]\displaystyle{ D \mid a \quad \text{i} \quad D \mid b }[/math]
  2.   [math]\displaystyle{ \,\, d \mid a \quad \text{i} \quad \; d \mid b \qquad \Longrightarrow \qquad d \leqslant D }[/math]

gdzie [math]\displaystyle{ d }[/math] jest dowolną liczbą całkowitą.


Uwaga H2
Tak zdefiniowaną liczbę [math]\displaystyle{ D }[/math] będziemy oznaczali przez [math]\displaystyle{ \gcd (a, b) }[/math]. Ponieważ [math]\displaystyle{ 1 \mid a \; }[/math] i [math]\displaystyle{ \; 1 \mid b }[/math] to, z definicji wynika natychmiast, że [math]\displaystyle{ \gcd (a, b) \geqslant 1 }[/math]. Zauważmy też, że jeżeli [math]\displaystyle{ d \mid a \; }[/math] i [math]\displaystyle{ \; d \mid b }[/math], to [math]\displaystyle{ d \mid \gcd (a, b) }[/math]. Co natychmiast wynika z lematu Bézouta (zobacz C73).


Twierdzenie H3
Jeżeli liczby całkowite [math]\displaystyle{ a, b }[/math] nie są jednocześnie równe zero i [math]\displaystyle{ \gcd (a, b) = a x + b y }[/math], to [math]\displaystyle{ \gcd (x, y) = 1 }[/math].

Dowód


Twierdzenie H4
Niech [math]\displaystyle{ a, b, k \in \mathbb{Z} }[/math]. Prawdziwy jest wzór

[math]\displaystyle{ \gcd (a + k b, b) = \gcd (a, b) }[/math]
Dowód


Twierdzenie H5
Niech [math]\displaystyle{ a, b, m \in \mathbb{Z} }[/math]. Prawdziwa jest następująca równoważność

[math]\displaystyle{ \gcd (a, m) = 1 \quad \text{i} \quad \gcd (b, m) = 1 \quad \qquad \Longleftrightarrow \quad \qquad \gcd (a b, m) = 1 }[/math]
Dowód


Twierdzenie H6
Dla [math]\displaystyle{ a, b, m \in \mathbb{Z} }[/math] jest

[math]\displaystyle{ \gcd (a b, m) \mid \gcd (a, m) \cdot \gcd (b, m) }[/math]
Dowód


Twierdzenie H7
Jeżeli liczby [math]\displaystyle{ a, b }[/math] są względnie pierwsze, to

[math]\displaystyle{ \gcd (a b, m) = \gcd (a, m) \cdot \gcd (b, m) }[/math]
Dowód


Twierdzenie H8
Jeżeli [math]\displaystyle{ a, m, n \in \mathbb{Z}_+ }[/math], to

[math]\displaystyle{ \gcd (a^m - 1, a^n - 1) = a^{\gcd (m, n)} - 1 }[/math]
Dowód


Uwaga H9
W dowodzie twierdzenia H8 pominęliśmy milczeniem fakt, że jedna z liczb [math]\displaystyle{ x, y }[/math] może być (i często jest) ujemna. Choć rezultat jest prawidłowy, to nie wiemy, co oznacza zapis

[math]\displaystyle{ a^{- 1000} \equiv 1^{- 10} \equiv 1 \!\! \pmod{d} }[/math]

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

[math]\displaystyle{ a^m \equiv 1 \!\! \pmod{d} \quad \qquad \text{oraz} \quad \qquad a^n \equiv 1 \!\! \pmod{d} }[/math]

wynika, że [math]\displaystyle{ \gcd (a, d) = 1 }[/math] i liczba [math]\displaystyle{ a }[/math] ma element odwrotny modulo [math]\displaystyle{ d }[/math].



Element odwrotny modulo [math]\displaystyle{ m }[/math]

Twierdzenie H10
Niech [math]\displaystyle{ m \in \mathbb{Z}_+ }[/math]. Dla liczby [math]\displaystyle{ a \in \mathbb{Z} }[/math] istnieje taka liczba [math]\displaystyle{ x }[/math], że

[math]\displaystyle{ a x \equiv 1 \!\! \pmod{m} }[/math]

wtedy i tylko wtedy, gdy [math]\displaystyle{ \gcd (a, m) = 1 }[/math].

Dowód


Definicja H11
Niech [math]\displaystyle{ m \in \mathbb{Z}_+ }[/math]. Liczbę [math]\displaystyle{ x }[/math] taką, że

[math]\displaystyle{ a \cdot x \equiv 1 \!\! \pmod{m} }[/math]

będziemy nazywali elementem odwrotnym liczby [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ m }[/math] i oznaczali jako [math]\displaystyle{ a^{- 1} }[/math].


Uwaga H12
Oznaczenie elementu odwrotnego ma naturalne uzasadnienie. Zauważmy, że jeżeli [math]\displaystyle{ b \mid a }[/math] oraz [math]\displaystyle{ b }[/math] ma element odwrotny modulo [math]\displaystyle{ m }[/math], to prawdziwa jest kongruencja

[math]\displaystyle{ {\small\frac{a}{b}} \equiv a b^{- 1} \!\! \pmod{m} }[/math]

Istotnie

[math]\displaystyle{ {\small\frac{a}{b}} = {\small\frac{a}{b}} \cdot 1 \equiv {\small\frac{a}{b}} \cdot b b^{- 1} \equiv a b^{- 1} \!\! \pmod{m} }[/math]

W PARI/GP odwrotność liczby [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ m }[/math] znajdujemy, wpisując Mod(a, m)^(-1).


Twierdzenie H13
Niech [math]\displaystyle{ a, k \in \mathbb{Z} }[/math], [math]\displaystyle{ m \in \mathbb{Z}_+ }[/math]. Poniższa tabelka przedstawia elementy odwrotne do elementu [math]\displaystyle{ a }[/math] w przypadku niektórych modułów [math]\displaystyle{ m }[/math]. W szczególności, jeżeli moduł [math]\displaystyle{ m }[/math] jest liczbą nieparzystą, to [math]\displaystyle{ 2^{- 1} \equiv {\small\frac{m + 1}{2}} \!\! \pmod{m} }[/math].

Dowód


Twierdzenie H14
Niech [math]\displaystyle{ a, b \in \mathbb{Z} }[/math], [math]\displaystyle{ m \in \mathbb{Z}_+ }[/math] i liczba [math]\displaystyle{ a }[/math] ma element odwrotny modulo [math]\displaystyle{ m }[/math]. Jeżeli liczby [math]\displaystyle{ u_1, u_2, \ldots, u_r }[/math] są liczbami różnymi modulo [math]\displaystyle{ m }[/math], to liczby

1.   [math]\displaystyle{ a u_1, a u_2, \ldots, a u_r }[/math]
2.   [math]\displaystyle{ a u_1 + b, a u_2 + b, \ldots, a u_r + b }[/math]

są liczbami różnymi modulo [math]\displaystyle{ m }[/math]. Jeżeli ponadto liczby [math]\displaystyle{ u_1, u_2, \ldots, u_r }[/math] są względnie pierwsze z [math]\displaystyle{ m }[/math], to również liczby

3.   [math]\displaystyle{ u^{- 1}_1, u^{- 1}_2, \ldots, u^{- 1}_r }[/math]

są liczbami różnymi modulo [math]\displaystyle{ m }[/math].

Dowód


Zadanie H15
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą. Pokazać, że dla [math]\displaystyle{ k \in [0, p - 1] }[/math] prawdziwa jest kongruencja

[math]\displaystyle{ \binom{p - 1}{k} \equiv (- 1)^k \pmod{p} }[/math]
Rozwiązanie


Twierdzenie H16
Niech [math]\displaystyle{ A }[/math] i [math]\displaystyle{ B }[/math] będą zbiorami skończonymi. Pokazać, że jeżeli [math]\displaystyle{ A \subseteq B \;\; \text{i} \;\; | A | = | B | }[/math], to [math]\displaystyle{ \; A = B }[/math].

Dowód


Definicja H17
Niech elementy każdego ze zbiorów [math]\displaystyle{ A = \{ a_1, a_2, \ldots, a_r \} }[/math] oraz [math]\displaystyle{ B = \{ b_1, b_2, \ldots, b_r \} }[/math] będą różne modulo [math]\displaystyle{ m }[/math]. Powiemy, że zbiory [math]\displaystyle{ A, B }[/math] są równe modulo [math]\displaystyle{ m }[/math], jeżeli dla każdego [math]\displaystyle{ k = 1, \ldots, r }[/math] istnieje takie [math]\displaystyle{ j = 1, \ldots, r }[/math], że prawdziwa jest kongruencja [math]\displaystyle{ a_k \equiv b_j \!\! \pmod{m} }[/math].


Twierdzenie H18
Niech elementy każdego ze zbiorów [math]\displaystyle{ A = \{ a_1, a_2, \ldots, a_r \} }[/math] oraz [math]\displaystyle{ B = \{ b_1, b_2, \ldots, b_r \} }[/math] będą różne modulo [math]\displaystyle{ m }[/math]. Zbiory [math]\displaystyle{ A, B }[/math] są równe modulo [math]\displaystyle{ m }[/math] wtedy i tylko wtedy, gdy zbiory [math]\displaystyle{ A' = \{ R_m (a_1), R_m (a_2), \ldots, R_m (a_r) \} }[/math] i [math]\displaystyle{ B' = \{ R_m (b_1), R_m (b_2), \ldots, R_m (b_r) \} }[/math] są równe.

Dowód


Twierdzenie H19
Niech będą dane zbiory [math]\displaystyle{ A = \{ 1, 2, \ldots, p - 1 \} }[/math], [math]\displaystyle{ B = \{ b_1, b_2, \ldots, b_{p - 1} \} }[/math], gdzie [math]\displaystyle{ p }[/math] jest liczbą pierwszą. Jeżeli wszystkie elementy zbioru [math]\displaystyle{ B }[/math] są różne modulo [math]\displaystyle{ p }[/math] i żadna z liczb [math]\displaystyle{ b_k \in B }[/math] nie jest podzielna przez [math]\displaystyle{ p }[/math], to zbiory [math]\displaystyle{ A, B, C = \{ b^{- 1}_1, b^{- 1}_2, \ldots, b^{- 1}_{p - 1} \} }[/math] są równe modulo [math]\displaystyle{ p }[/math].

Dowód


Zadanie H20
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą nieparzystą. Pokazać, że suma [math]\displaystyle{ \sum_{k = 1}^{p - 1} {\small\frac{(p - 1) !}{k}} }[/math] jest podzielna przez [math]\displaystyle{ p }[/math].

Rozwiązanie



Funkcje multiplikatywne

Definicja H21
Powiemy, że funkcja [math]\displaystyle{ f(n) }[/math] określona w zbiorze liczb całkowitych dodatnich jest funkcją multiplikatywną, jeżeli [math]\displaystyle{ f(1) = 1 }[/math] i dla względnie pierwszych liczb [math]\displaystyle{ a, b }[/math] spełniony jest warunek [math]\displaystyle{ f(a b) = f (a) f (b) }[/math].


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

a)   [math]\displaystyle{ f(n) }[/math] jest tożsamościowo równa zeru wtedy i tylko wtedy, gdy [math]\displaystyle{ f(1) = 0 }[/math]
b)   [math]\displaystyle{ f(n) }[/math] nie jest tożsamościowo równa zeru wtedy i tylko wtedy, gdy [math]\displaystyle{ f(1) = 1 }[/math]

Ponieważ [math]\displaystyle{ f(1) = f (1 \cdot 1) = f (1) f (1) }[/math], zatem [math]\displaystyle{ f(1) = 0 }[/math] lub [math]\displaystyle{ f (1) = 1 }[/math].

Jeżeli [math]\displaystyle{ f(1) = 0 }[/math], to dla dowolnego [math]\displaystyle{ n }[/math] mamy

[math]\displaystyle{ f(n) = f (n \cdot 1) = f (n) f (1) = 0 }[/math]

Czyli [math]\displaystyle{ f(n) }[/math] jest funkcją tożsamościowo równą zero.

Jeżeli [math]\displaystyle{ f(n) }[/math] nie jest funkcją tożsamościowo równą zero, to istnieje taka liczba [math]\displaystyle{ a \in \mathbb{Z}_+ }[/math], że [math]\displaystyle{ f(a) \neq 0 }[/math]. Zatem

[math]\displaystyle{ f(a) = f (a \cdot 1) = f (a) f (1) }[/math]

I dzieląc obie strony przez [math]\displaystyle{ f(a) \neq 0 }[/math], dostajemy [math]\displaystyle{ f(1) = 1 }[/math].


Przykład H23
Ponieważ [math]\displaystyle{ \gcd (1, c) = 1 }[/math], to [math]\displaystyle{ \gcd (n, c) }[/math] rozpatrywana jako funkcja [math]\displaystyle{ n }[/math], gdzie [math]\displaystyle{ c }[/math] jest ustaloną liczbą całkowitą, jest funkcją multiplikatywną (zobacz H7).



Funkcja Eulera [math]\displaystyle{ \varphi (n) }[/math]

Definicja H24
Funkcja Eulera [math]\displaystyle{ \varphi (n) }[/math][4] jest równa ilości liczb całkowitych dodatnich nie większych od [math]\displaystyle{ n }[/math] i względnie pierwszych z [math]\displaystyle{ n }[/math].


Twierdzenie H25
Funkcja Eulera [math]\displaystyle{ \varphi (n) }[/math] jest multiplikatywna, czyli dla względnie pierwszych liczb [math]\displaystyle{ m, n }[/math] jest [math]\displaystyle{ \varphi (m n) = \varphi (m) \varphi (n) }[/math].

Dowód


Twierdzenie H26
Dla dowolnej liczby całkowitej dodatniej [math]\displaystyle{ n }[/math] jest

[math]\displaystyle{ \varphi (n) = n \cdot \prod_{p|n} \left( 1 - {\small\frac{1}{p}} \right) }[/math]

gdzie iloczyn obliczamy po wszystkich liczbach pierwszych [math]\displaystyle{ p }[/math], będących dzielnikami liczby [math]\displaystyle{ n }[/math].

Dowód


Twierdzenie H27
Niech [math]\displaystyle{ n \in \mathbb{Z}_+ }[/math]. Jeżeli [math]\displaystyle{ q }[/math] jest liczbą pierwszą, to

[math]\displaystyle{ \varphi (q n) = \left\{ \begin{array}{rl} (q - 1) \varphi (n) & \quad \text{gdy} \quad q \nmid n\\ q \varphi (n) & \quad \text{gdy} \quad q \mid n \end{array} \right. }[/math]
Dowód


Twierdzenie H28
Niech [math]\displaystyle{ m, n \in \mathbb{Z}_+ }[/math]. Jeżeli [math]\displaystyle{ m \mid n }[/math], to [math]\displaystyle{ \varphi (m) \mid \varphi (n) }[/math].

Dowód


Zadanie H29
Dla [math]\displaystyle{ n \geqslant 3 }[/math] wartości [math]\displaystyle{ \varphi (n) }[/math] są liczbami parzystymi.

Rozwiązanie


Twierdzenie H30
Jeżeli [math]\displaystyle{ n }[/math] jest liczbą złożoną, to [math]\displaystyle{ \varphi (n) \leqslant n - \sqrt{n} }[/math].

Dowód


Twierdzenie H31
Niech [math]\displaystyle{ n \in \mathbb{Z}_+ }[/math]. Liczba [math]\displaystyle{ n }[/math] jest liczbą pierwszą wtedy i tylko wtedy, gdy [math]\displaystyle{ \varphi (n) = n - 1 }[/math].

Dowód


Zadanie H32
Niech [math]\displaystyle{ n \geqslant 2 }[/math]. Pokazać, że suma liczb całkowitych dodatnich nie większych od [math]\displaystyle{ n }[/math] i względnie pierwszych z [math]\displaystyle{ n }[/math] jest równa [math]\displaystyle{ {\small\frac{1}{2}} n \varphi (n) }[/math].

Rozwiązanie


Zadanie H33
Dla liczb naturalnych nieparzystych [math]\displaystyle{ n \geqslant 5 }[/math] prawdziwe jest oszacowanie [math]\displaystyle{ \varphi (n) \gt \pi (n) }[/math].

Rozwiązanie


Zadanie H34
Dla liczb naturalnych [math]\displaystyle{ n \geqslant 91 }[/math] prawdziwe jest oszacowanie [math]\displaystyle{ \varphi (n) \gt \pi (n) }[/math].

Rozwiązanie








Przypisy

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