Teoria liczb 2010, sem.IV,

B.Bajorska, O.Macedońska

Wykład 10.

Twierdzenia z Arytmetyki Modularnej

Potrzebne:

1. Własność skracania: Jeśli ad ≡

m

bd ∧ N W D(d, m) = 1 to a ≡

m

b.

2. Jeśli N W D(r

1

, m) = 1, N W D(r

2

, m) = 1, to N W D(r

1

r

2

, m) = 1.

2’. Jeśli N W D(r

i

, m) = 1, dla i = 1, 2, ..., n to N W D(

Q

n
i=1

r

i

, m) = 1.

3. a ≡

m

1

b, a ≡

m

2

b oraz N W D(m

1

, m

2

) = 1, to a ≡

m

1

m

2

b.

3’. a ≡

m

i

b, dla i = 1, 2, ..., n oraz N W D(m

i

, m

j

) = 1, to a ≡

m

1

m

2

...m

n

b.

1

Małe Twierdzenie Fermat’a (1640) i

Twierdzenie Eulera (ok. 1770 )

Twierdzenie 1. Niech a oznacza liczbe całkowita, a p oznacza liczb¸

e pierwsz¸

a.

Jeśli p nie dzieli a, to

a

p−1

≡ 1 (mod p).

Dowód. Liczby a, 2a, 3a, . . . , (p − 1)a s¸

a różne mod p a wi¸ec przystaj¸

a

(mod p) do 1, 2, 3, . . . , p − 1 w jakiejś kolejności. St¸

ad wnioskujemy, że ich

iloczyny przystaj¸

a (mod p):

a · 2a · 3a · · · (p − 1)a ≡ 1 · 2 · 3 · · · (p − 1) (mod p)

St¸

ad

a

p−1

(p − 1)! ≡ (p − 1)! (mod p).

Ponieważ p 6 |(p − 1)!, możemy skrócić i otrzymać a

p−1

≡ 1 (mod p).

Wniosek 1. Dla każdych p ∈ P i a ∈ N ,

a

p

≡ a (mod p).

Z Małego Twierdzenia Fermat’a wynika, że każda nieparzysta liczba pierw-

sza p jest dzielnikiem liczby 2

p−1

− 1. Odwrotne stwierdzenie nie jest praw-

dziwe, to znaczy że istniej¸

a liczby złożone n b¸ed¸

ace dzielnikami 2

n−1

− 1, ale

takich liczb ”nie jest dużo”, to znaczy że jeśli n dzieli 2

n−1

− 1, to jest duże

prawdopodobieństwo, że n jest liczb¸

a pierwsz¸

a i wtedy stosuje si¸e test dziele-

nia przez liczby pierwsze mniejsze lub równe

√

n. Istniej¸

a szybsze algorytmy

dla sprawdzenia, czy n jest liczb¸

a pierwsz¸

a. Tak na przykład sprawdzono, że

1

liczba 2

216 091

− 1 jest pierwsza. Trudność rozkładu dużej liczby na czynniki

pierwsze jest wykorzystana w kryptografii.

Wprowadzając funkcję ϕ(n) która przyporządkowuje liczbie naturalnej n

(n > 1) ilość liczb naturalnych mniejszych od n i względnie pierwszych z n,
i korzystając z jej własności, Euler uogólnił Małe Twierdzenie Fermat’a.

Twierdzenie 2 (Euler). Dla m ∈ N \ {1}, a ∈ Z takich, że NW D(a, m) = 1
zachodzi

a

ϕ(m)

≡

m

1.

Dowód. Jeśli r

1

, r

2

, ..., r

ϕ(m)

jest zredukowanym układem reszt modulo m,

to jak wiemy, liczby ar

1

, ar

2

, ..., ar

ϕ(m)

też tworzą zredukowany układ reszt

modulo m. Stąd każda z liczb r

i

przystaje modulo m do dokładnie jednej

liczby ar

j

, a dla ich iloczynów:

(ar

1

)(ar

2

) · ... · (ar

ϕ(m)

) = a

ϕ(m)

r

1

r

2

· ... · r

ϕ(m)

≡

m

r

1

r

2

· ... · r

ϕ(m)

.

Ponieważ ∀ i N W D(r

i

, m) = 1, to jak zauważyliśmy na początku,

N W D(r

1

r

2

· · · r

ϕ(m)

, m) = 1, zatem w powyższej równości można zasto-

sować skrócenie, skąd wynika a

ϕ(m)

≡

m

1.

Lemat 1. Jeśli a ∈ Z \ {0}, m ∈ N \ {1} oraz N W D(a, m) = 1, to kon-
gruencja ax ≡

m

1 ma nieskończenie wiele rozwiązań przystających parami

modulo m. W szczególności, istnieje dokładnie jedno rozwiązanie b takie, że
0 < b < m.

Dowód. Samodzielnie. Wskazówka: skorzystać z twierdzenia o rozwiąza-
niach liniowego równania diofantycznego.

2

Twierdzenie Wilsona

Twierdzenie zostało odkryte przez Johna Wilsona, będącego studentem Ed-
warda Waringa. Jednak żaden z nich nie był w stanie go udowodnić. Dopiero
w 1773 roku Lagrange dał przekonujący dowód.

Twierdzenie 3 (Wilson). Jeśli p ∈ P, to (p − 1)! ≡

p

−1.

Dowód. Jeśli p = 2 to (2−1)! = 1 ≡

2

−1, zatem twierdzenie jest prawdziwe.

Jeśli p > 2, to ∀ a

0 < a < p mamy N W D(a, p) = 1, a więc na podstawie

Lematu 1, dla każdego a istnieje dokładnie jedno naturalne b < m takie, że
ab ≡

m

1. Czyli w iloczynie (p − 1)! każdy czynnik a ma element odwrotny b.

Ale może być że a = b. Zauważmy, że jeśli ab ≡

m

1, to

a = b ⇐⇒ a

2

≡

p

1 ⇐⇒ a

2

− 1 ≡

p

0 ⇐⇒ (a − 1)(a + 1) ≡

p

0.

(a − 1)(a + 1) ≡

p

0 ⇐⇒ (a ≡

p

1) ∨ (a ≡

p

−1)

0<a<p

⇐⇒ (a = 1) ∨ (a = p − 1) .

2

Ponadto, jako że p jest liczbą nieparzystą, to liczb między 2 i p − 2 jest
parzysta ilość.

Wynika z tego, że wszystkie liczby naturalne między 2 i

p − 2 można połączyć w pary a

i

, b

i

takie, że a

i

b

i

≡

p

1, przy czym oczywiście

i = 1, 2, ...,

p−1

2

. Wobec tego

(p − 1)! = 1 · 2 · 3 · · · (p − 2)

|

{z

}

1

·(p − 1)

(∗)

≡

p

1 · 1 · (p − 1) ≡

p

−1.

Przykład 1. Korzystając z Twierdzenia Wilsona sprawdź, że: 2·26! ≡

29

−1.

Z twierdzenia Wilsona wiemy, że 28! ≡ −1 (mod 29). Czyli

28 · 27 · 26! ≡ −1 (mod 29), (−1)(−2) · 26! ≡ −1 (mod 29), co daje wynik.

3

Chińskie twierdzenie o resztach

Chińscy generałowie stosowali nastepujący sposób liczenia żołnierzy zebra-
nych na placu. Wydawano kolejno rozkazy: W dwuszeregu zbiórka! W 3-
szeregu zbiórka! W 5-szeregu zbiórka! i kontynuowali w ten sposób, oblicza-
jąc za każdym razem tylko resztę, czyli liczbę żołnierzy w ostatniej niepełnej
kolumnie.

Rozważmy łamigłówkę:

Siedmiu zbójnikow znalazło dzban w którym było x złotych monet. Kiedy
próbowali dzielić je pomi¸edzy sob¸

a - zostało 5 monet. Wywi¸

azała si¸e bójka i

trzech zgin¸eło. Pozostali znów dzielili monety ale zostały 2 monety. Ile było
monet? Mamy tu x ≡ 5 (mod 7),

x ≡ 2 (mod 4).

Chińskie Twierdzenie o Resztach dotyczy rozwi¸

azania układu postaci:

x ≡ r

1

(mod m

1

)

x ≡ r

2

(mod m

2

)

. . .

. . .

x ≡ r

n

(mod m

n

).

Twierdzenie 4 (Chińskie twierdzenie o resztach). Niech m

1

, ...m

n

będą licz-

bami naturalnymi parami względnie pierwszymi (tzn. ∀ i 6= j N W D(m

i

, m

j

) =

1) oraz niech r

1

, r

2

, ...r

n

będą dowolnymi liczbami całkowitymi. Wtedy układ

(∗)















x ≡

m

1

r

1

x ≡

m

2

r

2

. . . . . . . . .

x ≡

m

n

r

n

ma nieskończenie wiele rozwiązań całkowitych parami przystających do siebie
modulo M := m

1

m

2

· · · m

n

.

3

Dowód. Część 1: Istnienie rozwiązania Niech ∀ i M

i

:= M/m

i

będzie iloczy-

nem wszystkich modułów z wyjątkiem i-tego. Ponieważ moduły są względnie
pierwsze, to z trzeciej własności wymienionej na początku, otrzymujemy, że
N W D(M

i

, m

i

) = 1. Wobec tego z Lematu 1 dla każdego i istnieje N

i

takie,

że M

i

N

i

≡

m

i

1. Niech teraz t := r

1

M

1

N

1

+ r

2

M

2

N

2

+ ... + r

n

M

n

N

n

. Ponieważ

∀ j 6= i

m

j

|M

i

to M

i

≡

m

j

0, a więc ∀ j

t ≡

m

j

r

j

M

j

N

j

≡

m

j

r

j

, co oznacza,

że t jest rozwiązaniem układu (∗).

Część 2: Przystawanie rozwiązań Niech t

1

, t

2

będą rozwiązaniami układu

(∗). Wtedy ∀ i t

1

− t

2

≡

m

i

r

i

− r

i

= 0. Ponieważ moduły są parami względnie

pierwsze, to z trzeciej własności wymienionej na początku, otrzymujemy t

1

−

t

2

≡

M

0 ⇐⇒ t

1

≡

M

t

2

, co kończy dowód.

Uwaga Pierwsza część dowodu podaje de facto algorytm szukania pewnego
rozwiązania układu (∗):

Krok 1. Obliczamy M = m

1

m

2

· · · m

n

oraz M

i

:= M/m

i

Krok 2. Znajdujemy liczby N

i

takie że N

i

M

i

≡

m

i

1.

Krok 3. Obliczamy t =

P

i

r

i

N

i

M

i

.

Przykład 2. Znaleźć najmniejszą całkowitą liczbę nieujemną, która spełnia
układ kongruencji x ≡

6

4,

x ≡

35

5

Krok 0. Mamy m

1

= 6

m

2

= 35,

r

1

= 4,

r

2

= 5

Krok 1. Obliczamy M = m

1

m

2

= 210,

M

1

=

M

m

1

= m

2

= 35, M

2

=

M

m

2

=

m

1

= 6

Krok 2. Obliczamy N

1

, N

2

:

(a)

35 · N

1

≡

6

1 =⇒ −N

1

≡

6

1 =⇒ N

1

≡

6

−1 =⇒ N

1

= 5

(b)

6 · N

2

≡

35

1 =⇒ 36N

2

≡

35

6 =⇒ N

2

≡

35

6 =⇒ N

2

= 6

Krok 3. Obliczamy t = r

1

M

1

N

1

+r

2

M

2

N

2

= 4·35·5+5·6·6 = 700+180 = 880

Krok 4. Wyznaczamy rozwiązanie a spełniające dodatkowy warunek zadania.
Ponieważ a ≡

210

t oraz a jest najmniejszą liczbą nieujemną o tej własności,

to znaczy, że a jest resztą z dzielenia liczby t przez 210, zatem a = 40.

Uwaga W Kroku 2. niekoniecznie trzeba wybierać rozwiązanie będące

liczbą naturalną. Np. można było przyjąć N

1

= −1

4