[MIX][Teoria liczb] Liczby pierwsze, liczby naturalne

[jerzozwierz]

Mały mix zadań z teorii liczb, raczej niełatwych, uznanych przeze mnie jako jedne z najładniejszych, jakie kiedykolwiek robiłem:

1.
Dana jest liczba całkowita \(\displaystyle{ n \ge 2}\). Udowodnić, że jeżeli \(\displaystyle{ k^2+k+n}\) jest pierwsza dla wszystkich całkowitych \(\displaystyle{ k}\) takich, że \(\displaystyle{ 0 \le k \le \sqrt{ \frac{n}{3} }}\), to \(\displaystyle{ k^2 + k +n}\) jest pierwsza dla wszystkich całkowitych \(\displaystyle{ k}\) takich, że \(\displaystyle{ 0 \le k \le n-2}\).

2.
Dana jest nieparzysta liczba pierwsza \(\displaystyle{ p}\) i liczby całkowite \(\displaystyle{ a,b,c}\). Wyznaczyć \(\displaystyle{ \prod_{k=0}^{p-1} (ak^2+bk+c) \ (mod \ p)}\).

3.
Dana jest liczba pierwsza \(\displaystyle{ p \ge 5}\). Udowodnić, że liczba \(\displaystyle{ x^{p-1} + x^{p-2} + ... + x + 2}\) nie jest kwadratem liczby naturalnej dla żadnej liczby całkowitej \(\displaystyle{ x}\).

4.
Dla danego \(\displaystyle{ h = 2^r}\), gdzie \(\displaystyle{ r \ge 0}\), wyznaczyć wszystkie liczby naturalne \(\displaystyle{ k}\), dla których istnieje \(\displaystyle{ m>1}\) nieparzyste oraz liczba naturalna \(\displaystyle{ n}\) taka, że \(\displaystyle{ k | m^h - 1}\) oraz \(\displaystyle{ m | n^{ \frac{m^h - 1}{k}} + 1}\).

5.
Dana jest liczba naturalna \(\displaystyle{ k}\). Udowodnić, że liczb pierwszych postaci \(\displaystyle{ 2^k m + 1}\) jest nieskończenie wiele.

6.
Udowodnić, że istnieje nieskończenie wiele liczb naturalnych \(\displaystyle{ n}\) takich, że liczba \(\displaystyle{ n^2 + 1}\) ma dzielnik pierwszy większy od \(\displaystyle{ 2n + \sqrt{2n}}\).

7.
Znaleźć wszystkie naturalne n, dla których \(\displaystyle{ n^2 | 2^n + 1}\).

8.
Rozstrzygnąć, jakie liczby naturalne \(\displaystyle{ a}\) mają następującą własność: istnieje nieskończenie wiele takich \(\displaystyle{ n}\), że \(\displaystyle{ n^2 | a^n - 1}\).

9.
Dana jest nieparzysta liczba pierwsza \(\displaystyle{ p}\) i liczby całkowite \(\displaystyle{ a,b,c}\) spełniające warunek \(\displaystyle{ b^2 \not\equiv 4ac \ (mod \ p)}\). Udowodnić, że \(\displaystyle{ \sum_{k=0}^{p-1} \left( \frac{ak^2+bk+c}{p} \right) = - \left( \frac{a}{p} \right)}\), gdzie \(\displaystyle{ \left( \frac{x}{p} \right)}\) oznacza symbol Legendre'a.

10.
Niech \(\displaystyle{ a}\) będzie liczbą całkowitą. Wykazać, że istnieje nieskończenie wiele liczb pierwszych \(\displaystyle{ p}\), dla których \(\displaystyle{ p | n^2 + 3}\) oraz \(\displaystyle{ p | m^3 - a}\) dla pewnych całkowitych \(\displaystyle{ m,n}\).

11.
Dane są liczby całkowite \(\displaystyle{ m,n}\) spełniające \(\displaystyle{ 0<n<m}\). Udowodnić, że jeśli liczby \(\displaystyle{ a^m - 1}\) i \(\displaystyle{ a^n - 1}\) mają te same dzielniki pierwsze, to \(\displaystyle{ a+1}\) jest potęgą dwójki.

Życzę miłego rozwiązywania i zachęcam do dzielenia się swoimi rozwiązaniami (:

[KPR]

5:    

Udowodnimy przez indukcję, że jeżeli \(\displaystyle{ p}\) jest nieparzystą liczbą pierwszą i -1 jest \(\displaystyle{ 2^k}\)-tą potęgą modulo \(\displaystyle{ p}\), to \(\displaystyle{ p\equiv 1 \mod{2^{k+1}}}\). Dla \(\displaystyle{ k=1}\) teza jest oczywista. Załóżmy teraz, że teza zachodzi dla pewnego \(\displaystyle{ k \geq 1}\). Niech \(\displaystyle{ p}\) będzie nieparzystą liczbą pierwszą taką, że -1 jest \(\displaystyle{ 2^{k+1}}\)-szą potęgą modulo \(\displaystyle{ p}\). Wtedy \(\displaystyle{ -1\equiv x^{2^{k+1}} \mod {p}}\) dla pewnej reszty \(\displaystyle{ x}\). Ponieważ na mocy założenia indukcyjnego \(\displaystyle{ p\equiv 1 \mod{2^{k+1}}}\), to podnieśmy to równanie obustronnie do potęgi \(\displaystyle{ \frac{p-1}{2^{k+1}}}\). Otrzymujemy \(\displaystyle{ (-1)^{\frac{p-1}{2^{k+1}}}\equiv x^{p-1} \mod {p}}\). Z małego twierdzenia Fermata prawa strona przystaje do 1 modulo \(\displaystyle{ p}\), zatem \(\displaystyle{ \frac{p-1}{2^{k+1}}}\) jest parzyste, aby \(\displaystyle{ (-1)^{\frac{p-1}{2^{k+1}}}\equiv 1 \mod {p}}\), co kończy dowód tezy indukcyjnej.

Ponieważ dla każdej liczby pierwszej \(\displaystyle{ p}\) dzielącej \(\displaystyle{ 2^{2^k}}\), \(\displaystyle{ -1\equiv 2^{2^k} \mod {p}}\), to \(\displaystyle{ p\equiv 1 \mod {2^{k+1}}}\).
Zauważmy, że każde dwie liczby postaci \(\displaystyle{ 2^{2^m}+1}\) i \(\displaystyle{ 2^{2^n}+1}\), gdzie \(\displaystyle{ m \neq m}\), są względnie pierwsze. Istotnie, załóżmy, że \(\displaystyle{ m<n}\). Wtedy \(\displaystyle{ 2^{2^m}+1 | 2^{2^{m+1}}-1 | 2^{2^n}-1=2^{2^n}+1-2}\), a ponieważ \(\displaystyle{ 2^{2^n}+1\perp 2}\), to \(\displaystyle{ 2^{2^n}+1\perp 2^{2^m}+1}\). Zatem w szczególności jeśli \(\displaystyle{ p_1,p_2, \dots}\) będą takimi liczbami pierwszymi, że \(\displaystyle{ p_i|2^{2^{k-2+i}}+1}\), to wszystkie \(\displaystyle{ p_i}\) będą różne, a ponadto, na mocy powyższej indukcji, wszystkie będą przystawały do 1 \(\displaystyle{ \mod{2^k}}\), c.k.d.

Jeszcze jedno rozwiązanie:

Ukryta treść:    

twierdzenie Dirichleta

Osobiście też uważam to zadanie za ładne.

[Swistak]

Jak mogłeś zapomnieć o tych dwóch epickich zadaniach z ostatniego Zwardonia!?
Rozwiąż w naturalnych: \(\displaystyle{ 2^x+3^y=5^z}\)
oraz
Czy istnieje ciąg arytmetyczny liczb naturalnych o różnicy niepodzielnej przez 10, w którym suma cyfr każdego wyrazu jest co najmniej \(\displaystyle{ 2011^{2011}}\)?

Nie no żarty na bok. Bardzo polecam ten mix, to naprawdę dobrze wyselekcjonowane zadania z tego, co w matmie najfajniejsze (przynajmniej na poziomie OMa/IMO), czyli zarąbistej teorii liczb ! Grzechem będzie zostawić ten temat bez rozwiązania któregoś z tych zadań .

[KPR]

2:    

Wszystko modulo \(\displaystyle{ p}\).
Jeśli \(\displaystyle{ a=0}\), to mamy dwa przypadki:
\(\displaystyle{ b=0}\), \(\displaystyle{ c\neq 0}\) - w tym wypadku iloczyn to \(\displaystyle{ c^p}\).
\(\displaystyle{ b\neq0}\) lub \(\displaystyle{ c=0}\) - wtedy istnieje wyraz równy 0 - iloczyn wynosi 0.
Załóżmy zatem, że \(\displaystyle{ a\neq 0}\). Wtedy \(\displaystyle{ ax^2+bx+c=a(x+\frac{b}{2a})^2+\frac{-\Delta}{4a}}\) (ach ta delta). Jeśli \(\displaystyle{ x\neq -\frac{b}{2a}}\), to istnieje taki \(\displaystyle{ y}\) (równy \(\displaystyle{ -\frac{b}{4a}-x}\)), dla którego \(\displaystyle{ ax^2+bx+c=ay^2+by+c}\). Zatem pomijając \(\displaystyle{ x=-\frac{b}{2a}}\), funkcja \(\displaystyle{ ax^2+bx+c}\) przyjmuje tylko \(\displaystyle{ \frac{p-1}{2}}\) wartości. Rozważmy wielomian \(\displaystyle{ (x+\frac{\Delta}{4a})^{\frac{p-1}{2}}-1}\). Dla dowolnego \(\displaystyle{ x\neq -\frac{b}{2a}}\) ten wielomian się zeruje, a ponieważ jest stopnia \(\displaystyle{ \frac{p-1}{2}}\), to ze wzorów Viete'a iloczyn wszystkich reszt tej postaci wynosi \(\displaystyle{ (-1)^{\frac{p-1}{2}}\left(\left(\frac{\Delta}{4a}\right)^{\frac{p-1}{2}}-1\right)}\). Jak pomnożymy to przez wartość trójmianu dla \(\displaystyle{ x=-\frac{b}{2a}}\), czyli \(\displaystyle{ \frac{-\Delta}{4a}}\), to dostajemy odpowiedź:
\(\displaystyle{ (-1)^{\frac{p+1}{2}}\left(\left(\frac{b^2-4ac}{4a}\right)^{\frac{p+1}{2}}+\frac{4ac-b^2}{4a}\right)}\)

[limes123]

10.

Ukryta treść:    

Zajmiemy sie przypadkiem \(\displaystyle{ a\neq 0}\). Zamiast drugiego wyrazenia rozwazmy to wyrazenie przemnozone przez 3 i wezmy m postaci \(\displaystyle{ -3ak^2}\) dla k calkowitego. Wtedy drugie wyrazenie mozemy zapisac tak:
\(\displaystyle{ -a((9ak^3)^2+3)}\) i juz widac jakie trzeba dobrac n. To ze wielomian z[x] dodatniego stopnia ma nieskonczenie wiele dzielnikow pierwszych juz bylo duzo razy na forum.

Zadanie ma uogolnienie:

Ukryta treść:    

Dla wielomianow \(\displaystyle{ p_1,...,p_n\in \mathbb{Z}[X]}\) stopni >0 zamiast tylko dwoch okreslonych wyrazen. Do dowodu wystarczy lemat, ze dla wielomianow q, r w Z[X] istnieja wielomiany \(\displaystyle{ s, t}\) w Z[X] takie, ze \(\displaystyle{ q(s(x))}\) i \(\displaystyle{ r(t(x))}\) nie sa wzglednie pierwsze (czyli to samo co wyzej, tylko w przypadku ogolnym). By to pokazac bierzemy jakies pierwiastki x, y odpowiednio q i r i szukamy takiego z, ze \(\displaystyle{ s(z)=x}\) i \(\displaystyle{ t(z)=y}\). Jest takie tw, ze jesli a,b to liczby algebraiczne nad Q, to istnieje takie c algebraiczne, ze \(\displaystyle{ \mathbb{Q}(a,b)=\mathbb{Q}(c)}\). Jak juz wiemy, ze dwa wielomiany maja wspolny pierwiastek bedacy liczba algebraiczna, to oba te wielomiany sa podzielne przez wielomian minimalny tej liczby, czyli nie sa wzglednie pierwsze. Dowod tego glownego tw z ktorego korzystam wrzuce jutro.

[jerzozwierz]

@Kamil: pomysł dobry, tylko masz sporo błędów rachunkowych i rzeczowych (ale można się domyślić o co chodzi). Polecam przejrzenie całego dowodu krok po kroku i napisanie tak jak powinno być.

[Swistak]

zad. 3:    

Załóżmy wbrew tezie, że to wyrażenie jest równe \(\displaystyle{ k^2}\) dla pewnego całkowitego \(\displaystyle{ k}\). Po prostych przekształceniach otrzymujemy \(\displaystyle{ \frac{x^p-1}{x-1}=(k-1)(k+1)}\)
Niech \(\displaystyle{ r}\) będzie jakimś dzielnikiem pierwszym \(\displaystyle{ (k-1)(k+1)}\). Musi ono wtedy dzielić \(\displaystyle{ \frac{x^p-1}{x-1}}\).
Załóżmy najpierw, że \(\displaystyle{ r \nmid x-1}\). Mamy wtedy także \(\displaystyle{ r|x^p-1}\), zatem rząd \(\displaystyle{ x}\) modulo \(\displaystyle{ r}\) dzieli \(\displaystyle{ p}\), ale nie dzieli \(\displaystyle{ 1}\) stąd wniosek, że jest on równy \(\displaystyle{ p}\). Mamy oczywiście \(\displaystyle{ r\nmid x}\), zatem \(\displaystyle{ r|x^{r-1}-1}\), zatem \(\displaystyle{ p|r-1}\), zatem każdy dzielnik pierwszy tych liczb taki, że \(\displaystyle{ r\nmid x-1}\) przystaje do \(\displaystyle{ 1 \mod \ p}\).
Załóżmy teraz, że jest jakiś dzielnik pierwszy \(\displaystyle{ q}\) tych liczb taki, że \(\displaystyle{ q|x-1}\). Możemy wtedy napisać \(\displaystyle{ x=lq^{\alpha}+1}\), gdzie \(\displaystyle{ l}\) jest niepodzielne przez \(\displaystyle{ q}\). Aby zachodziło \(\displaystyle{ q|\frac{x^p-1}{x-1}}\), to musi zachodzić \(\displaystyle{ q^{\alpha+1}|x^p-1}\) Rozpatrzmy kiedy jest to możliwe. Mamy wtedy \(\displaystyle{ x^p-1=(lq^{\alpha}+1)^p-1\equiv _{q^{\alpha+1}}plq^{\alpha}}\). Zatem \(\displaystyle{ q|x^p-1 \Rightarrow q|pl}\), ale \(\displaystyle{ l}\) było niepodzielne przez \(\displaystyle{ q}\), zatem musi być \(\displaystyle{ p=q}\). Poza tym można wysnuć wniosek, że \(\displaystyle{ q^2}\) już nie dzieli tej liczby, ale nie będzie nam to potrzebne.
Otrzymaliśmy zatem wniosek, że każdy dzielnik pierwszy \(\displaystyle{ (k-1)(k+1)}\) daje resztę \(\displaystyle{ 0}\) lub \(\displaystyle{ 1}\) z dzielenia przez \(\displaystyle{ p}\), a iloczyn liczb takiej postaci też daje którąś z tych reszt \(\displaystyle{ \mod \ p}\), zatem i \(\displaystyle{ k-1}\) i \(\displaystyle{ k+1}\) też takie dają, ale skoro różnią się o \(\displaystyle{ 2}\) i \(\displaystyle{ p \ge 5}\), to otrzymujemy sprzeczność.

To ode mnie tyle w tym temacie, bo gdy mix został napisany nie znałem rozw. tylko 2, 3 i 10, 2 wykminiłem, ale Kamil mnie uprzedził, a 10 już jest . Nie będę wam psuć zabawy, bo naprawdę warto się pobawić z tymi zadankami .

[KPR]

Jerzu, o którym zadaniu mówisz?
A, chyba 2.

Ukryta treść:    

2 błędy zauważyłem, a nie mogę edytować: w ostatnim wyrażeniu powinno być \(\displaystyle{ (-1)^{\frac{p-1}{2}}\left(\left( \frac{b^2-4ac}{2a} \right) ^{\frac{p+1}{2}}+\frac{b^2-4ac}{2a}\right)}\)

[mol_ksiazkowy]

ad 7

Ukryta treść:    

IMO 90 (Jeśli ułamek \(\displaystyle{ \frac{2^n+1}{n^2}}\) wyraża liczbę całkowitą, to \(\displaystyle{ n}\) musi być nieparzyste. \(\displaystyle{ n=3}\) spełnia warunki zadania. Gdy
\(\displaystyle{ 3^k}\) jest największą potęgą trójki dzielącą \(\displaystyle{ n}\), to na mocy lematu:

Jeśli \(\displaystyle{ 2^n \equiv -1 \ (mod \ 3^k)}\) to \(\displaystyle{ 3^{k-1}}\) jest dzielnikiem \(\displaystyle{ n}\)

musi być \(\displaystyle{ k=1}\).
Niech \(\displaystyle{ p>3}\) będzie najmniejszym dzielnikiem pierwszym \(\displaystyle{ n}\) i niech \(\displaystyle{ d}\) będzie najmniejszą liczba naturalną: \(\displaystyle{ 2^d \equiv 1 \ (mod \ p)}\).
skoro \(\displaystyle{ 2^n \equiv -1 \ (mod \ p)}\), \(\displaystyle{ d}\) musi być dzielnikiem \(\displaystyle{ 2n}\). Jednak \(\displaystyle{ d}\) nie może być nieparzyste (bo wtedy \(\displaystyle{ d}\) jest dzielnikiem \(\displaystyle{ n}\), co przeczy powyższej kongruencji).
Zatem \(\displaystyle{ d=2d_1}\) i wtedy \(\displaystyle{ d_1}\) jest dzielnikiem \(\displaystyle{ n}\). Jednak \(\displaystyle{ 2d_1}\) jest dzielnikiem \(\displaystyle{ p-1}\). tj.
\(\displaystyle{ d_1 \leq \frac{p-1}{2}<p}\). czyli \(\displaystyle{ d_1=1}\) (co jest sprzeczne z tym że \(\displaystyle{ p>3}\)) lub \(\displaystyle{ d_1=3}\). Wtedy \(\displaystyle{ d=6}\) a więc
\(\displaystyle{ 2^6 \equiv 1 \ (mod \ p)}\) tj. \(\displaystyle{ p=7}\). Jednak przeczy to okresleniu \(\displaystyle{ d}\), gdyż \(\displaystyle{ 2^3 \equiv 1 \ (mod \ 7)}\)
Tak więc postulowana liczba pierwsza \(\displaystyle{ p}\) nie istnieje: tym samym \(\displaystyle{ n=3}\) stanowi wynik zadania

[KPR]

11:    

Dla \(\displaystyle{ a=1}\) wiadomo.
Niech \(\displaystyle{ d=NWD(m,n)}\). Łatwo dowieść, że \(\displaystyle{ NWD(a^m-1,a^n-1)=a^d-1}\) (zapuścić taki algorytm Euklidesa). Zatem \(\displaystyle{ a^d-1}\) ma takie same dzielniki pierwsze, co \(\displaystyle{ a^m-1}\). Niech \(\displaystyle{ m=dk}\) i \(\displaystyle{ n=dl}\). Jeżeli \(\displaystyle{ a}\) jest parzyste, to z LTE mamy \(\displaystyle{ a^m-1=k(a^d-1)}\), czyli \(\displaystyle{ a^d(a^{kd-d}-k)+k-1=0}\). Jednakże lewa strona jest zawsze nieujemna dla \(\displaystyle{ a\ge 2}\) co wynika z nierówności \(\displaystyle{ 2^{k-1}\ge k}\). Może być równa 0 jedynie wtedy, gdy \(\displaystyle{ k=1}\). Analogicznie \(\displaystyle{ l=1}\), co jest sprzecznością. Zatem \(\displaystyle{ a}\) jest nieparzyste. Jeżeli \(\displaystyle{ d}\) jest parzyste, to \(\displaystyle{ 4|a^d-1}\) i dajemy ten sam argument z LTE. To samo, jeśli obie liczby \(\displaystyle{ k}\) lub \(\displaystyle{ l}\) są nieparzyste (bo co najmniej jedna jest większa od 1). Zatem jedna jest parzysta, druga nieparzysta, to samo z \(\displaystyle{ m}\) i \(\displaystyle{ n}\). Zakładamy, że \(\displaystyle{ m}\) jest parzyste. Wtedy \(\displaystyle{ a+1|a^m-1}\) i dla każdego \(\displaystyle{ p|a+1}\) mamy \(\displaystyle{ p|a^n-1}\), ale ponieważ \(\displaystyle{ n}\) jest nieparzyste, to \(\displaystyle{ a^n-1\equiv -2\pmod{p}}\), więc \(\displaystyle{ p=2}\), c.k.d.