Teoria liczb 2010, sem.IV,

B.Bajorska, O.Macedo«ska

Wykªad 8.

Równania diofantyczne i Wielkie Twierdzenie Fermat'a

1 Diofantos 200-284, Aleksandria

›yª w drugiej poªowie III wieku, w Aleksandrii (Grecja). Napis na nagrobku:

"Dzieci«stwo moje trwaªo

1
6

jego »ycia. Po dalszej

1

12

zacz¦ªa rosn¡¢ mi broda.

O»eniªem si¦ po dalszej

1
7

, a po 5 latach urodziª mi si¦ syn, który prze»yª

poªow¦ tego co ja. Zmarªem 4 lata po ±mierci syna. Policz przechodniu, ile

prze»yªem."

W latach 250-275 Diofantos napisaª 13-tomow¡ ksi¡»k¦ rithmetica". Skªa-

daªa si¦ ona z trzynastu ksi¡g (podobnie jak †lementy†uklidesa), z których

znanych jest tylko sze±¢. Ksi¦ga w owych czasach skªadaªy si¦ z kilkunastu

w¡skich pasków papirusu, zszytych lub sklejonych z boku, a caªe dzieªa (tzn.

zbiór zªo»ony z kilku ksi¡g) byªy przechowywane w naczyniach podobnych

do wiader. Diofantos bada równania i ukªady równa« o wspóªczynnikach caª-

kowitych unikaj¡c j¦zyka geometrycznego ale jego rozwa»ania s¡ - w gruncie

rzeczy - geometryczne.

Diofantos wprowadziª symbolik¦ literow¡, zajmowaª si¦ równaniami wielo-

mianowymi stopnia ≤ 3 o wspóªczynnikach i rozwi¡zaniach nad Z. Przy-

kªad: x

2

+ y

2

= z

2

, ax + by = c.

Pó¹niej powstaª problem: dowie±¢, »e równanie x

n

+ y

n

= z

n

nie ma roz-

wi¡za« w liczbach naturalnych x, y, z dla n > 2.

Wszystkie rozwi¡zania równania Pitagorasa X

2

+ Y

2

= Z

2

w liczbach caªko-

witych podaª Diofantos:
Twierdzenie 1. Je±li x, y, z jest wªa±ciw¡ trójk¡ pitagorejsk¡ tak¡, »e y jest

liczb¡ parzyst¡, to istniej¡ wzgl¦dnie pierwsze liczby naturalne m, n o ró»nej

parzysto±ci, przy czym m > n, takie, »e

x = m

2

− n

2

,

y = 2mn,

z = m

2

+ n

2

.

Denicja 1. Niech n ∈ N. Równaniem diofantycznym nazywamy do-

wolne równanie o n niewiadomych, którego rozwi¡zania nale»¡ do zbioru Z

n

.

Uwaga Nazwa pochodzi od imienia greckiego matematyka Diofantosa

(niektóre ¹ródªa podaj¡ »e miaª na imi¦ Diofantes).

Przykªad 1. Jest wiele znanych równa« diofantycznych - najsªynniejszym z

nich jest tzw. równanie Pierre Fermat'a (1601-1665), które zwykle podaje si¦

w postaci

x

n

+ y

n

= z

n

.

1

W notce zrobionej okoªo roku 1637 na marginesie dzieª Diofantosa Fermat

napisaª, »e to równanie diofantyczne dla n ≥ 3 nie ma rozwi¡za«. To stwier-

dzenie - znane jako Wielkie Twierdzenie Fermata - doczekaªo si¦ poprawnego

dowodu (przeprowadzonego przez Andrew Wiles'a) W roku 1993 udowod-

niª on hipotez¦ Shimury-Taniyamy-Weila dotycz¡c¡ krzywych eliptycznych,

a dopiero w roku 1995  Wielkie Twierdzenie Fermat'a.

Dla n = 1 powy»sze równanie mo»na zapisa¢ w postaci x+y −z = 0 i jest

to przykªad równania liniowego. Dla n = 2 przybiera ono posta¢ x

2

+ y

2

= z

2

i jest znane jako równanie Pitagorasa.

1.1 Liniowe równania diofantyczne

Denicja 2. Niech n ∈ N, a

1

, ..., a

n

, b ∈ Z

. Równanie diofantyczne postaci

a

1

x

1

+ a

2

x

2

+ · · · + a

n

x

n

= b

o niewiadomych x

1

, ..., x

n

nazywamy liniowym równaniem diofantycz-

nym.
Przykªad 2. x + 3y = 2, x

1

+ 2x

2

− 7x

3

= 0

Twierdzenie 2 (Istnienie rozwi¡zania równania liniowego o dwóch niewia-

domych). Niech a, b, c ∈ Z, a, b 6= 0. Równanie diofantyczne ax + by = c o

niewiadomych x, y ma rozwi¡zanie wtedy i tylko wtedy, gdy NW D(a, b) dzieli
c

.

Dowód. Zaªó»my, »e powy»sze równanie ax + by = c ma rozwi¡zanie, po-

wiedzmy x

0

, y

0

. Oznaczmy NW D(a, b) = d. Nale»y pokaza¢, »e d|c. Po-

niewa» dla pewnych u, v ∈ Z mamy a = ud, b = vd, oraz zachodzi róvno±¢
c = ax

0

+ by

0

to c = d(ux

0

+ by

0

)

, a st¡d d|c.

Odwrotnie, niech NW D(a, b) = d i d|c. Nale»y pokaza¢ istnienie rozwi¡zania

równania ax + by = c. Mamy z zaªo»e«, »e dla pewnego k, c = kd, oraz dla

pewnych u, v, au + bv = d. Mno»¡c t¦ równo±¢ przez k mamy

a(ku) + b(kv) = c,

co oznacza, »e istnieje rozwi¡zanie i jest nim np. para ku, kv.
Wniosek 1. Równanie diofantyczne ax + by = c ze wzgl¦dnie pierwszymi

wspóªczynnikami a, b zawsze ma rozwi¡zanie.

K¡»de liniowe równanie diofantyczne o dwóch niewiadomych maj¡ce roz-

wi¡zanie jest równowa»ne równaniu ax + by = c ze wzgl¦dnie pierwszymi

wspóªczynnikami a, b. Równowa»no±¢ oznacza »e równania maj¡ ten sam

zbiór rozwi¡za«.
Twierdzenie 3 (Posta¢ rozwi¡zania równania liniowego o dwóch niewia-

domych). Je±li para liczb x

0

, y

0

∈ Z

jest pewnym rozwi¡zaniem równania

diofantycznego ax + by = c, to wszystkie rozwi¡zania dane s¡ wzorami:

x = x

0

+

b

NW D(a, b)

t,

y = y

0

−

a

NW D(a, b)

t,

t ∈ Z.

2

Dowód. Zaªó»my, »e x

0

, y

0

jest rozwi¡zaniem istnienie którego dowiedli±my

i niech x, y b¦dzie dowolnym innym rozwi¡zaniem, to znaczy ax

0

+ by

0

= c =

ax + by

. Wtedy

a(x − x

0

) = b(y

0

− y).

Niech d := NW D(a, b), wtedy dla pewnych r, s mamy a = dr, b = ds oraz
NW D(r, s) = 1

. Z poprzedniej równo±ci skracaj¡c d mo»emy rozpatrywa¢

równanie

r(x − x

0

) = s(y

0

− y).

Poniewa» s dzieli iloczyn r(x − x

0

)

i NW D(r, s) = 1, to z Lematu Eu-

klidesamamy s|(x − x

0

)

i podobnie wnioskujemy, »e r|(y

0

− y)

. St¡d istniej¡

t

1

, t

2

takie, »e (x − x

0

) = st

1

, (y

0

− y) = rt

2

. Po wstawieniu st

1

i rt

2

za-

miast nawiasów mamy rst

1

= srt

2

, co daje t

1

= t

2

=: t.

Otrzymujemy, wi¦c

niesko«czony zbiór rozwi¡za« z parametrem caªkowitym t

x = x

0

+ st = x

0

+

b

d

t,

y = y

0

− rt = y

0

−

a
d

t,

co ko«czy dowód twierdzenia.

Zatem rozwi¡zywanie liniowego równania diofantycznego o dwóch nie-

wiadomych polega na znalezieniu jakiegokolwiek rozwi¡zania i skorzystaniu

ze wzoru w Twierdzeniu. 3. Jakiekolwiek rozwi¡zanie mo»na znale¹¢ albo

wprost albo wykorzystuj¡c przedstawienie najwi¦kszego wspólnego dzielnika

w postaci kombinacji liniowej.
Przykªad 3. Rozwi¡za¢ 3x − 2y = 1.

Poniewa» NW D(3, −2) = 1 dzieli 1, to z Twierdzenia 2 wynika, »e

powy»sze równanie ma rozwi¡zanie. Wida¢, »e jednym z rozwi¡za« jest
x

0

= 1, y

0

= 1

. Wobec tego, ponownie z Twierdzenia 3 wynika, »e wszystkie

rozwi¡zania maj¡ posta¢:

x = 1 + (−2)t = 1 − 2t,

y = 1 − 3t, t ∈ Z.

(Sprawdzenie: 3(1 − 2t) − 2(1 − 3t) = 1.)
Przykªad 4. Rozwi¡za¢ 11x + 3y = 4

Równanie ma rozwi¡zanie, poniewa» NW D(11, 3) = 1. Do znalezienia

jednego z rozwi¡za« wykorzystamy Algorytm Euklidesa.

11 = 3 · 3 + 2, 3 = 2 + 1 → 1 = 3 − 2 = 3 − (11 − 3 · 3) = 4 · 3 − 1 · 11

.

Po pomno»eniu obu stron przez 4 otrzymujemy 4 = 16 · 3 − 4 · 11 → x

0

=

−4, y

0

= 16

, zatem wszystkie rozwi¡zania maj¡ posta¢:

x = −4 + 3t,

y = 16 − 11t, t ∈ Z.

Uwaga Aby znale¹¢ jedno rozwi¡zanie niekoniecznie trzeba doprowadzi¢ Al-

gorytm Euklidesa do ko«ca - w powy»szym przykªadzie mo»na post¡pi¢ np.

tak:

11 = 3 · 3 + 2 → 2 = 11 − 3 · 3

·2

→ 4 = 2 · 11 − 6 · 3 → x

0

= 2, y

0

= −6

.

3

Twierdzenie 4 (WKW istnienia rozwi¡zania liniowego równania diofan-
tycznego). Niech n ∈ N, a

1

, a

2

, ..., a

n

, b ∈ Z,

n

P

i=1

a

2

i

> 0

. Wówczas liniowe

równanie diofantyczne a

1

x

1

+ a

2

x

2

+ · · · + a

n

x

n

= b

o niewiadomych x

1

, ..., x

n

ma rozwi¡zanie wtedy i tylko wtedy, gdy NW D(a

1

, ..., a

n

)|b

.

Przy rozwi¡zywaniu równa« o dowolnej ilo±ci niewiadomych mo»na równie»

korzysta¢ z Twierdzenia 3.

Przykªad 5. Rozwi¡za¢ 6x + 8y − 3z = 2

Z Twierdzenia 4 wynika, »e powy»sze równanie diofantyczne ma rozwi¡-

zanie, poniewa» NW D(6, 8, −3) = 1. Pierwszym krokiem na drodze do roz-

wi¡zania jest sprowadzenie tego równania do ukªadu równa«, z których jedno

ma dwie niewiadome, a drugie trzy. Robimy to w nast¦puj¡cy sposób: wybie-

ramy dowolne dwie niewiadome równania i za najmniejsz¡ cze±¢ równania za-

wieraj¡c¡ te dwie niewiadome (tzn. za ich kombinacj¦ która wyst¦puje w rów-

naniu) podstawiamy now¡ niewiadom¡ pomno»on¡ przez najwi¦kszy wspólny

dzielnik wspóªczynników (aby w prosty sposób zapewni¢ sobie caªkowitolicz-

bowy zapis rozwi¡za« równania). Np. je±li wybierzemy x, y to wyj±ciowe

równanie jest równowa»ne z ukªadem równa«: 2k = 6x + 8y ∧ 2k − 3z = 2.

Rozwi¡zujemy najpierw drugie równanie, korzystaj¡c z Twierdzenia 3:
k

0

= 1, z

0

= 0 → k = 1 − 3t, z = −2t, t ∈ Z

.

Wobec tego pierwsze równanie (które mo»na najpierw podzieli¢ przez 2) staje

sie teraz równaniem o dwóch niewiadomych x, y (k jest ju» dane), zatem

mo»emy je równie» rozwi¡za¢ na podstawie Twierdzenia 3:
2k = 6x + 8y

jest równowa»ne z 3x + 4y = k, czyli 3x + 4y = 1 − 3t.

Poniewa» 1 = 4 − 3 mamy 1 − 3t = 4(1 − 3t) − 3(1 − 3t), a wi¦c mamy

3x + 4y = −3(1 − 3t) + 4(1 − 3t) = 3(3t − 1) + 4(1 − 3t),

sk¡d x

0

= 3t − 1, y

0

= 1 − 3t

oraz x = 3t − 1 + 4m, y = 1 − 3t − 3m, m ∈ N.

Ostatecznie mamy: x = −1 + 3t + 4m, y = 1 − 3t − 3m, z = −2t, t, m ∈ N.
Uwaga Analogiczny sposób post¦powania mo»na zastosowa¢ równie» w przy-

padku równa« o wi¦kszej ilo±ci niewiadomych - np. równanie x−3y+2z−4t =
1

jest równowa»ne m.in. z ukªadem równa« x−3y = a, z−2t = b, a+2b = 1.

Podziaªu mo»na dokona¢ w dowolny sposób pami¦taj¡c jedynie, aby podsta-

wia¢ now¡ zmienn¡ pomno»on¡ przez najwi¦kszy wspólny dzielnik wspóª-

czynników.

4