Podzielność

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11265
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3143 razy
Pomógł: 747 razy

Podzielność

Post autor: mol_ksiazkowy »

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}\).
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Podzielność

Post autor: arek1357 »

\(\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...
Brombal
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 1 gru 2015, o 21:49
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 6 razy
Pomógł: 20 razy

Re: Podzielność

Post autor: Brombal »

Przyjmijmy
\(\displaystyle{ x=26}\) oraz \(\displaystyle{ y=2}\)
albo
\(\displaystyle{ x=37}\) oraz \(\displaystyle{ y=1}\)
albo
\(\displaystyle{ x=44}\) oraz \(\displaystyle{ y=1}\) ;-)
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Podzielność

Post autor: arek1357 »

\(\displaystyle{ 26^{16} \mod 33=4}\)

I o co chodzi?
Brombal
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 1 gru 2015, o 21:49
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 6 razy
Pomógł: 20 razy

Re: Podzielność

Post autor: Brombal »

mol_ksiazkowy pisze: 17 maja 2023, o 15:57 ...n=1,2,3
Dla tych trzech liczb \(\displaystyle{ n}\) istnieją \(\displaystyle{ x>1}\)
Taki głupi żarcik dla sprawdzających kolejno od \(\displaystyle{ 1}\) ;-)
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Podzielność

Post autor: arek1357 »

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