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:

ap−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 = ax0 + by0 dla pewnych x0, y0 ∈ 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(ax0 + by0) = a(1 − kx0) + b(−ky0)

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(ax0 + by0) = a(1 − sx0) + b(−sy0)

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 = ax0 + by0 = gcx0 + gdy0 = g(cx0 + dy0)

. 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 poprzedniego wniosku wiemy,»e równanie ax + by = NW D(a, b) posiada rozwi¡zania (ustalmy, »e x0, y0 ∈ Z speªniaj¡ to równanie). Wówczas mamy: ax0 + by0 = N W D(a, b) i mno»ymy

stronami przez k. Wówczas liczby kx0, ky0 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 x0, y0 ∈ Z speªniaj¡ ax0 + by0 = c). Wiemy z zaªo»enia, »e c = (N W 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 x0, y0 czyli niech:

ax0 + by0 = kN W D(a, b)

. Wtedy odejmuj¡c stronami:ax0 + by0 = c i ax0 + by0 = kNW D(a, b) dostaniemy:

a(x0 − x0) + b(y0 − y0) = 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 zmiennych). Dla a, b ∈ Z i NW D(a, b)|c rozwi¡zania równania:

ax + by = c

s¡ postaci:

b

x = x0 +

t

N W D(a, b)

a

y = y0 −

t

N W D(a, b)

dla dowolnego t ∈ Z, gdzie x0, y0 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 x0, y0 speªnia równanie ax+by = c, czyli mamyax0+by0 =

c. We¹my teraz dowoln¡ par¦ x0, y0 tak¡, »¦ ax0 + by0 = c. Wówczas mamy:

ax0 + by0 = ax0 + by0

a(x0 − x0) = b(y0 − y0)

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

a

b

(x0 − x0) =

(y0 − y0)

N W D(a, b)

N W D(a, b)

i ponadto zachodzi NW D(

a

,

b

) = 1 (korzystamy z denicji NWD(a,b) -

N W D(a,b)

N W D(a,b)

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

b

(

)|(x0 − x0)

N W D(a, b)

a

(

)|(y0 − y0)

N W D(a, b)

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

b

x0 − x0 =

t

N W D(a, b)

3

a

y0 − y0 =

t

N W D(a, b)

Czyli para x0, y0 jest postaci:

b

x0 = x0 +

t

N W D(a, b)

a

y0 = y0 −

t

N W D(a, b)

. Wtakimraziewszystkierozwi¡zaniarównanialiniowegoax+by = cs¡wpostacipodanej

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:

ax1 ≡ b (mod n)

ax2 ≡ b (mod n)

x1 nie jest kongruentnym rozwi¡zaniem do x2, dokªadnie wtedy, gdy x1 6≡ x2 (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 N W D(a, n)|b i istnieje dokªadnie NW D(a, n) niekongruentnych rozwi¡za«.

Je±li ax0 ≡ b (mod n) zachodzi dla x0 takiego, »e 0 ≤ x0 ≤ n − 1 to nast¦puj¡cy zbiór daje peªn¡ list¦ niekongruentnych rozwi¡za« równania:

n

n

M = {x0, x0 +

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

}

N W D(a, 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 x0, y0 jest szczególnym rozwi¡zaniem równania ax + ny = b to wszystkie rozwi¡zania s¡ scharaktery-zowane jako:

n

x = x0 +

t

N W D(a, n)

a

y = y0 −

t

N W D(a, n)

4

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

n

. Mo»emy zatem wybra¢ pewne

N W D(a,n)

rozwi¡zanie x0 tak, »e 0 ≤ x0 ≤

n

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

N W D(a,n)

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

n

x = x0 + k NWD(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:

n

n

x0 + k

≡ x0 + l

(mod n)

N W D(a, n)

N W D(a, n)

n

n

k

≡ l

(mod n)

N W D(a, n)

N W D(a, n)

Z tego wynika natomiast:

n

n|

(k − l)

N W D(a, n)

n

(k − l) = ns

N W D(a, n)

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

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

N W D(a,n)

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 = {a1, . . . , aφ(n)} nazywamy zredukowanym zbiorem reszt, gdy:

• N W D(ai, n) = 1 dla i = 1, . . . , φ(n)

• ai ≡ aj (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 = {a1, . . . , aφ(n) jest zredukowanym zbiorem reszt modulo n oraz NW D(a, n) = 1, to zbiór:

Ra = {aa1, . . . , aaφ(n)}

te» jest zredukowanym system reszt modulo n (inaczej mo»na powiedzie¢, »e zbiór Ra 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(aai, n) = 1 (dla dowolonychi = 1, . . . , phi(n)) i aai ≡ aaj (mod n). Dla dowodu pierwszego zauwa»my,»e z zaªo»enia NW D(a, n) = 1

oraz NW D(ai, n). wynika NW D(aai, 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 = ai, b = aj, c = a. Zatem ai ≡ aj (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 N W D(a, n) = 1 i z poprzedniego wniosku

dostaniemy nowy zredukowany system reszt modulo n R = {aa1, . . . , aaφ(n)} i zachodzi równo±¢ zbiorów R = Ra (po odpowiedniej zamianie kolejno±ci). W takim razie zachodz¡

nast¦puj¡ce równo±ci:

a1 · a2 · . . . aφ(n) ≡ aa1 · aa2 · . . . aaφ(n) (mod n)

a1 · a2 · . . . aφ(n) ≡ aφ(n)a1 · a2 · . . . aφ(n) (mod n)

Poniewa» NW D(ai, n) = 1 dla i = 1, . . . , φ(n) zatem NW D(a1 · . . . · aφ(n)) = 1 i mo»na podzieli¢ kongruencj¦ otrzymuj¡c:

1 ≡ aφ(n) (mod n)

Ostatecznie:

aφ(n) ≡ 1 (mod n)

6