Konstrukcje w zadaniach z teorii liczb

Jak to? Przecież zadania konstrukcyjne dotyczą geometrii! To prawda, ale nie o zastosowaniu cyrkla i linijki będzie tu mowa. Naszym zadaniem będzie konstruowanie przykładów, a często nawet nieskończonego zbioru przykładów, dla pytań natury teorioliczbowej. Inspiracją do napisania tego tekstu było drugie zadanie z ubiegłorocznej Międzynarodowej Olimpiady Matematycznej (IMO).

Nietrudno przekonać się, że $a=b=1$ spełniają powyższy warunek. Czy istnieją jednak inne przykłady? Okazuje się, że nie, co można uzasadnić, powołując się na to, że pewien powiązany problem ma nieskończenie wiele rozwiązań. I właśnie tego typu zagadnieniom przyjrzymy się poniżej (przy okazji rozwiązując powyższe zadanie z IMO). Do dzieła!

Rozwiązanie. Pokażemy, jak skonstruować dowolnie duże liczby $a,b,c$ takie, że $$\frac{ab+ac+bc}{a+b+c}=3^K$$ dla pewnej liczby całkowitej dodatniej $K,$ oraz $a+b+c$ jest podzielne przez $3.$ Liczby te będą oczywiście spełniały warunki zadania.

Zachodzi równość: $$\frac{ab+ac+bc}{a+b+c}=a+b-\frac{a^2+ab+b^2}{a+b+c}.$$ Będziemy wybierali $c$ takie, że $\frac{a^2+ab+b^2}{a+b+c}=1,$ czyli $c=a^2+b^2+ab-a-b.$ Wystarczy dalej szukać względnie pierwszych liczb $a,b$ takich, że $a+b-1=3^K$ (oraz $3\mid a+b+c$).

Niech $a>N$ będzie liczbą pierwszą spełniającą $a\equiv 2(\mathrm{mod}3).$ Niech liczba $K$ spełnia nierówność $3^K+1>2a.$ Wówczas liczba $b=3^K+1-a$ jest większa od $a$ (więc również od $N$) oraz daje resztę 2 z dzielenia przez 3. Możemy ponadto założyć, że liczba $3^K+1$ nie jest podzielna przez $a,$ gdyż w przeciwnym wypadku $3^{K+1}+1=3(3^K+1)-2$ nie jest podzielne przez $a$ i moglibyśmy pod $K$ podstawić $K+1.$ Przy takim założeniu liczba $b$ nie może być podzielna przez $a,$ zatem jest z nią względnie pierwsza.

Przypuśćmy, że liczby $b$ i $c$ mają wspólny dzielnik pierwszy $p.$ Zgodnie z definicją $c$ liczba $p$ musiałaby wtedy dzielić $a^2-a=a(a-1).$ Ponieważ $a$ i $b$ są względnie pierwsze, to musiałoby zachodzić $p\mid (a-1),$ a skoro $(a-1)+b=3^K,$ otrzymalibyśmy $p\mid 3^K,$ czyli $p=3.$ Jest to jednak sprzeczność, gdyż $b\equiv 2(\mathrm{mod}3).$ Analogicznie dowodzimy, że $nwd(a,c)=1.$

Pozostaje zauważyć, że jeśli $a\equiv b\equiv 2(\mathrm{mod}3),$ to liczba $a+b+c=a^2+ab+b^2$ jest podzielna przez 3. ◻

Rozwiązanie. Niech $x_1,\dots ,x_{2n}$ będą różnymi liczbami całkowitymi dodatnimi, określmy ponadto: $$D=\prod _{1\le i<j\le 2n}\prod _{1\le k\le n}(x_i^k+x_j^k)$$ oraz $a_i=D{x}_i$ dla $i=1,\dots ,n.$ Oczywiście $x_i^k+x_j^k\mid D,$ zatem $D^k(x_i^k+x_j^k)\mid D^{k+1},$ więc tym bardziej $D^k(x_i^k+x_j^k)\mid D^{k+1}(x_i^{k+1}+x_j^{k+1}).$ Lewa strona tej podzielności to $a_i^k+a_j^k,$ zaś prawa to $a_i^{k+1}+a_j^{k+1},$ co kończy uzasadnienie. ◻

W kolejnych zadaniach będziemy stosować małe twierdzenie Fermata, zgodnie z którym jeśli $p$ jest liczbą pierwszą oraz $p\nmid a,$ to $a^{p-1}\equiv 1(\mathrm{mod}p).$ W prosty sposób wynika stąd, że jeśli $x\equiv y(\mathrm{mod}p-1),$ to $a^x\equiv a^y(\mathrm{mod}p).$

Rozwiązanie. Niech $p$ będzie liczbą pierwszą dzielącą $(2a{)}^b+1,$ wtedy oczywiście $nwd(p,2a)=1.$ Ustalmy dowolnie $\ell >\frac{2a}{p}$ i przyjmijmy $n=(p-1)(\ell p-2a).$ Wtedy $n\equiv 2a(\mathrm{mod}p),$ a zatem $$n^b+1\equiv {(2a)}^b+1\equiv 0(\mathrm{mod}p).$$ Jednocześnie $(p-1)\mid n,$ więc na mocy małego twierdzenia Fermata mamy $a^n+1\equiv 2(\mathrm{mod}p),$ co wyklucza podzielność $a^n+1$ przez $n^b+1$ i kończy rozwiązanie. ◻

Kolejny problem jest mocno związany z problemem z IMO 2024, od którego zaczęliśmy ten artykuł.

Rozwiązanie. Niech $p$ będzie liczbą pierwszą dzielącą $1+abc.$ Wówczas $p$ nie dzieli żadnej z liczb $a,b,c.$ Wybierzmy $k=\ell (p-1)-1$ dla pewnej liczby całkowitej dodatniej $\ell .$ Wtedy zgodnie z małym twierdzeniem Fermata $$a(a^k+bc)=a^{k+1}+abc\equiv 1+abc\equiv 0(\mathrm{mod}p).$$ Ponieważ $p\nmid a,$ więc $p\mid (a^k+bc).$ To samo dotyczy $c^k+ab$ oraz $b^k+ac,$ stąd $p$ dzieli $nwd(a^k+bc,c^k+ab,b^k+ac).$ ◻

Powyższe rozważania mogą nas naprowadzić na rozwiązanie Zadania 1. Wstawiając $c=1$ w rozumowaniu wyżej, a następnie przyjmując za $p$ dowolny dzielnik pierwszy liczby $1+ab,$ otrzymujemy, że $p$ dzieli $a^k+b$ i $b^k+a$ dla nieskończenie wielu wykładników $k.$

Załóżmy, że $(a,b)\ne (1,1),$ i przypuśćmy, że istnieją $N$ i $g$ takie, że dla dowolnego $n\ge N$ zachodzi $nwd(a^n+b,b^n+a)=g.$ W połączeniu z poprzednią obserwacją oznaczałoby to, że $p$ dzieli $g.$ Zwróćmy uwagę, że reszty z dzielenia pary $(a^n,b^n)$ przez $p$ powtarzają się cyklicznie z okresem $p-1.$ Skoro więc $p$ dzieli $nwd(a^n+b,b^n+a)$ dla wszystkich $n\ge N,$ to jest to prawdą dla dowolnego $n\ge 0.$

Podstawiając $n=0$ i $n=1,$ otrzymujemy, że $a+1,b+1,a+b$ są podzielne przez $p.$ Zatem $p$ dzieli również $2b=(a+b)-(a+1)+(b+1).$ Skoro $p$ jest względnie pierwsze z $b,$ to $p=2,$ a więc $ab+1=2^t$ dla pewnej liczby całkowitej dodatniej $t,$ a skoro $(a,b)\ne (1,1),$ musi być $t\ge 2,$ czyli $4\mid ab+1.$ Analiza reszt z dzielenia przez 4 liczb $a$ i $b$ prowadzi do wniosku, że $a$ i $b$ to liczby nieparzyste spełniające $b\equiv -a(\mathrm{mod}4).$ Przeczy to założeniom zadania, ponieważ $nwd(a^n+b,b^n+a)$ dla $n$ nieparzystego jest podzielne przez 4, a dla $n$ parzystego nie jest. ◻

W rozwiązaniu zadania 4 potrafiliśmy wskazać dowolnie duże liczby $n,$ które są podzielne przez $p-1$ i dawały zadaną resztę $2a$ z dzielenia przez $p.$ Obserwację tę uogólnia następujący

Powyższy lemat wykorzystamy w rozwiązaniu kolejnych dwóch zadań.

Rozwiązanie. Jeśli $nwd(a,b)=D>1,$ to dla $n=Dk,$ gdzie $k$ jest dowolną liczbą całkowitą dodatnią, obie liczby $a^n+n^b$ oraz $b^n+n^a$ są podzielne przez $D.$ Załóżmy teraz, że $nwd(a,b)=1$ oraz $a\ge b.$ Niech $p$ będzie liczbą pierwszą dzielącą $a^a+b^b.$ Zgodnie z lematem istnieje nieskończenie wiele liczb całkowitych dodatnich $n\ge 0$ spełniających $$n\equiv ab(\mathrm{mod}p)\text{oraz}n\equiv a+b(\mathrm{mod}p-1).$$ Wtedy, znów powołując się na małe twierdzenie Fermata, $$a^n+n^b\equiv a^{a+b}+(ab{)}^b\equiv a^b(a^a+b^b)\equiv a^a+b^b\equiv 0(\mathrm{mod}p),$$ skąd dostajemy $p\mid a^n+n^b.$ Analogicznie dowodzimy $p\mid b^n+n^a.$◻

Rozwiązanie. Załóżmy przeciwnie: istnieje wielomian $f(x)$ o współczynnikach całkowitych o takiej własności, że dla każdej liczby całkowitej dodatniej $n$ mamy $nwd(f(n^a),f(b^n))=1.$ Wynika z tego, że $nwd(f(b^a),f(b^b))=1.$ Stąd $b$ jest względnie pierwsze z wyrazem wolnym wielomianu $f,$ czyli $nwd(b,f(0))=1.$ Ustalmy $m,$ a następnie wybierzmy dzielnik pierwszy $p$ liczby $f(b^{am})$. Zachodzi wówczas $nwd(p,b)=1$. Na mocy lematu istnieje taka dodatnia liczba całkowita $n,$ że $n\equiv b^m(\mathrm{mod}p)$ i $n\equiv am(\mathrm{mod}p-1)$. Wówczas $$f(n^a)\equiv f(b^{ma})\equiv 0(\mathrm{mod}p).$$ Z drugiej strony, $f(b^{ma})\equiv f(b^n)(\mathrm{mod}p)$, stąd $p\mid nwd(f(n^a),f(b^n)).$ Uzyskana sprzeczność kończy dowód. ◻

Nasz przegląd zadań konstrukcyjnych zakończymy następującym zadaniem.

Rozwiązanie. Cóż, najkrótsze rozwiązanie tego problemu wymaga znacznie mniej technicznych umiejętności niż rozwiązania poprzednich zadań – wystarczy bowiem ,,wpaść” na odpowiedni przykład. A jest nim $a=2n-1$ oraz $b=2n+1$ dla dowolnej nieparzystej liczby naturalnej $n$! Aby udowodnić podzielność $a^b+b^a$ przez $a+b=4n,$ wystarczy osobno wykazać podzielność przez $4$ oraz przez $n,$ co pozostawiamy Czytelnikowi jako nietrudne ćwiczenie. ◻

W tym artykule przedstawiliśmy kilka problemów wymagających teorioliczbowych konstrukcji. Jak można było zobaczyć, odrobina kreatywności w połączeniu z dobrze znanymi faktami z elementarnej teorii liczb doprowadziła nas aż na poziom olimpijski.