Zbiór i kongruencja

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: 11263
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3140 razy
Pomógł: 746 razy

Zbiór i kongruencja

Post autor: mol_ksiazkowy »

Niech \(\displaystyle{ M}\) będzie zbiorem liczb naturalnych \(\displaystyle{ k}\) takich, że istnieje liczba naturalna \(\displaystyle{ n}\)

\(\displaystyle{ 3^n \equiv k\ (\bmod n)}\)

Udowodnić, że zbiór \(\displaystyle{ M}\) jest nieskończony.
Ostatnio zmieniony 27 mar 2023, o 10:35 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
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: Zbiór i kongruencja

Post autor: arek1357 »

Żeby zbiór reszt był nieskończony wystarczy pokazać taki podciąg w którym reszty modulaste będą się rozszerzać do nieskończoności...

Czyli np. potęgi będą przyjmowały wartości: \(\displaystyle{ -1 \mod n}\)

Wystarczy więc wykazać, że liczb spełniających poniższą podzielność jest nieskończenie wiele, a mianowicie:

\(\displaystyle{ n|3^n+1}\)

Lub inaczej:

\(\displaystyle{ 3^n=-1 \mod n}\)

Wystarczy położyć:

\(\displaystyle{ n=2*5^k}\)

Znaczy, że:

\(\displaystyle{ 9^{5^k}+1=0 \mod 5^k}\)

Bo:
\(\displaystyle{ 2|9^{5^k}+1 }\)

Że tak jest można indukcją:

dla:

\(\displaystyle{ k=1}\)

\(\displaystyle{ 9^5+1= 0 \mod 5}\)

Załóżmy indukcyjnie, że dla pewnego k spełniony jest krok indukcyjny, czyli:

\(\displaystyle{ 9^{5^k}+1=0 \mod 5^k}\)

trzeba udowodnić, że:

\(\displaystyle{ 9^{5^{k+1}}+1= 0 \mod 5^{k+1}}\)

Dw.:

\(\displaystyle{ 9^{5^{k+1}}=\left( 9^{5^k}\right)^5 +k=\left[ a5^k-1\right]^5+1=a^5 \cdot 5^{5k}-a^4 \cdot 5^{4k+1} +2a^3 \cdot 5^{3k+1}-2a^2 \cdot 5^{2k+1}+a \cdot 5^{k+1}=b \cdot 5^{k+1}=0 \mod 5^{k+1} }\)

cnd...

Jeszcze dopiszę, że:

\(\displaystyle{ -1 \mod 5^k =5^k-1 \mod 5^k}\)

I jak widać te reszty będą za każdym razem inne coraz "większe" bo \(\displaystyle{ k}\) rośnie

Dlatego jakby wynosiło to modulo jeden to reszty byłyby ciągle takie same i dlatego wybrałem tę drogę...

Dodano po 2 godzinach 14 minutach 58 sekundach:
Zadanie mogło brzmieć tak:

Wykaż, że istnieje nieskończenie wiele liczb naturalnych takich, że:

\(\displaystyle{ n|3^n+1}\)

Dodano po 1 minucie 52 sekundach:
i tu:

\(\displaystyle{ n=2 \cdot 5^k}\)
Samouk1
Użytkownik
Użytkownik
Posty: 75
Rejestracja: 13 lis 2022, o 14:12
Płeć: Mężczyzna
wiek: 26
Podziękował: 30 razy
Pomógł: 1 raz

Re: Zbiór i kongruencja

Post autor: Samouk1 »

Prawdopodobnie nie zrozumiałem zadania, ale dlaczego nie podstawić \(\displaystyle{ k = 3^n}\)?
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: Zbiór i kongruencja

Post autor: arek1357 »

Podstaw sprawdź, jak zadziała to mamy kolejny zbiór rozwiązań...
Samouk1
Użytkownik
Użytkownik
Posty: 75
Rejestracja: 13 lis 2022, o 14:12
Płeć: Mężczyzna
wiek: 26
Podziękował: 30 razy
Pomógł: 1 raz

Re: Zbiór i kongruencja

Post autor: Samouk1 »

Nie bardzo wiem co tu sprawdzać.

Dla dowolnego \(\displaystyle{ n}\) naturalnego zachodzi
\(\displaystyle{ 3^n \equiv 3^n (\bmod n)}\)

Więc
\(\displaystyle{ \left\{ 3, 9, 27, 81, \ldots \right\} \subset M }\)
Ostatnio zmieniony 14 kwie 2023, o 20:11 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Zbiór i kongruencja

Post autor: Jan Kraszewski »

Powstaje zatem pytanie, czy na pewno o to chodziło w tym zadaniu.

JK
Samouk1
Użytkownik
Użytkownik
Posty: 75
Rejestracja: 13 lis 2022, o 14:12
Płeć: Mężczyzna
wiek: 26
Podziękował: 30 razy
Pomógł: 1 raz

Re: Zbiór i kongruencja

Post autor: Samouk1 »

Jan Kraszewski pisze: 14 kwie 2023, o 20:14 Powstaje zatem pytanie, czy na pewno o to chodziło w tym zadaniu.
Stąd moje pierwsze pytanie
Samouk1 pisze: 1 kwie 2023, o 02:41 Prawdopodobnie nie zrozumiałem zadania, ale dlaczego nie podstawić \(\displaystyle{ k = 3^n}\)?
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: Zbiór i kongruencja

Post autor: arek1357 »

Dobra brnijmy dalej:

\(\displaystyle{ 3^2 \mod 2=9=1 \mod 2}\)

\(\displaystyle{ 3^3\mod 3=0 \mod 3}\)

\(\displaystyle{ 3^4 \mod 4 =1 \mod 4}\)

\(\displaystyle{ 3^5 \mod 5 =3 \mod 5}\)

\(\displaystyle{ 3^6 \mod 6 =3 \mod 6}\)

\(\displaystyle{ 3^7 \mod 7 =3 \mod 7}\)

\(\displaystyle{ 3^8 \mod 8 =1 \mod 8}\)

......................................................

I co mamy?

\(\displaystyle{ M=\left\{ 0, 1,3,...\right\} }\)

Daleka droga do nieskończoności zbioru M przynajmniej tego nie widać...
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: Zbiór i kongruencja

Post autor: Brombal »

A gdyby \(\displaystyle{ M}\) to \(\displaystyle{ \left\{ 4, 11, 30, 85, 248, 735, 2194...\right\}}\) ?
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: Zbiór i kongruencja

Post autor: arek1357 »

Tylko trzeba pokazać taki ciąg...
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: Zbiór i kongruencja

Post autor: Brombal »

\(\displaystyle{ k=3 ^{n}+n }\)
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: Zbiór i kongruencja

Post autor: arek1357 »

\(\displaystyle{ 3^n+n=3^n \mod n}\)

To mają być reszty ludzie reszty nie liczby...

Było do wykazania, że zbiór reszt jest nieskończony , ten sam robisz błąd co i twój poprzednik...
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Zbiór i kongruencja

Post autor: Jan Kraszewski »

arek1357 pisze: 18 kwie 2023, o 11:24Było do wykazania, że zbiór reszt jest nieskończony , ten sam robisz błąd co i twój poprzednik...
Było do pokazania to, co zostało napisane, a nie to, co Ty tam widzisz.

A czy zostało poprawnie napisane to już inna sprawa.

JK
Mateusz5324
Użytkownik
Użytkownik
Posty: 47
Rejestracja: 26 sty 2023, o 18:37
Płeć: Mężczyzna
wiek: 15
Lokalizacja: Kraków
Pomógł: 3 razy

Re: Zbiór i kongruencja

Post autor: Mateusz5324 »

Kongruencja ta ma min. 1 rozwiązanie, a zwiększając k o kolejne wielokrotności n otrzymujemy nieskończoność rozwiązań
\(\displaystyle{ 3^n \equiv 3^n {\pmod n}}\)
Z tego podstawmy.
\(\displaystyle{ k_1=3^n}\)
\(\displaystyle{ k_z=k_{z-1}+n=3^n+(z-1)n}\)
c.k.d.
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: Zbiór i kongruencja

Post autor: arek1357 »

Było do pokazania to, co zostało napisane, a nie to, co Ty tam widzisz.
Nie wiem co piszesz ale do pokazania było, że zbiór reszt jest nieskończony i ja tam nic nie widzę więcej...

Brombal i Samouk tworzyli jakieś ciągi ale niestety nie modulo...

A co Ty chciałeś powiedzieć tego niestety nie wiem...(troszkę od czapy wstawka)...

Dodano po 1 minucie 43 sekundach:
Mateusz pisze kolejne herezje

Dodano po 1 minucie 48 sekundach:
Udowodnić, że zbiór M jest nieskończony.
Raczej tylko ja to widzę...no ale trudno...
ODPOWIEDZ