Zbiór i kongruencja
- mol_ksiazkowy
- Użytkownik
- Posty: 11409
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3155 razy
- Pomógł: 748 razy
Zbiór i kongruencja
Niech \(\displaystyle{ M}\) będzie zbiorem liczb naturalnych \(\displaystyle{ k}\) takich, że istnieje liczba naturalna \(\displaystyle{ n}\) iż
\(\displaystyle{ 3^n \equiv k\ (\bmod n)}\)
Udowodnić, że zbiór \(\displaystyle{ M}\) jest nieskończony.
\(\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.
Powód: Poprawa wiadomości.
- arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Zbiór i kongruencja
Ż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}\)
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}\)
-
- Użytkownik
- Posty: 78
- Rejestracja: 13 lis 2022, o 14:12
- Płeć: Mężczyzna
- wiek: 26
- Podziękował: 30 razy
- Pomógł: 2 razy
Re: Zbiór i kongruencja
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 }\)
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.
Powód: Poprawa wiadomości.
-
- Administrator
- Posty: 34285
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
-
- Użytkownik
- Posty: 78
- Rejestracja: 13 lis 2022, o 14:12
- Płeć: Mężczyzna
- wiek: 26
- Podziękował: 30 razy
- Pomógł: 2 razy
Re: Zbiór i kongruencja
Stąd moje pierwsze pytanieJan Kraszewski pisze: ↑14 kwie 2023, o 20:14 Powstaje zatem pytanie, czy na pewno o to chodziło w tym zadaniu.
- arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Zbiór i kongruencja
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ć...
\(\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ć...
- arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Zbiór i kongruencja
\(\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...
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...
-
- Administrator
- Posty: 34285
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
Re: Zbiór i kongruencja
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
-
- 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
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.
\(\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.
- arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Zbiór i kongruencja
Nie wiem co piszesz ale do pokazania było, że zbiór reszt jest nieskończony i ja tam nic nie widzę więcej...Było do pokazania to, co zostało napisane, a nie to, co Ty tam widzisz.
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:
Raczej tylko ja to widzę...no ale trudno...Udowodnić, że zbiór M jest nieskończony.