Matematyka.pl

Oczywiście kongruencje możemy doprowadzić do postaci \(\displaystyle{ a(x+ \frac{b}{2a})^2- \frac{b^2-4ac}{4a} \equiv 0}\), czyli \(\displaystyle{ (x+ \frac{b}{2a})^2 \equiv\frac{b^2-4ac}{4}}\). Jeśli \(\displaystyle{ b^2-4ac}\) jest resztą kwadratową, to wynika stąd od razu rozwiązanie. Jeśli z kolei kongruencja ma rozwiązanie, to istnieje \(\displaystyle{ x}\), dla którego \(\displaystyle{ (x+ \frac{b}{2a})^2}\) przyjmuje wartość \(\displaystyle{ \frac{b^2-4ac}{4}}\). Zatem jest to reszta kwadratowa, więc po pomnożeniu przez 4 nadal jest resztą kwadratową.

Wykażemy, że \(\displaystyle{ p|n}\). Zauważmy, że ze wzoru \(\displaystyle{ x^n + y^n = (x+y)(\ldots)}\) wynika, że \(\displaystyle{ x+y}\) jest potęgą liczby \(\displaystyle{ p}\), tzn. \(\displaystyle{ x+y = p^l}\), możemy też założyć, że \(\displaystyle{ l > 0}\) bo w innej sytuacji sytuacja się trywializuje skoro \(\displaystyle{ x, y}\) są naturalne. Jasne też jest, że \(\displaystyle{ l < k}\).

Mamy \(\displaystyle{ p^k = x^n + y^n = x^n + (p^l - x)^n = \sum_{i=1}^{n} (-1)^{n-i}\binom{n}{i} p^{li}x^{n-i} = np^l + p^{l+1}A,}\) gdzie \(\displaystyle{ A}\) jest całkowite. Ponieważ \(\displaystyle{ k \geq l+1}\) to musimy też mieć \(\displaystyle{ p|n}\), a więc dowiedliśmy tego co chcieliśmy.

Zauważmy, że kończy to zadanie. Dlaczego? Jeśli \(\displaystyle{ n=mp}\) to mamy równanie \(\displaystyle{ x_0^m + y_0^m = p^k}\), gdzie \(\displaystyle{ x_0=x^p}\) i \(\displaystyle{ y_0=y^p}\). Analogicznie jak wcześniej pokazujemy, że \(\displaystyle{ p|m}\) i ... tak dalej w końcu musimy dojść do \(\displaystyle{ 1}\) czyli wyjściowa liczba była potęgą liczby \(\displaystyle{ p}\), co kończy dowód.

Dany jest ciąg określony wzorem \(\displaystyle{ a_1=2}\), \(\displaystyle{ a_n=2^{a_{n-1}}}\) dla \(\displaystyle{ n>1}\). Udowodnić, że dla każdego \(\displaystyle{ n}\) ciąg ten jest od pewnego miejsca stały modulo \(\displaystyle{ n}\).

Pokażemy, że jeśli teza zadania zachodzi dla wszystkich liczb do jakiegoś n włącznie, to zachodzi też dla n+1. Na pewno "cykl" reszt z dzielenia potęg dwójki przez n+1 ma długość maksymalnie n i/bo jego elementy to podzbiór zbioru 1,2,3,4...,n. Załóżmy, że długość tego cyklu to k<n+1.
Wówczas musimy pokazać, że to, co będzie w wykładniku od pewnego momentu, będzie dawało takie same reszty z dzielenia przez k. (chodzi o to, że każdy wyraz możemy przedstawić w postaci 2 do potęgi którejś). Przy czym jak tak przedstawiamy każdy kolejny element, to wychodzą potęgi dwójki o kolejnych wykładnikach 1,2,2^2, 2^2^2, ..., więc, jak założyliśmy indukcyjnie, od pewnego momentu będą dawać takie same reszty z dzielenia przez k, bo te wykładniki to są wyrazy naszego ciągu, prócz 1, a k<n+1. A zatem skoro od pewnego momentu dają takie same reszty z dzielenia przez k, to dają takie same reszty z dzielenia przez n.

Co prawda, nie czytałem całego, więc nie wiem, czy da się naprawić, ale na pewno złym uzasadnieniem faktu, że cykl reszt mod n+1 ma długość co najwyżej n, bo po pierwsze 0 też może być (ale wtedy już jesteśmy w domu, więc to praktycznie żadna usterka), ale co ważniejsze reszta z dzielenia k-tego wyrazu przez k+1 nie wyznacza nam reszty z dzielenia kolejnego wyrazu

Ciąg \(\displaystyle{ a_i=2^i}\) ma cykl długości k modulo n. Stąd jak mamy ciąg \(\displaystyle{ b_i=2^{c_i}}\), to żeby ciąg \(\displaystyle{ (b_i)}\) był stały modulo n wystarcza, żeby \(\displaystyle{ c_i}\) był stały modulo k. Czyli w naszym przypadku z tezy dla \(\displaystyle{ k}\) wynika teza dla \(\displaystyle{ n}\).