Podzielność przez 43

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Kera
Użytkownik
Użytkownik
Posty: 120
Rejestracja: 8 lis 2014, o 15:33
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 2 razy
Pomógł: 4 razy

Podzielność przez 43

Post autor: Kera »

Czy waszym zdaniem liczba \(\displaystyle{ 43}\) dzieli jakąkolwiek liczbę postaci \(\displaystyle{ 10 ^{N} +1}\), dla dowolnej liczby naturalnej \(\displaystyle{ N }\)?
Ostatnio zmieniony 9 cze 2024, o 20:16 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm . Poprawa wiadomości.
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4119
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 82 razy
Pomógł: 1410 razy

Re: Podzielność przez 43

Post autor: Janusz Tracz »

Można zauważyć, że dla dowolnego naturalnego \(\displaystyle{ n}\) mamy kongruencję \(\displaystyle{ 10^n+1 = 10^{n+21}+1 \, \mathrm{ mod } 43}\). Wystarczy więc sprawdzić pierwsze \(\displaystyle{ 21}\) wyrazów ciągu \(\displaystyle{ 10^n+1\, \mathrm{ mod } 43 }\) pod względem tego, że nie są to zera aby okazało się, że nie ma takiego \(\displaystyle{ n}\) dla którego \(\displaystyle{ 43| 10^n+1}\).
Kera
Użytkownik
Użytkownik
Posty: 120
Rejestracja: 8 lis 2014, o 15:33
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 2 razy
Pomógł: 4 razy

Re: Podzielność przez 43

Post autor: Kera »

Ten link https://stdkmd.net/nrr/repunit/10001.htm wskazuje że \(\displaystyle{ 10^{21} + 1 }\) nie dzieli się przez 43
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4119
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 82 razy
Pomógł: 1410 razy

Re: Podzielność przez 43

Post autor: Janusz Tracz »

Ano nie dzieli się, zgodnie z przypuszczeniem i dowodem.
Kera
Użytkownik
Użytkownik
Posty: 120
Rejestracja: 8 lis 2014, o 15:33
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 2 razy
Pomógł: 4 razy

Re: Podzielność przez 43

Post autor: Kera »

Czyli 43 nie dzieli żadną z liczb \(\displaystyle{ 10 ^{N} +1}\) dla dowolnej liczby naturalnej N.
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4119
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 82 razy
Pomógł: 1410 razy

Re: Podzielność przez 43

Post autor: Janusz Tracz »

https://starwars.fandom.com/wiki/I_have_spoken Powiedziałem swoje nie ma takiego \(\displaystyle{ n}\) dla którego \(\displaystyle{ 43|10^n+1}\).
Kera
Użytkownik
Użytkownik
Posty: 120
Rejestracja: 8 lis 2014, o 15:33
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 2 razy
Pomógł: 4 razy

Re: Podzielność przez 43

Post autor: Kera »

Więc liczby \(\displaystyle{ 31;53;67;71;79;83}\) zgodnie z tym co napisałeś też nie dzielą \(\displaystyle{ 10 ^{N}+1 }\), dlla \(\displaystyle{ N}\) naturalnego.
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4119
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 82 razy
Pomógł: 1410 razy

Re: Podzielność przez 43

Post autor: Janusz Tracz »

Nie wiem jak to wynika z tego co pisałem. Może tak jest.
Samouk1
Użytkownik
Użytkownik
Posty: 86
Rejestracja: 13 lis 2022, o 14:12
Płeć: Mężczyzna
wiek: 26
Podziękował: 33 razy
Pomógł: 2 razy

Re: Podzielność przez 43

Post autor: Samouk1 »

Janusz Tracz pisze: 9 cze 2024, o 19:50 Można zauważyć, że dla dowolnego naturalnego \(\displaystyle{ n}\) mamy kongruencję \(\displaystyle{ 10^n+1 = 10^{n+21}+1 \, \mathrm{ mod } 43}\).
To jakiś prosty fakt? Jak to zauważyć?
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4119
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 82 razy
Pomógł: 1410 razy

Re: Podzielność przez 43

Post autor: Janusz Tracz »

Tak, to jest prosty fakt. Dowód jest indukcyjny (o ile już się wie co chce się osiągnąć). A jeśli o zauważenie takiego czegoś chodzi to w tym przypadku - zgadłem to po zbadaniu kilku przystawań. Jednak można to usystematyzować (i wskazać kandydatów na dobry wykładnik). Z małego twierdzenie Fermata wynika, że

\(\displaystyle{ 10^{42}=1 \mod 43}\)

Niestety w ogólności wykładnik (to jest \(\displaystyle{ 42}\)) z małego twierdzenie Fermata nie musi być rzędem elementu (tu \(\displaystyle{ 10}\)) w grupie multiplikatywnej \(\displaystyle{ \ZZ_{43}^{\times}}\). Jednak z twierdzenia Lagrange wynika, że rząd (jako liczność grupy generowanej) jest dzielnikiem tego co pojawia się w małym twierdzeniu Fermata. Czyli podejrzane są dzielniki \(\displaystyle{ 42}\). Sprawdziłem \(\displaystyle{ 1,2,3,6,7,14}\) i dopiero \(\displaystyle{ 21}\) zadziałało.

Jednak to wszystko jest tylko po to aby otrzymać bardziej optymalną kongruencje. Optymalną w sensie pozwalającą na zbadanie mniejszej liczby przypadków. Mogłem równie dobrze napisać, że skoro \(\displaystyle{ 10^{43}=10 \mod 43}\) to wystarczy sprawdzić pierwsze \(\displaystyle{ 42}\) liczby naturalne pod względem podzielności \(\displaystyle{ 43|10^n+1}\). Tylko po co sprawdzać \(\displaystyle{ 42}\) przypadki jak można \(\displaystyle{ 21}\).


Można to też zrobić jeszcze szybciej z kryterium Eulera (tu dodatkowo wykorzystamy fakt pierwszości \(\displaystyle{ 43}\)) mówiącego (przy pewnych założeniach które są tu spełnione), że \(\displaystyle{ a=10}\) jest resztą kwadratową modulo \(\displaystyle{ p=43}\) wtedy i tylko wtedy, gdy

\(\displaystyle{ {\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}} \pmod {p}}. }\)

Nie będziemy tu tej kongruencji sprawdzać tylko skorzystamy z drugiej części (wtedy i tylko wtedy). To znaczy inną metodą można pokąsać, że \(\displaystyle{ 10}\) jest resztą kwadratową modulo \(\displaystyle{ 43}\). Ta inna metoda to po prostu policzenie symbolu Legendre. Po policzeniu mamy, że

\(\displaystyle{ \left({\frac {10}{43}}\right) = 1 }\)

Zatem \(\displaystyle{ 10}\) jest resztą kwadratową modulo \(\displaystyle{ 43}\) oraz co wynika z kryterium Eulera \(\displaystyle{ {\displaystyle 10^{\frac {43-1}{2}} \equiv 1 \pmod {43}}}\).



No i oczywiście jak już wiemy, że \(\displaystyle{ 10^{21}=1}\) w grupie reszt \(\displaystyle{ 43}\) to pomnożenie równości przez \(\displaystyle{ 10^n}\) kończy dowód kongruencji które Cię zainteresowała.
ODPOWIEDZ