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łada daje układ równań postaci:

${\begin{alignedat}{7}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{alignedat}}$

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{alignedat}{7}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{alignedat}}$

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ż

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

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.