Podzielność
- mol_ksiazkowy
- Użytkownik
- Posty: 11458
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3156 razy
- Pomógł: 748 razy
Podzielność
Dane są liczby naturalne \(\displaystyle{ x, y}\) takie, że \(\displaystyle{ x^{2^n}-1}\) dzieli się przez \(\displaystyle{ 2^ny+1}\) dla \(\displaystyle{ n=1, 2, 3,...}\) Udowodnić, że \(\displaystyle{ x=1}\).
- arek1357
- Użytkownik
- Posty: 5750
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Podzielność
\(\displaystyle{ x^2=1 \mod (2y+1)}\)
Trzeba tu rozwiązywać równania w pierścieniach:
\(\displaystyle{ \ZZ_{2^ny+1}}\)
Rozwiązaniem tego równania jest:
(*) \(\displaystyle{ x=1+(2y+1)a \vee x=2y+(2y+1)a}\)
Załóżmy, że: \(\displaystyle{ a \neq 0}\)
Weźmy np. drugie równanie i rozwiążmy kongurencję:
\(\displaystyle{ x^4=1 \mod (4y+1)}\)
\(\displaystyle{ \left[ 2y+(2y+1)a\right]^4= 1 \mod (4y+1) \vee \left[ 1+(2y+1)a\right]^4=1 \mod (4y+1) }\)
\(\displaystyle{ \left( 2y+2ay+a\right)^4=1/ \cdot 4^4 \mod (4y+1) \vee \left( 1+2ay+a\right)^4=1 \mod (4y+1) / \cdot 4^4 }\)
\(\displaystyle{ 4y+1}\) nieparzysta więc nie ma możliwości obawy o to, że liczba przez którą mnożymy jest dzielnikiem zera...
\(\displaystyle{ \left( 2 \cdot 4y+2a4y+4a\right)^4=4^4 \mod (4y+1) \vee \left( 4+2a4y+4a\right)^4=4^4 \mod (4y+1) }\)
Pamiętając, że:
\(\displaystyle{ 4y=-1}\)
Otrzymamy:
\(\displaystyle{ \left( -2-2a+4a \right)^4=4^4 \mod (4y+1) \vee \left( 4-2a+4a \right)^4=4^4 \mod (4y+1) }\)
\(\displaystyle{ \left( 2a-2 \right)^4=4^4 \mod (4y+1) \vee \left( 2a+4 \right)^4=4^4 \mod (4y+1) }\)
\(\displaystyle{ 2^4 \left( a-1 \right)^4=4^4 \mod (4y+1) \vee 2^4 \left( a+2 \right)^4=4^4 \mod (4y+1) }\)
Z tego:
\(\displaystyle{ (a-1)^4=2^4 \vee (a+2)^4=2^4 \mod (4y+1) }\)
Mamy między innymi rozwiązania:
\(\displaystyle{ a=3,-1,0,4 \mod (4y+1)}\)
Pal sześć inne rozwiązania bo o wszystkie nie bardzo mi biega
Otrzymyjemy:
\(\displaystyle{ a=3+(4y+1)b \vee a=4y+(4y+1)b \vee a=4+(4y+1)b , a=(4b+1)b}\)
Na pewno jest więcej niż przedstawiłem ale nie o to mi do końca biega,żeby je tu wszystkie wypisywać...
Zapiszmy nasze \(\displaystyle{ x}\)
A więc:
\(\displaystyle{ x=1+(1+2y)a \vee x=2y+(1+2y)a}\)
Podstawiając za \(\displaystyle{ a}\) otrzymamy coś w tym stylu:
\(\displaystyle{ x=1+3(1+2y)+(1+2y)(1+4y)b \vee x =2y+4y(1+2y)+(1+2y)(1+4y)b , x=..................}\)
Idąc za ciosem już można coś odczytać, w następnym równaniu modulo będziemy szukać \(\displaystyle{ b}\)
w równaniu:
\(\displaystyle{ x^8=1 \ mod (8y+1)}\)
Łatwo teraz odczytać jak będzie wyglądał x po rozwiązaniu n równań:
\(\displaystyle{ x=p_{1}+p_{2}(1+2y)+p_{3}(1+2y)(1+4y)+p_{4}(1+2y)(1+4y)(1+8y)+..............+p_{n}(1+2y)(1+4y) \cdot ... \cdot (1+2^{n-1}y)+...}\)
Jeżeli tych równań modulo jest nieskończenie wiele a \(\displaystyle{ p_{i} \neq 0}\) i one są wyznaczone jednoznacznie to to nasze \(\displaystyle{ x }\)
urośnie do nieskończoności i nie będzie dla wszystkich \(\displaystyle{ n}\) rozwiązania różnego od jeden
Wracając do (*) i zakładając, że \(\displaystyle{ a=0}\)
otrzymamy równanie:
\(\displaystyle{ x=2y}\)
następne będzie:
\(\displaystyle{ (2y)^4=1 \mod (4y+1)}\)
lub:
\(\displaystyle{ 16y^4=4y \cdot 4y \cdot y^2=y^2=1 \mod (4y+1)}\)
Z tego:
\(\displaystyle{ y=1+(4y+1)c \vee y=4y+(4y+1)c}\)
Z tego wyjdzie co łatwo sprawdzić:
\(\displaystyle{ y=1}\)
więc:
\(\displaystyle{ x=2}\) i napiszemy kolejny szereg równań, które mają być spełnione:
\(\displaystyle{ x^2=2^2=4=1 \mod(2y+1)=1 \mod 3 , y=1}\) - spełnia
teraz drugie:
\(\displaystyle{ x^4=2^4=16 =1 \mod 5}\) - spełnia
trzecie:
\(\displaystyle{ x^8=2^8=1 \mod 9}\) - nie spełnia tu się załamuje...
Więc zostaje jedyne rozwiązanie:
\(\displaystyle{ x=1, a=0}\)
jest spełnione dla wszystkich n, cnd...
Trzeba tu rozwiązywać równania w pierścieniach:
\(\displaystyle{ \ZZ_{2^ny+1}}\)
Rozwiązaniem tego równania jest:
(*) \(\displaystyle{ x=1+(2y+1)a \vee x=2y+(2y+1)a}\)
Załóżmy, że: \(\displaystyle{ a \neq 0}\)
Weźmy np. drugie równanie i rozwiążmy kongurencję:
\(\displaystyle{ x^4=1 \mod (4y+1)}\)
\(\displaystyle{ \left[ 2y+(2y+1)a\right]^4= 1 \mod (4y+1) \vee \left[ 1+(2y+1)a\right]^4=1 \mod (4y+1) }\)
\(\displaystyle{ \left( 2y+2ay+a\right)^4=1/ \cdot 4^4 \mod (4y+1) \vee \left( 1+2ay+a\right)^4=1 \mod (4y+1) / \cdot 4^4 }\)
\(\displaystyle{ 4y+1}\) nieparzysta więc nie ma możliwości obawy o to, że liczba przez którą mnożymy jest dzielnikiem zera...
\(\displaystyle{ \left( 2 \cdot 4y+2a4y+4a\right)^4=4^4 \mod (4y+1) \vee \left( 4+2a4y+4a\right)^4=4^4 \mod (4y+1) }\)
Pamiętając, że:
\(\displaystyle{ 4y=-1}\)
Otrzymamy:
\(\displaystyle{ \left( -2-2a+4a \right)^4=4^4 \mod (4y+1) \vee \left( 4-2a+4a \right)^4=4^4 \mod (4y+1) }\)
\(\displaystyle{ \left( 2a-2 \right)^4=4^4 \mod (4y+1) \vee \left( 2a+4 \right)^4=4^4 \mod (4y+1) }\)
\(\displaystyle{ 2^4 \left( a-1 \right)^4=4^4 \mod (4y+1) \vee 2^4 \left( a+2 \right)^4=4^4 \mod (4y+1) }\)
Z tego:
\(\displaystyle{ (a-1)^4=2^4 \vee (a+2)^4=2^4 \mod (4y+1) }\)
Mamy między innymi rozwiązania:
\(\displaystyle{ a=3,-1,0,4 \mod (4y+1)}\)
Pal sześć inne rozwiązania bo o wszystkie nie bardzo mi biega
Otrzymyjemy:
\(\displaystyle{ a=3+(4y+1)b \vee a=4y+(4y+1)b \vee a=4+(4y+1)b , a=(4b+1)b}\)
Na pewno jest więcej niż przedstawiłem ale nie o to mi do końca biega,żeby je tu wszystkie wypisywać...
Zapiszmy nasze \(\displaystyle{ x}\)
A więc:
\(\displaystyle{ x=1+(1+2y)a \vee x=2y+(1+2y)a}\)
Podstawiając za \(\displaystyle{ a}\) otrzymamy coś w tym stylu:
\(\displaystyle{ x=1+3(1+2y)+(1+2y)(1+4y)b \vee x =2y+4y(1+2y)+(1+2y)(1+4y)b , x=..................}\)
Idąc za ciosem już można coś odczytać, w następnym równaniu modulo będziemy szukać \(\displaystyle{ b}\)
w równaniu:
\(\displaystyle{ x^8=1 \ mod (8y+1)}\)
Łatwo teraz odczytać jak będzie wyglądał x po rozwiązaniu n równań:
\(\displaystyle{ x=p_{1}+p_{2}(1+2y)+p_{3}(1+2y)(1+4y)+p_{4}(1+2y)(1+4y)(1+8y)+..............+p_{n}(1+2y)(1+4y) \cdot ... \cdot (1+2^{n-1}y)+...}\)
Jeżeli tych równań modulo jest nieskończenie wiele a \(\displaystyle{ p_{i} \neq 0}\) i one są wyznaczone jednoznacznie to to nasze \(\displaystyle{ x }\)
urośnie do nieskończoności i nie będzie dla wszystkich \(\displaystyle{ n}\) rozwiązania różnego od jeden
Wracając do (*) i zakładając, że \(\displaystyle{ a=0}\)
otrzymamy równanie:
\(\displaystyle{ x=2y}\)
następne będzie:
\(\displaystyle{ (2y)^4=1 \mod (4y+1)}\)
lub:
\(\displaystyle{ 16y^4=4y \cdot 4y \cdot y^2=y^2=1 \mod (4y+1)}\)
Z tego:
\(\displaystyle{ y=1+(4y+1)c \vee y=4y+(4y+1)c}\)
Z tego wyjdzie co łatwo sprawdzić:
\(\displaystyle{ y=1}\)
więc:
\(\displaystyle{ x=2}\) i napiszemy kolejny szereg równań, które mają być spełnione:
\(\displaystyle{ x^2=2^2=4=1 \mod(2y+1)=1 \mod 3 , y=1}\) - spełnia
teraz drugie:
\(\displaystyle{ x^4=2^4=16 =1 \mod 5}\) - spełnia
trzecie:
\(\displaystyle{ x^8=2^8=1 \mod 9}\) - nie spełnia tu się załamuje...
Więc zostaje jedyne rozwiązanie:
\(\displaystyle{ x=1, a=0}\)
jest spełnione dla wszystkich n, cnd...
-
- Użytkownik
- Posty: 466
- Rejestracja: 1 gru 2015, o 21:49
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 6 razy
- Pomógł: 20 razy
Re: Podzielność
Przyjmijmy
\(\displaystyle{ x=26}\) oraz \(\displaystyle{ y=2}\)
albo
\(\displaystyle{ x=37}\) oraz \(\displaystyle{ y=1}\)
albo
\(\displaystyle{ x=44}\) oraz \(\displaystyle{ y=1}\)
\(\displaystyle{ x=26}\) oraz \(\displaystyle{ y=2}\)
albo
\(\displaystyle{ x=37}\) oraz \(\displaystyle{ y=1}\)
albo
\(\displaystyle{ x=44}\) oraz \(\displaystyle{ y=1}\)
-
- Użytkownik
- Posty: 466
- Rejestracja: 1 gru 2015, o 21:49
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 6 razy
- Pomógł: 20 razy
Re: Podzielność
Dla tych trzech liczb \(\displaystyle{ n}\) istnieją \(\displaystyle{ x>1}\)
Taki głupi żarcik dla sprawdzających kolejno od \(\displaystyle{ 1}\)
- arek1357
- Użytkownik
- Posty: 5750
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Podzielność
Tak uśmiałem się trochę z tego żartu prowadzącego...
Dla każdego n w sumie układ równań ale skończony ma rozwiązanie oprócz jedynki ale nie jeżeli równań modulo jest nieskończenie wiele w tych szczególnych pierścieniach...
Dla każdego n w sumie układ równań ale skończony ma rozwiązanie oprócz jedynki ale nie jeżeli równań modulo jest nieskończenie wiele w tych szczególnych pierścieniach...