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

[arek1357]

Chyba nic

[adamm]

Zadanie eleskiego to IMO 96' , niech ktoś wrzuci coś mniej pałkarskiego.

[K-mil]

niech ktoś wrzuci coś mniej pałkarskiego.

Niech \(\displaystyle{ p}\) będzie taką liczbą pierwszą, że \(\displaystyle{ 2p+1}\) również jest pierwsza. Rozwiąząc w liczbach całkowitych równanie \(\displaystyle{ x ^{p} + 2y ^{p} + 5z ^{p} = 0}\)

[KPR]

Ukryta treść:    

Ponieważ \(\displaystyle{ 2p+1}\) jest pierwsza, to dla każdego \(\displaystyle{ a\in\mathbb{Z}}\) niepodzielnego przez \(\displaystyle{ 2p+1}\) zachodzi \(\displaystyle{ a^{2p}\equiv 1 \bmod{2p+1}}\), czyli \(\displaystyle{ a^{p}\equiv 1 \bmod{2p+1}}\) lub \(\displaystyle{ a^{p}\equiv -1 \bmod{2p+1}}\). Zatem w naszym równaniu każda z liczb \(\displaystyle{ x^p,y^p,z^p}\) przystaje do 1,0 lub -1 modulo \(\displaystyle{ 2p+1}\). Łatwo zauważyć, że muszą być same 0. Czyli \(\displaystyle{ x,y,z}\) są podzielne przez \(\displaystyle{ 2p+1}\). Robimy nieskończone schodzenie i dostajemy \(\displaystyle{ x=y=z=0}\).

Hmm, coś za prosto poszło, nie wykorzystałem założenia, że \(\displaystyle{ p}\) jest pierwsze.-- 20 gru 2011, o 18:31 --To jeśli jest dobrze, to wrzucam następne zadanko:
Czy istnieje zbiór \(\displaystyle{ X}\) składający się liczb całkowitych taki, że dla każdego \(\displaystyle{ n\in\mathbb{Z}}\) istnieje dokładnie jedna para \(\displaystyle{ (a,b)\in X^2}\) taka, że \(\displaystyle{ 2a+b=n}\)?

[TomciO]

Hmm, coś za prosto poszło, nie wykorzystałem założenia, że \(\displaystyle{ p}\) jest pierwsze.

Rzeczywiście za prosto.

Ukryta treść:    

A \(\displaystyle{ 0 + 2 + 5}\)?

[KPR]

Ukryta treść:    

Ten przypadek idzie modulo 9.

[Swistak]

Czy istnieje zbiór \(\displaystyle{ X}\) składający się liczb całkowitych taki, że dla każdego \(\displaystyle{ n\in\mathbb{Z}}\) istnieje dokładnie jedna para \(\displaystyle{ (a,b)\in X^2}\) taka, że \(\displaystyle{ 2a+b=n}\)?

To jeszcze nie jest rozwiązanie, ale raczej duży krok w stronę ewentualnej konstrukcji.
Jeżeli się nie mylę, to gdyby miało być \(\displaystyle{ n \in \mathbb{N} \cup \{ 0 \}}\), to ładnie pasuje zbiór wszystkich liczb nieujemnych całkowitych, w których wszystkie jedynki w zapisie binarnym stoją na nieparzystych pozycjach. Wtedy zbiór z 2 razy większymi liczbami to zbiór wszystkich liczb nieujemnych całkowitych, w których wszystkie jedynki stoją na parzystych miejscach, a każda liczba całkowita nieujemna przedstawia się jednoznacznie jako suma jednej takiej i jednej takiej liczby.
Można z tym jeszcze zrobić takie szacher-machery, że jak się do każdej liczby w tym zbiorze doda liczbę \(\displaystyle{ r}\), to zbiór liczb, które otrzymamy będzie to zbiór liczb całkowitych \(\displaystyle{ \geq 3r}\) (\(\displaystyle{ r}\) może oczywiście być ujemne), a jak się pomnoży wszystko razy \(\displaystyle{ -1}\), to też wiadomo, co się stanie.
Ma ktoś pomysł, jak to rozciągnąć w obie nieskończoności?

[Oceansoul]

Może coś takiego:
Niech \(\displaystyle{ X}\) będzie zbiorem zaproponowanym przez Świstaka. Oczywiście każdy z jego elementów jest postaci \(\displaystyle{ 4k}\) lub \(\displaystyle{ 4k+1}\) .Możemy więc \(\displaystyle{ Y}\) zdefiniować jako obraz \(\displaystyle{ X}\) względem funkcji \(\displaystyle{ f(x)}\)= \(\displaystyle{ \begin{cases} x/4 \iff 4|x \\ -(x-1)/4 \iff 4 \nmid x \end{cases}}\).
Dla każdego \(\displaystyle{ n \in \mathbb N}\) istnieją takie \(\displaystyle{ x_{i},x_{j} \in X}\), że:
\(\displaystyle{ 4n = 2x_{i}+x_{j}}\)
\(\displaystyle{ n = \frac{x_{i}}{2} + \frac{x_{j}}{4}}\)
\(\displaystyle{ n = 2y_{i}+y_{j}}\); \(\displaystyle{ y_{i}, y_{j} \in Y}\)
Dla każdego \(\displaystyle{ n \in \mathbb N}\) mamy również takie \(\displaystyle{ x_{i},x_{j} \in X}\), że:
\(\displaystyle{ 4n+3 = 2x_{i}+x_{j}}\)
\(\displaystyle{ -4n = -2x_{i}+2-x_{j}+1}\)
\(\displaystyle{ -n = -2\frac{x_{i}-1}{4} - \frac{x_{j}-1}{4}}\)
\(\displaystyle{ -n = 2y_{i}+y_{j}}\); \(\displaystyle{ y_{i}, y_{j} \in Y}\)
A więc zbiór \(\displaystyle{ Y}\) spełnie warunki zadania.

[Ponewor]

Może by tak reaktywować temat?

[chomikchomik]

ok, pozwolicie, że wrzucę swoje (niestety jeszcze nie rozwiązane) zadanie:
dana jest liczba całkowita dodatnia d. niech S oznacza zbiór liczb całkowitych, które można przedstawić w postaci \(\displaystyle{ x^{2} + dy ^{2}}\) gdzie x, y są całkowite
a) udowodnić implikację \(\displaystyle{ a;b \in S \Rightarrow ab \in S}\)
b) udowodnić, że jeśli \(\displaystyle{ a;p \in S}\) oraz p jest liczbą pierwszą, która dzieli a, to \(\displaystyle{ a/p \in S}\)
c) załóżmy, że równanie: \(\displaystyle{ p=x ^{2} + dy ^{2}}\) , gdzie p jest daną liczbą pierwszą, ma rozwiązanie w liczbach całkowitych x, y. udowodnić, że dla d=1 istnieją dwa takie rozwiązania, a dla d nie mniejszego od 2 istnieje tylko jedno.

zadanie pochodzi z fajnego (wg. mnie) zbioru z teorii liczb, który znaleźć można tu:
... SatoNT.pdf
ale rozwiązania do tego akurat zadanie nie ma.

i jeszcze jedno, nie, żebym spamował, ale ożywię trochę ten temat, wrzucając fajny utwór.
filmik nie jest mój, żeby nie było.

[Ponewor]

a):    

tożsamość Diofantosa

b):    

\(\displaystyle{ a=x^{2}+dy^{2} \wedge p=m^{2}+dn^{2} \wedge p\mid a}\)
Zauważmy, że \(\displaystyle{ p\nmid d}\). W przeciwnym razie \(\displaystyle{ p=m^{2}+dn^{2} \ge m^{2}+pn^{2} > p}\)
\(\displaystyle{ m^{2}a-x^{2}p=m^{2}\left( x^{2}+dy^{2}\right)-x^{2}\left( m^{2}+dn^{2}\right)=dm^{2}y^{2}-dx^{2}n^{2}=d \left( my-xn \right) \left( my+xn \right)}\)
Stąd \(\displaystyle{ p \mid my \mp xn}\)
\(\displaystyle{ ap=\left( x^{2}+dy^{2}\right)\left( m^{2}+dn^{2}\right)= \left( xm \pm dyn \right) ^{2}+d\left( xn \mp ym\right)^{2}}\)
Stąd \(\displaystyle{ p \mid xm \pm dyn}\) i:
\(\displaystyle{ \frac{a}{p}= \left( \frac{xm \pm dyn}{p} \right) ^{2}+d\left(\frac{ xn \mp ym}{p}\right)^{2}}\)

Zaś z \(\displaystyle{ c)}\) jest coś nie tak, bo to nieprawda na mocy tego dowodu.
Jak ktoś chce, to niech ogarnie o co chodzi z c). Żeby rozruszać temat, dam parę zadań:

Udowodnij, że hipoteza liczb bliźniaczych równoważna jest następującej hipotezie:
Istnieje nieskończenie wiele liczb całkowitych nieprzedstawialnych w żadnej z poniższych postaci, przy całkowitych \(\displaystyle{ a}\) i \(\displaystyle{ b}\):
\(\displaystyle{ 6uv+u+v,\;\; 6uv+u-v,\;\; 6uv-u+v,\;\; 6uv-u-v}\)

Pokazać, że istnieje nieskończenie wiele liczb złożonych \(\displaystyle{ n}\), takich, że \(\displaystyle{ n \mid \left( 3^{n-1}-2^{n-1}\right)}\).

Znaleźć wszystkie takie liczby naturalne \(\displaystyle{ n}\), że każda liczba, której zapis w systemie dziesiętnym składa się z dokładnie \(\displaystyle{ n-1}\) jedynek i jednej siódemki jest liczbą pierwszą.

[Vax]

1:    

Rozumiem, że chodzi o \(\displaystyle{ a,b}\) (tudzież \(\displaystyle{ u,v}\)) różne od \(\displaystyle{ 0}\)? ;p Na początku \(\displaystyle{ \Rightarrow}\), załóżmy, że \(\displaystyle{ 6n+1 \in \mathbb{P}}\) oraz \(\displaystyle{ 6n-1 \in \mathbb{P}}\), pokażemy, że wówczas \(\displaystyle{ n}\) nie da się przedstawić w tej postaci, istotnie, jakby dla pewnych \(\displaystyle{ x,y}\) było \(\displaystyle{ n = 6xy+x+y \iff 6n+1 = (6x+1)(6y+1)}\) sprzeczność, analogicznie dostajemy sprzeczność dla tych 3 kolejnych wyrażeń.

Teraz \(\displaystyle{ \Leftarrow}\). Załóżmy, że mamy pewne \(\displaystyle{ n}\) którego nie da się przedstawić w żadnej z danych postaci dla całkowitych dodatnich \(\displaystyle{ x,y}\), jak wyżej łatwo dochodzimy do tego, że:

\(\displaystyle{ \begin{cases} 6n+1 \neq (6x+1)(6y+1) \\ 6n-1 \neq (6x-1)(6y+1) \end{cases}}\)

Skąd od razu \(\displaystyle{ 6n+1 \in \mathbb{P} \wedge 6n-1 \in \mathbb{P}}\), bo jeżeli byłyby takie \(\displaystyle{ a,b > 1}\), że \(\displaystyle{ 6n+1 = ab}\), to \(\displaystyle{ a,b}\) nie mogłyby być różne \(\displaystyle{ \pmod{6}}\), jeżeli są równe \(\displaystyle{ 1\pmod{6}}\) to sprzeczność, a jeżeli obie są równe \(\displaystyle{ -1\pmod{6}}\), to wywalamy jakiś dzielnik pierwszy liczby \(\displaystyle{ b}\) równy \(\displaystyle{ -1\pmod{6}}\) do \(\displaystyle{ a}\) i dostajemy oba czynniki równe \(\displaystyle{ 1\pmod{6}}\) więc sprzeczność, podobnie pokazujemy, że \(\displaystyle{ 6n-1 \in \mathbb{P}}\)

2:    

Pokażemy, że \(\displaystyle{ n=3^{2^k}-2^{2^k}}\) działa. Istotnie, ponieważ \(\displaystyle{ 3^{2^k} \equiv 2^{2^k} \pmod{3^{2^k}-2^{2^k}}}\) to wystarczy pokazać, że \(\displaystyle{ 2^k \mid 3^{2^k}-1}\) a to jest w szczególności prawdą, bo z LTE \(\displaystyle{ v_2(3^{2^k}-(-1)^{2^k}) = v_2(4) + v_2(2^k) = k+2}\)

3:    

Dla \(\displaystyle{ n=1,2}\) sprawdzamy, że teza działa. Pokażemy, że dla żadnego \(\displaystyle{ n \ge 3}\) nie działa. Łatwo można policzyć, że:

\(\displaystyle{ \underbrace{11\ldots 1}_{l}7\underbrace{11\ldots 1}_{n-l-1} = \frac{10^n-1+54\cdot 10^{n-l-1}}{9}}\)

Dla każdego \(\displaystyle{ l \in [0;n-1]}\) dana liczba ma być pierwsza. Zauważmy, że jeżeli \(\displaystyle{ 3|n}\) to dana liczba jest podzielna przez \(\displaystyle{ 3}\), więc sprzeczność, skąd zostaje do rozpatrzenia \(\displaystyle{ n \in \lbrace 1,2,4,5\rbrace \pmod{6}}\).

Wstawmy \(\displaystyle{ l=n-1}\), wówczas patrząc na licznik \(\displaystyle{ \pmod{7}}\) dostajemy \(\displaystyle{ 10^n+53 \equiv 3^n+4 \pmod{7}}\), jeżeli \(\displaystyle{ n=6k+1}\) to \(\displaystyle{ 3^n+4 \equiv 3\cdot (3^6)^k+4 \equiv 3+4 \equiv 0\pmod{7}}\) sprzeczność.

Wstawmy \(\displaystyle{ l=n-3}\), wówczas \(\displaystyle{ \pmod{13}}\) dostajemy \(\displaystyle{ 10^n-1+5400 \equiv 10^n+4 \pmod{13}}\), jeżeli \(\displaystyle{ n=6k+2}\), to \(\displaystyle{ 10^n+4 \equiv 100 \cdot (10^{3})^{2k}+4 \equiv 9+4 \equiv 0\pmod{13}}\) sprzeczność.

Wstawmy \(\displaystyle{ l=0}\), wówczas licznik \(\displaystyle{ \pmod{13}}\) wynosi \(\displaystyle{ 64\cdot 10^{n-1}-1 \equiv -10^{n-1}-1\pmod{13}}\), jeżeli \(\displaystyle{ n=6k+4}\) to \(\displaystyle{ -10^{n-1}-1 \equiv -(10^3)^{2k+1}-1 \equiv 1-1 \equiv 0\pmod{13}}\) sprzeczność.

Wstawmy \(\displaystyle{ l=2}\), wówczas \(\displaystyle{ \pmod{7}}\) dostajemy \(\displaystyle{ 10^n-1+54\cdot 10^{n-3} \equiv 10^{n-3}\cdot 1054-1 \equiv 3^{n-3}\cdot 4-1 \equiv -3^{n-2}-1\pmod{7}}\), jeżeli \(\displaystyle{ n=6k+5}\) to \(\displaystyle{ -3^{n-2}-1 \equiv -(3^3)^{2k+1}-1 \equiv 1-1 \equiv 0\pmod{7}}\) sprzeczność.

Pokazać, że \(\displaystyle{ t,t+2}\) są liczbami pierwszymi wtedy i tylko wtedy, gdy:

\(\displaystyle{ t(t+2) \mid 4((t-1)!+1)+t}\)

[MadJack]

Hm, coś za łatwo poszło, więc może być blef.

Ukryta treść:    

Załóżmy pierwsze, że \(\displaystyle{ t}\) i \(\displaystyle{ t+2}\) są pierwsze. Mamy oczywiście \(\displaystyle{ t \mid t}\) i z twierdzenia Wilsona \(\displaystyle{ t \mid (t-1)!+1}\), a zatem \(\displaystyle{ t \mid 4((t-1)!+1)+t}\).
Z twierdzenia Wilsona można też łatwo wyprowadzić, że \(\displaystyle{ (t-1-n)!n!+(-1)^n \equiv 0 \pmod{t}}\) dla \(\displaystyle{ 0 \le n \le t}\) i \(\displaystyle{ n}\) całkowitego.
Kładąc zatem \(\displaystyle{ n=2}\) i \(\displaystyle{ t:=t+2}\), mamy: \(\displaystyle{ 2(t-1)!+1 \equiv 0 \pmod{t+2}}\). Zatem \(\displaystyle{ 4((t-1)!+1)+t=2(2(t-1)!+1)+(t+2) \equiv 0 \pmod{t+2}}\), co dowodzi pierwszej części twierdzenia, gdyż oczywiście \(\displaystyle{ t}\) i \(\displaystyle{ t+2}\) są względnie pierwsze.

Załóżmy teraz, że \(\displaystyle{ t}\) nie jest pierwsze. Dla \(\displaystyle{ t=1}\) i \(\displaystyle{ t=4}\) sprawdzamy ręcznie. Gdy \(\displaystyle{ t>4}\) łatwo pokazać, że \(\displaystyle{ t \mid (t-1)!}\), stąd \(\displaystyle{ t}\) nie dzieli \(\displaystyle{ 4((t-1)!+1)+t}\).
Załóżmy, że \(\displaystyle{ t+2}\) jest złożone. Znowu łatwo pokazać, że dla \(\displaystyle{ t>4}\) mamy \(\displaystyle{ t+2 \mid (t-1)!}\) i znowu podzielność nie zachodzi.

Jak wszystko ok, to poszukam jakiegoś zadanka do wrzucenia.

[Vax]

Jest spoko, wrzucaj nowe

[Ponewor]

To nie fair Ja tu w pocie czoła przepisuję swoje rozwiązanie, a tu ktoś się ładuje. Poza tym to twierdzenie nie jest prawdziwe dla \(\displaystyle{ t=1}\). Pewien fragment mam inaczej i może pokażę, gdyby ktoś był ciekaw.

Ukryta treść:    

Z twierdzenia Leibniz'a \(\displaystyle{ t+2\mid t!-1 \Rightarrow t+2\mid 4\left(t!-1\right)+\left(t+2\right)^{2}=t\left(4\left(\left(t-1\right)!+1\right)+t\right)}\). Ponieważ \(\displaystyle{ \left(t, \ t+2\right)=1}\), to \(\displaystyle{ t+2 \mid 4\left(\left(t-1\right)!+1\right)+t}\).

Jest ok, dawaj nowe.

EDIT To jest już turbo nie fair. Ja tu w pocie czoła piszę "Jest ok, dawaj nowe", a tu Vax się wcina.