Delta mi!

Załóżmy, że dodatnie liczby całkowite spełniają podane równanie. Oznaczmy przez ich największy wspólny dzielnik; tak więc gdzie to liczby naturalne względnie pierwsze. Wstawiając to do równania i dzieląc stronami przez otrzymujemy

(1)

Niech będzie dowolnym dzielnikiem pierwszym liczby Wobec związku (1) jest też dzielnikiem sumy To znaczy, że (mod ); a skoro jest liczbą parzystą, mamy stąd (mod ), i dalej

Liczba nie dzieli się przez (bo zaś są względnie pierwsze); zatem

Skoro nie ma innych dzielników pierwszych, znaczy to, że

(2)

Zatem liczby i (względnie pierwsze) są obie nieparzyste; stąd (mod 4), bo jest liczbą parzystą. W równości (2) mamy więc skąd Wracamy do równania (1): To pokazuje, że (dla pewnego ); przy tym czyli : liczba dzieli się przez

Na odwrót, załóżmy, że dla pewnego Wówczas para jest rozwiązaniem zadanego równania:

Uzyskaliśmy żądaną równoważność.

Rozważana suma ma parzystą liczbę składników. Parujemy: pierwszy z ostatnim, drugi z przedostatnim itd. Dostajemy sumę par postaci

Wystarczy pokazać, że każda z liczb dzieli się przez W rozwinięciu dwumianowym

składniki odpowiadające indeksom są podzielne przez ; skoro zaś jest liczbą nieparzystą, dwa składniki początkowe dają w sumie

Tak więc dzieli się przez Korzystając jeszcze raz z nieparzystości wnosimy, że dzieli się przez

Wykażemy, że każda dodatnia liczba całkowita mogła zostać uzyskana (poprzez ciąg kilku kolejnych dopisywań) z pewnej mniejszej liczby. Stąd dostaniemy odpowiedź twierdzącą na postawione w zadaniu pytanie.

Liczbę dającą resztę z dzielenia przez powiedzmy można uzyskać w jednym kroku z liczby Liczba dająca resztę z dzielenia przez powiedzmy może zostać uzyskana w dwóch krokach z liczby : w pierwszym kroku dopisujemy liczbę Wreszcie liczba podzielna przez powiedzmy może zostać uzyskana w siedmiu krokach z liczby : w kolejnych pośrednich krokach dopisujemy

Odpowiedź: oraz
Spośród ośmiu rozważanych sum największa jest z jednej strony nie mniejsza od a z drugiej - nie większa od Stąd wniosek, że Ponadto suma ośmiu rozważanych sum jest równa dwukrotności sumy wszystkich liczb wpisanych w pola tablicy, czyli Liczba jest dzielnikiem tej sumy, wobec czego lub Poniższy przykład pozwala stwierdzić, że te wartości w istocie są osiągalne.

Odpowiedź:
Zauważmy, że dowolny wspólny dzielnik liczb oraz dzieli również liczbę

i w konsekwencji także liczbę

Pozostaje zauważyć, że dla mamy oraz

Zauważmy, że dla dowolnych różnych liczb całkowitych ma miejsce podzielność

Istotnie, oznaczając mamy

a każda z liczb jest podzielna przez (w razie potrzeby przyjmujemy ).

Korzystając z przywołanego spostrzeżenia, możemy zapisać

co w połączeniu z założeniami zadania prowadzi do wniosku, że jest liczbą podzielną zarówno przez jak i przez Pozostaje skorzystać z założenia, że liczby i są względnie pierwsze.

Z tożsamości

wynika, że zadane równanie jest równoważne następującemu:

(1)

Jest też równoważne każdemu z dwóch równań uzyskanych przez cykliczne przestawienie zmiennych w (1). Jeśli więc liczby całkowite spełniają warunki zadania, to iloczyny są nieujemne, co oznacza, że liczby są wszystkie nieujemne lub wszystkie niedodatnie.

Weźmy przypadek, gdy Ze związku (1) (oraz warunku, że nie mają wspólnego dzielnika ) wynika, że dla pewnej pary liczb całkowitych względnie pierwszych. Przepisujemy (1) jako czyli

Uwzględniając pominięty przypadek, gdy widzimy, że trójka ma postać

(2)

Na odwrót, jeśli trójka liczb całkowitych ma taką postać (więc ; ), wówczas spełnione jest równanie (1) (równoważne wyjściowemu), zaś liczby są względnie pierwsze. Wzór (2) przedstawia więc ogólne rozwiązanie postawionego zagadnienia.

Można sformułować tę odpowiedź w formie bardziej symetryczej, pisząc, że liczby po ewentualnej jednoczesnej zmianie znaku, są kwadratami trzech względnie pierwszych liczb całkowitych, z których jedna jest sumą dwóch pozostałych

Dla oba warunki są spełnione. Dalej przyjmujemy Zapiszmy liczbę jako

(1)

Wobec określenia mamy kongruencję (mod ), którą podnosimy do potęgi : (mod ); stąd po pomnożeniu przez (i uwzględnieniu (1)):

(2)

Jeśli zachodzi warunek (i), to jest dzielnikiem liczby równej czyli w równości (1) jest Ze związku (2) dostajemy (mod ); pomnożenie przez 2 daje warunek (ii).

Na odwrót, jeśli zachodzi warunek (ii), to daną w nim kongruencję (mod ) dzielimy stronami przez 2 (to dozwolone, bo jest liczbą nieparzystą), otrzymując (mod ). W połączeniu z (2) dostajemy

(3)

Ale więc kongruencja (3) jest równością, skąd To znaczy, w myśl (1), że dzieli liczbę i mamy warunek (i).

Na "tak": gdy jest nieparzyste, dzieli się przez i wystarczy zauważyć, że a więc dzieli się przez przez oraz przez

Na "nie": liczba ta zarówno modulo 5, jak modulo 11 przystaje do 2.

Zauważmy bowiem, że i podobnie i ).

Skoro to ; podobnie z wynika a więc skąd

Analogicznie, skoro więc stąd ; podobnie z mamy ; wobec tego

Zauważmy, że reszta z dzielenia liczby przez liczbę jest równa

wobec tego równość można przepisać jako

czyli równoważnie

Zauważmy ponadto, że czynnik

jest równy jeżeli dzieli oraz 0 w przeciwnym przypadku. Stąd wniosek, że powyższy warunek można przepisać jako

Łatwo sprawdzić, że równość ta jest spełniona dla gdzie jest dodatnią liczbą całkowitą. Przykładową nieskończoną rodzinę liczb spełniających warunek zadania stanowią więc wszystkie potęgi dwójki.

Udowodnimy, że jeżeli jest liczbą podzielną przez to nie można zapisać w postaci sumy dwóch elementów zbioru albo - w myśl tezy poprzedniego zadania - w postaci iloczynu dwóch elementów zbioru Przypuśćmy, że

gdzie Skoro to co najmniej jeden z czynników w liczniku powyższego ułamka jest podzielny przez ; bez straty ogólności załóżmy, że Stąd wynika, że liczby i są tej samej parzystości, skąd wobec - obie są nieparzyste. Jednak wówczas daje resztę przy dzieleniu przez - sprzeczność.

Aby wskazać nieskończenie wiele liczb naturalnych będących iloczynami dwóch elementów zbioru rozważymy ciąg Fibonacciego

i wykorzystamy tożsamość

Dla mamy więc

co jest liczbą całkowitą dla każdego To kończy dowód, gdyż dla różnych otrzymujemy różne liczby.

(a) Przypuśćmy, że liczby oraz mają wspólny dzielnik pierwszy (jasne, że ). Wykażemy, że wówczas liczba dzieli się przez (nie jest więc bezkwadratowa). Zgodnie z małym twierdzeniem Fermata, (mod ). Podnosimy tę kongruencję stronami do potęgi otrzymując (mod ). Zatem dla pewnej liczby całkowitej Stąd

czyli (mod ); a to była nasza teza.

(b) Przykład pokazujący, że nie zachodzi implikacja odwrotna, nie tak łatwo znaleźć (mała szansa, że trafimy, zwyczajnie próbując - bez komputera ciężko). Prosty program, który dla zadanej liczby pierwszej kontroluje dwie końcowe cyfry rozwinięcia (przy podstawie ) kolejnych potęg dwójki, pozwala znaleźć moment powtórzenia końcówki czyli wykładnik dla którego (mod ). Powtarzamy tę procedurę dla kolejnych liczb pierwszych ; warto przy tym, dla oszczędności czasu, ograniczyć zakres wykładnika, np. do W ten sposób szybko znajdujemy parę ; nie jest ona jednak szukanym kontrprzykładem, bowiem dla tej pary zachodzą związki (mod ), z których nietrudno wynika, że liczby i nie są względnie pierwsze.

Następna znaleziona para jest już dobra: gdyby liczby oraz nie były względnie pierwsze, ta ostatnia musiałaby się dzielić przez 7 lub 13; ale minimalne wykładniki dla których (mod 7), (mod 13), to więc wykładnik musiałby się dzielić przez 3; a tak nie jest. Skoro zaś ta para została wygenerowana przez algorytm, zapewniający podzielność przez zatem liczba nie jest bezkwadratowa.

Niech gdzie oznacza -krotne złożenie funkcji Z warunków zadania wynika, że dla pewnego mamy Jeżeli to

co nie może mieć miejsca, gdyż reszty z dzielenia przez wyrazów ciągu są parami różne. To oznacza, że czyli

Przypuśćmy nie wprost, że czyli Wówczas istnieją takie liczby całkowite że

W szczególności czyli Z warunków zadania wynika, że dla pewnego mamy

Wówczas

czyli (gdzie w razie potrzeby przyjmujemy ). To stoi w sprzeczności z założeniem, że reszty z dzielenia przez wyrazów ciągu są parami różne.