Twierdzenie Eulera, kongruencje liniowe i równania

diofantyczne liniowe

Bartosz Naskr¦cki

7 grudnia 2008

W poni»szym tek±cie postaramy si¦ zbudowa¢ potrzebny aparat do udowodnienia nast¦pu-

j¡cego przydatnego twierdzenia:

Denicja 1 (Funkcja φ Eulera). Dla danego n ∈ N deniujemy funkcj¦ zliczaj¡c¡ liczby

naturalne (wi¦ksze od zera), wzgl¦dnie pierwsze z n:

φ(n) = #{k : N W D(k, n) = 1, 1 ≤ k ≤ n − 1}

Twierdzenie 1 (Twierdzenie Eulera). Dla danych a, n ∈ N takich, »e NW D(a, n) = 1

zachodzi nast¦puj¡ca kongruencja:

a

φ(n)

≡ 1

(mod n)

Wniosek 1 (Maªe twierdzenie Fermata). Dla danych a, p ∈ N, takich, »e p-liczba pierwsza,
N W D(a, p) = 1

(a jest wzgl¦dnie pierwsza z p) zachodzi:

a

p−1

≡ 1

(mod p)

Dowód. Wystarczy wzi¡¢ n = p w twierdzeniu Eulera. Wówczas φ(p) = p − 1 (sprawdzi¢!).

Denicja 2 (Diofantyczne równanie liniowe(2 zmiennych)). Równanie postaci:

ax + by = c

dla a, b, c, x, y ∈ Z nazywamy diofantycznym równaniem liniowym

Twierdzenie 2. Je±li g = NW D(a, b) i a, b 6= 0 liczby caªkowite, to g jest najmniejszym

dodatnim rozwi¡zaniem równania liniowego ax + by, gdzie x, y ∈ Z.

Dowód. Niech S = {ax + by : x, y ∈ Z}. W zbiorze S istnieje najmniejsza liczba naturalna
l = ax

0

+ by

0

dla pewnych x

0

, y

0

∈ Z (istnienie takiej liczby jest zawsze pewne w dowolnym

podzbiorze liczb naturalnych!). Ponadto ªatwo zauwa»y¢, »e dla x, y ∈ N ax + by ≥ 0,

czyli S ∩ N 6= ∅. Poka»emy teraz,»e l = g (czyli NW D(a, b) jest najmniejszym dodatnim

rozwi¡zaniem równania diofantycznego liniowego dwóch zmiennych).

l|a

1

Gdyby tak nie byªo, wówczas a = kl + r dla 0 ≤ r < l. Ale wtedy

r = a − lk = a − k(ax

0

+ by

0

) = a(1 − kx

0

) + b(−ky

0

)

czyli r ∈ S. Ale to jest niemo»liwe, bo l byªo najmniejszym dodatnim elementem zbioru S!

l|b

Gdyby tak nie byªo, wówczas b = sl + r dla 0 ≤ r < l. Ale wtedy

r = a − ls = a − s(ax

0

+ by

0

) = a(1 − sx

0

) + b(−sy

0

)

czyli r ∈ S. Ale to jest niemo»liwe, bo l byªo najmniejszym dodatnim elementem zbioru S!

Zatem l jest wspólnym dzielnikiem a i b.

Ale g te» jest wspólnym dzielnikiem a i b zatem a = gc i b = gd dla pewnych c, d ∈ Z. W

takim razie mamy:

l = ax

0

+ by

0

= gcx

0

+ gdy

0

= g(cx

0

+ dy

0

)

. W takim razie g|l. Ale g = NW D(a, b) jest najwi¦kszym mo»liwym wspólnym dzielnikiem
a

i b zatem g = l , co ko«czy dowód twierdzenia.

Wniosek 2. Równanie diofantyczne:

ax + by = c

gdzie c = NW D(a, b) posiada rozwi¡zania x, y ∈ Z

Dowód. Zbiór S = ax + by : x, y ∈ Z ma niepusty przekrój ze zbiorem liczb naturalnych i

najmniejsza taka liczba jest dokªadnie równa NW D(a, b) (dowód poprzedniego twierdzenia).

Twierdzenie 3. Równanie diofantyczne:

ax + by = c

posiada rozwi¡zania x, y ∈ Z wtedy i tylko wtedy, gdy NW D(a, b)|c

Dowód. Udowodnimy najpierw, »e je±li NW D(a, b)|c to równanie ax + by = c posiada

rozwi¡zania w liczbach caªkowitych.

Zauwa»my, »e z zaªo»enia wynika, i» c = NW D(a, b)k dla pewnego k ∈ Z. Ale z poprzed-

niego wniosku wiemy,»e równanie ax + by = NW D(a, b) posiada rozwi¡zania (ustalmy, »e
x

0

, y

0

∈ Z speªniaj¡ to równanie). Wówczas mamy: ax

0

+ by

0

= N W D(a, b)

i mno»ymy

stronami przez k. Wówczas liczby kx

0

, ky

0

speªniaj¡ równanie ax + by = c.

Teraz udowodnijmy, »e je±li ax+by = c posiada rozwi¡zania to NW D(a, b)|c. Równowa»nie

wystarczy udowodni¢ (dowód przez kontrapozycj¦), »e je±li NW D(a, b) - c, to równanie
ax + by = c

nie posiada rozwi¡za« caªkowitych. Przypu±¢my, »e rozwi¡zanie istnieje(niech

x

0

, y

0

∈ Z speªniaj¡ ax

0

+ by

0

= c

). Wiemy z zaªo»enia, »e c = (NW D(a, b))k + r i

0 < r < N W D(a, b)

. Ale z poprzedniej cz¦±ci twierdzenia wiemy ponadto, »e równanie

2

ax + by = kN W D(a, b)

posiada rozwi¡zania. Oznaczmy takie rozwi¡zanie jako x

0

, y

0

czyli

niech:

ax

0

+ by

0

= kN W D(a, b)

. Wtedy odejmuj¡c stronami:ax

0

+ by

0

= c

i ax

0

+ by

0

= kN W D(a, b)

dostaniemy:

a(x

0

− x

0

) + b(y

0

− y

0

) = r

, czyli liczba r ∈ S = ax + by : x, y ∈ Z, ale to jest sprzeczno±¢, bo z poprzedniego twierdzenia

wynikaªo, »e NW D(a, b) jest najmniejszym dodatnim elementem zbioru S !

Twierdzenie 4 (Charakteryzacja rozwi¡za« diofantycznego równania liniowego dwóch zmi-

ennych). Dla a, b ∈ Z i NW D(a, b)|c rozwi¡zania równania:

ax + by = c

s¡ postaci:

x = x

0

+

b

N W D(a, b)

t

y = y

0

−

a

N W D(a, b)

t

dla dowolnego t ∈ Z, gdzie x

0

, y

0

jest pewnym dowolnie ustalonym rozwi¡zaniem równania

ax + by = c

(z poprzedniego tw. wiemy, »e takie istnieje).

Dowód. Po pierwsze nale»y sprawdzi¢, »e powy»ej podane pary x, y s¡ istotnie rozwi¡zani-

ami.

Przypu±¢my teraz, »e pewna para x

0

, y

0

speªnia równanie ax+by = c, czyli mamyax

0

+by

0

=

c

. We¹my teraz dowoln¡ par¦ x

0

, y

0

tak¡, »¦ ax

0

+ by

0

= c

. Wówczas mamy:

ax

0

+ by

0

= ax

0

+ by

0

a(x

0

− x

0

) = b(y

0

− y

0

)

Poniewa» NW D(a, b)|a i NW D(a, b)|b, zatem:

a

N W D(a, b)

(x

0

− x

0

) =

b

N W D(a, b)

(y

0

− y

0

)

i ponadto zachodzi NW D(

a

N W D(a,b)

,

b

N W D(a,b)

) = 1

(korzystamy z denicji NWD(a,b) -

najwi¦kszego wspólnego dzielnika a i b). Czyli w takim razie musz¡ zachodzi¢ nast¦puj¡ce

podzielno±ci:

(

b

N W D(a, b)

)|(x

0

− x

0

)

(

a

N W D(a, b)

)|(y

0

− y

0

)

Z tego i z równo±ci powy»ej dostajemy, »e istnieje t ∈ Z takie, »e :

x

0

− x

0

=

b

N W D(a, b)

t

3

y

0

− y

0

=

a

N W D(a, b)

t

Czyli para x

0

, y

0

jest postaci:

x

0

= x

0

+

b

N W D(a, b)

t

y

0

= y

0

−

a

N W D(a, b)

t

.

W takim razie wszystkie rozwi¡zania równania liniowego ax+by = c s¡ w postaci podanej

w twierdzeniu. To ko«czy dowód.

Denicja 3 (Kongruencja liniowa). Zbiór rozwi¡za« równania ax ≡ b (mod n), gdzie a, b, n ∈
Z ustalone, x zmienna nazywamy zbiorem rozwi¡za« kongruencji liniowej, a samo równanie

nazywamy kongruencj¡ liniow¡.

Uwaga:rozwi¡zania kongruencji liniowej je±li istniej¡ to z powy»szych twierdze« wynika,

»e tworz¡ zbiór niesko«czony. Dla nas interesuj¡ce s¡ tylko te rozwi¡zania, które nie s¡ do

siebie kongruentne, czyli dla:

ax

1

≡ b

(mod n)

ax

2

≡ b

(mod n)

x

1

nie jest kongruentnym rozwi¡zaniem do x

2

, dokªadnie wtedy, gdy x

1

6≡ x

2

(mod n).

Twierdzenie 5 (Charakteryzacja rozwi¡za« kongruencji liniowej). Kongruencja liniowa
ax ≡ b

(mod n), gdzie a, b, n ∈ Z posiada rozwi¡zania dokªadnie wtedy, gdy NW D(a, n)|b i

istnieje dokªadnie NW D(a, n) niekongruentnych rozwi¡za«.

Je±li ax

0

≡ b

(mod n) zachodzi dla x

0

takiego, »e 0 ≤ x

0

≤ n − 1

to nast¦puj¡cy zbiór

daje peªn¡ list¦ niekongruentnych rozwi¡za« równania:

M = {x

0

, x

0

+

n

N W D(a, n)

, . . . , x

0

+ (N W D(a, n) − 1)

n

N W D(a, n)

}

Dowód. Kongruencja liniowa ax ≡ b (mod n) jest równowa»na diofantycznemu równaniu

liniowemu:

ax + ny = b

Wiemy z poprzednich twierdze«, »e takie równanie posiada rozwi¡zania dokªadnie wt-

edy, gdy NW D(a, n)|b. Ponadto z poprzedniego twierdzenia wiemy,»e je±li para x

0

, y

0

jest

szczególnym rozwi¡zaniem równania ax + ny = b to wszystkie rozwi¡zania s¡ scharaktery-

zowane jako:

x = x

0

+

n

N W D(a, n)

t

y = y

0

−

a

N W D(a, n)

t

4

gdzie t ∈ Z. Zauwa»my zatem, »e x ≡ x

0

mod

n

N W D(a,n)

. Mo»emy zatem wybra¢ pewne

rozwi¡zanie x

0

tak, »e 0 ≤ x

0

≤

n

N W D(a,n)

− 1

. W ten sposób dostaniemy list¦ NW D(a, n)

niekongruentnych do siebie rozwi¡za« wyj±ciowej kongruencji:

x = x

0

+ k

n

N W D(a, n)

dla k = 0, 1, . . . , NW D(a, n) − 1. Z konstrukcji wida¢, »e nale»a one do zbioru {0, 1, . . . , n −
1}

. Ponadto, gdy:

x

0

+ k

n

N W D(a, n)

≡ x

0

+ l

n

N W D(a, n)

(mod n)

k

n

N W D(a, n)

≡ l

n

N W D(a, n)

(mod n)

Z tego wynika natomiast:

n|

n

N W D(a, n)

(k − l)

n

N W D(a, n)

(k − l) = ns

dla pewnego s ∈ Z. Ale zauwa»my, »e skoro 0 ≤ k, l ≤ NW D(a, n) − 1, to 0 ≤ (k − l) ≤
N W D(a, n) − 1

(mo»emy przyj¡¢, »e k ≥ l, inaczej zamieniamy je rolami). Ale skoro

ns ∈ Z, to

n

N W D(a,n)

(k − l)

, a to mo»liwe tylko dla k = l z powy»szej uwagi. Czyli istotnie

rozwi¡zania s¡ parami niekongruentne i jest ich dokªadnie NW D(a, n).

Wniosek 3. Kongruencja liniowa ax ≡ 1 (mod n) dla NW D(a, n) = 1 ma dokªadnie jedno

rozwi¡zanie x takie, »e 0 ≤ x ≤ n − 1.
Wniosek 4 (Istnienie odwrotno±ci multiplikatywnej modulo n). Dla dowolnego a ∈ Z

takiego,»e NW D(a, n) = 1 istnieje dokªadnie jedna reszta b ∈ Z taka, »e 0 ≤ b ≤ n − 1

i ab ≡ 1 (mod n).
Dowód. Za b wystarczy wzi¡¢ jednoznacznie wyznaczone rozwi¡zanie kongruencji ax ≡
1

(mod n), które istnieje na podstawie poprzedniego wniosku.

Denicja 4 (Zredukowany zbiór reszt modulo n). Zbiór R = {a

1

, . . . , a

φ(n)

}

nazywamy

zredukowanym zbiorem reszt, gdy:

• N W D(a

i

, n) = 1

dla i = 1, . . . , φ(n)

• a

i

≡ a

j

(mod n) =⇒ i = j (elementy s¡ parami niekongruentne)

W szczególno±ci skoro zbiór zredukowanych reszt R skªada si¦ z φ(n) elementów, zatem

stanowi on zbiór wszystkich odwracalnych reszt modulo n.
Wniosek 5. Je±li a, n ∈ Z iR = {a

1

, . . . , a

φ(n)

jest zredukowanym zbiorem reszt modulo n

oraz NW D(a, n) = 1, to zbiór:

R

a

= {aa

1

, . . . , aa

φ(n)

}

te» jest zredukowanym system reszt modulo n (inaczej mo»na powiedzie¢, »e zbiór R

a

skªada

si¦ z tych samych elementów, co zbiór R zapisanych w innej kolejno±ci -przepermutowanych).

5

Dowód. Wystarczy udowodni¢, »e NW D(aa

i

, n) = 1

(dla dowolonychi = 1, . . . , phi(n))

i aa

i

≡ aa

j

(mod n). Dla dowodu pierwszego zauwa»my,»e z zaªo»enia NW D(a, n) = 1

oraz NW D(a

i

, n)

. wynika NW D(aa

i

, n) = 1

. Dla dowodu drugie wystarczy skorzysta¢ z

wªasno±ci kongruencji: dla NW D(c, n) = 1 mamy:

ac ≡ bc

(mod n) =⇒ a ≡ b mod n

dla a = a

i

, b = a

j

, c = a

. Zatem a

i

≡ a

j

(mod n), ale poniewa» R jest zredukowanym

ukªadem reszt, to i = j.

Dowód twierdzenia Eulera. Rozwa»my zredukowany system R reszt modulo n. Taki system

istnieje, gdy» wystarczy rozwa»y¢ reszty modulo n zbioru liczb {x : NW D(x, n) = 1, 1 ≤
x ≤ n − 1}

. Z zaªo»e« twierdzenia mamy NW D(a, n) = 1 i z poprzedniego wniosku

dostaniemy nowy zredukowany system reszt modulo n R = {aa

1

, . . . , aa

φ(n)

}

i zachodzi

równo±¢ zbiorów R = R

a

(po odpowiedniej zamianie kolejno±ci). W takim razie zachodz¡

nast¦puj¡ce równo±ci:

a

1

· a

2

· . . . a

φ(n)

≡ aa

1

· aa

2

· . . . aa

φ(n)

(mod n)

a

1

· a

2

· . . . a

φ(n)

≡ a

φ(n)

a

1

· a

2

· . . . a

φ(n)

(mod n)

Poniewa» NW D(a

i

, n) = 1

dla i = 1, . . . , φ(n) zatem NW D(a

1

· . . . · a

φ(n)

) = 1

i mo»na

podzieli¢ kongruencj¦ otrzymuj¡c:

1 ≡ a

φ(n)

(mod n)

Ostatecznie:

a

φ(n)

≡ 1

(mod n)

6