[Rozgrzewka OM][MIX][Teoria liczb] Teoria liczb

[TomciO]

Założenie \(\displaystyle{ a \not \equiv 0}\) chyba nie jest potrzebne

[KPR]

Ukryta treść:    

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ą.

Liczby \(\displaystyle{ x,y,p,n,k}\) spełniają równość \(\displaystyle{ x^n+y^n=p^k}\) Pokazać, że jeśli \(\displaystyle{ n>1}\) jest nieparzyste, a \(\displaystyle{ p}\) pierwsze nieparzyste, to \(\displaystyle{ n}\) jest potęgą \(\displaystyle{ p}\).

[TomciO]

Nie napisałeś tego, ale zakładam, że liczby \(\displaystyle{ x, y}\) są naturalne - inaczej teza nie jest prawdziwa, np \(\displaystyle{ x=3, y=-2}\) i \(\displaystyle{ n=3}\).

Ukryta treść:    

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.

Ostrzegam, że następne zadanie może wymagać trochę pracy niech \(\displaystyle{ P}\) będzie wielomianem o współczynnikach całkowitych, który posiada pierwiastek rzeczywisty. Udowodnić, że istnieje nieskończenie wiele liczb pierwszych \(\displaystyle{ p}\) postaci \(\displaystyle{ 4k+3}\), które dzielą pewną z wartości: \(\displaystyle{ P(1), P(2), P(3), \ldots}\).

[Kartezjusz]

Zadanie:"nowe"Zauważmy,że wszystkie operacje poza pierwiastkowaniem są zachowane (mod p)
Pierwiastek istnieje wtedy i tylko wtedy jak liczba pod nim jest resztą kwadratową,a jak ją mamy to pierwiastek też zachowa się (mod p)

[K-mil]

Jak ktoś ma jakieś ciekawe zadania to może je tu wrzucić i odświeżymy trochę temat, z korzyścią dla wszystkich

[KPR]

Ok

Ukryta treść:    

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}\).

[ElEski]

Ukryta treść:    

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.

Jest jakiś blef tutaj? Bo trochę za prosto poszło. Poza tym, nie wiem, czy ktoś zrozumie, co tu napisałem, ale postaram się to poprawić estetycznie potem.

[Swistak]

Czemu powyższe nie działa:    

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

[ElEski]

Swistak,
Chodzi o to, że jeśli mamy cykl k-elementowy reszt z dzielenia kolejnych potęg dwójki przez n+1, to znaczy, że 2^s daje taką samą resztę, co 2^(s+mk) w dzieleniu przez n+1.
I teraz zakładamy indukcyjnie, że dla 1,2,3,...n teza zachodzi, czyli zachodzi w szczególności dla k (no, jak k jest potęgą dwójki, to ustaliliśmy że jesteśmy w domu).
A skoro zachodzi dla k, powiedzmy, że resztę z dzielenia przez k taką samą dają elementy a_l, a_(l+1),...
Wówczas na pewno również kolejnymi elementami są 2^a_l, 2^a_(l+1), ..., a one dają taką samą resztę z dzielenia przez n, co wynika z tego, że ich wykładniki dają tę samą resztę z dzielenia przez k.

Nie rozumiem chyba Twojej uwagi.

[KPR]

Ja chyba rozumiem o co chodzi:

Ukryta treść:    

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}\).

Rozwiązanie jest wg mnie dobre, moje jest podobne.

[ElEski]

KPR,
Tak, o to chodzi, właśnie myślałem, że mój zapis będzie beznadziejny, ale kościół ponaglał

[KPR]

Myślę, że możesz dać następne zadanko.

[ElEski]

\(\displaystyle{ x,y}\) to dodatnie liczby naturalne.
Okazało się, że liczby \(\displaystyle{ 15x+16y}\) i \(\displaystyle{ 16x-15y}\) to kwadraty liczb naturalnych. Jaką minimalną wartość może osiągnąć mniejszy z nich?

[Swistak]

Dobra, oczywiście rozwiązanie ElEski jest dobre, pomyliła mi się jedna rzecz, ale to tam nieważne xd

[Kartezjusz]

Co możemy powiedzieć o resztach z dzielenia różnicy kwadratów przez 31