Równanie diofantyczne

Równanie diofantyczne – równanie postaci:

$f(x_{1},x_{2},...,x_{n})=0$,

gdzie $f$ jest n-argumentową funkcją $(n\geq 2)$ i którego rozwiązania szukamy w dziedzinie liczb całkowitych. Jeżeli $f$ jest wielomianem ze współczynnikami całkowitymi to takie równanie nazywamy algebraicznym równaniem diofantycznym.

Przykłady równań diofantycznych

• Równanie $x^{n}+y^{n}=z^{n}$: dla $n=2$ równanie to obrazuje zależność między długościami boków w trójkącie prostokątnym (zobacz: trójki pitagorejskie). Dla $n>2$ równanie to nie ma rozwiązań – jest to treść wielkiego twierdzenia Fermata.
• Równanie $ax+by=c$ (a, b, c są dane) jest równaniem diofantycznym liniowym. Ma rozwiązanie wtedy i tylko wtedy, gdy największy wspólny dzielnik liczb a i b dzieli c.
• Równanie $2^{x}+1=y^{2}$ ma w liczbach naturalnych jedno rozwiązanie: (3,3).
• Równanie $x^{y}=y^{x}$ ma w liczbach naturalnych dwa rozwiązania, gdy $x\neq y$: $x=2,y=4$ oraz $x=4\ {\mbox{,}}\ y=2$.
• Równanie $x^{2}-ny^{2}=1$ ($n>0$) zwane równaniem Pella (od nazwiska angielskiego matematyka Johna Pella; sam Pell nie zajmował się takimi równaniami) – jeżeli $n$ jest kwadratem liczby naturalnej, to równanie nie ma rozwiązań, jeżeli zaś nie jest, ma ich ono nieskończenie wiele. Rozwiązania te tablicuje się w zależności od $n$.
• Równanie ${\tfrac {3^{a}\cdot k-1}{2^{a}\cdot k-1}}=2^{x}$ jest warunkiem istnienia tzw. pętli pierwszego stopnia w ciągu Collatza-Ulama. Ma ono tylko jedno rozwiązanie dla a=1, k=1 oraz x=1, które odpowiada występowaniu pętli trywialnej w tym ciągu.

Typowe problemy

Badając dane równanie diofantyczne staramy się przede wszystkim odpowiedzieć na następujące pytania:

• Czy ma ono rozwiązania?
• Jeśli tak, to ile ich jest (skończenie, czy nieskończenie wiele)?
• Czy istnieje algorytm na ich wyznaczanie?

W przypadku wielu prostych równań te i inne pytania pozostawały bez odpowiedzi przed długie lata, a próby znalezienia ich częstokroć prowadziły do głębokich badań i rozwoju nowych teorii matematycznych. Klasycznym przykładem jest wielkie twierdzenie Fermata, które pozostawało bez dowodu przez blisko 350 lat.

Metody rozwiązywania

Podstawowe metody

Metoda dekompozycji

Polega na przekształceniu równania z postaci:

$D(x_{1},...,x_{n})=0$

do postaci:

$D_{1}(x_{1},...,x_{n})\cdot D_{2}(x_{1},...,x_{n})...D_{k}(x_{1},...,x_{n})=a$,

gdzie $D_{1},D_{2},...,D_{k}\in \mathbb {Z} [X_{1},X_{2},...,X_{n}]$ i $a\in \mathbb {Z}$.

Następnie liczbę $a$ rozkładamy na $k$ czynników pierwszych. Każdy taki rozkład daje układ równań postaci:

${\begin{aligned}D_{1}(x_{1},...,x_{n})=a_{1}\\D_{2}(x_{1},...,x_{n})=a_{2}\\...\\D_{k}(x_{1},...,x_{n})=a_{k}\end{aligned}}.$

Suma zbioru rozwiązań tych układów daje zbiór rozwiązań równania $D$.

Przykład

Rozważmy równanie:

$nm-2n+m-6=0$.

I przekształćmy je w następujący sposób:

$n(m-2)+m-2=4$,

$(m-2)(n+1)=(\pm 2)^{2}$.

Odpowiada to dwóm możliwościom:

$\left\{{m-2=2 \atop n+1=2}\right.$,

$\left\{{m-2=-2 \atop n+1=-2}\right.$,

co daje rozwiązanie:$\{m=4,n=1\}$ lub $\{m=0,n=-3\}$.

Rozwiązania z wykorzystaniem nierówności

Metoda polega na ograniczeniu przestrzeni potencjalnych rozwiązań równania do skończonego zbioru.

Przykład

Szukamy wszystkich par liczb całkowitych $(n,m)$ spełniających równanie:

$n^{3}+m^{3}=(n+m)^{2}.$

Po pierwsze, rozwiązaniem powyższego równania są wszystkie pary postaci $(k,-k),k\in \mathbb {Z}$. Teraz rozważmy takie rozwiązania, że $(n+m)\neq 0$, wtedy równanie możemy podzielić obustronnie przez $(n+m)$:

$n^{2}-nm+m^{2}=n+m$

i przekształcić do postaci:

$(n-m)^{2}+(n-1)^{2}+(m-1)^{2}=2.$

Z tego wynikają nierówności $(n-1)^{2}\leq 1$ i $(m-1)^{2}\leq 1$ ograniczające położenie niewiadomych $n,m$ do przedziału $[0,2]$. Ponieważ rozpatrujemy rozwiązania w dziedzinie liczb całkowitych, daje to dziewięć potencjalnych rozwiązań. Poprzez sprawdzenie każdej możliwości z osobna możemy pokazać, że rozwiązaniami są pary: $(0,1)$, $(1,0)$, $(1,2)$, $(2,1)$, $(2,2)$.

Metoda parametryczna

W niektórych przypadkach zbiór rozwiązań równania $f(x_{1},x_{2},...,x_{n})=0$ można opisać jako:

${\begin{aligned}x_{1}=g_{1}(k_{1},...,k_{l})\\x_{2}=g_{2}(k_{1},...,k_{l})\\...\\x_{n}=g_{n}(k_{1},...,k_{l})\end{aligned}},$

gdzie $g_{1},g_{2},...,g_{n}$ są l-argumentowymi funkcjami o wartościach całkowitych i $k_{1},k_{2},...,k_{l}\in \mathbb {Z}$. Metoda parametryczna jest często wykorzystywana w sytuacjach, gdy nie jest możliwe pokazanie explicite wszystkich rozwiązań równania, ponieważ jest ich nieskończenie wiele.

Przykład

Określić w podanej wyżej postaci nieskończenie wiele rozwiązań poniższego równania:

$a^{3}+b^{3}+c^{3}=a^{2}+b^{2}+c^{2}.$

Rozważmy podzbiór rozwiązań takiej postaci, że $c=-b$, w ten sposób otrzymujemy równanie:

$a^{3}=a^{2}+2b^{2}.$

Biorąc $b=ka$ i $a=1+2k^{2}$ $(k\in \mathbb {Z} )$ powyższe równanie jest spełnione. W ten sposób otrzymujemy rodzinę rozwiązań w postaci:

$a=2k^{2}+1,$

$b=k(2k^{2}+1),$

$c=-k(2k^{2}+1).$

Zobacz też

• dziesiąty problem Hilberta
• równanie diofantyczne (automatyka)
• zbiór diofantyczny

Bibliografia

• Titu Andreescu, Dorin Andrica, Ion Cucurezeanu: An Introduction to Diophantine Equations A Problem-Based Approach. Birkhäuser, 2010. ISBN 978-0-8176-4548-9.