Matematyka.pl

Czy waszym zdaniem liczba \(\displaystyle{ 43}\) dzieli jakąkolwiek liczbę postaci \(\displaystyle{ 10 ^{N} +1}\), dla dowolnej liczby naturalnej \(\displaystyle{ N }\)?

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}\).

Ten link https://stdkmd.net/nrr/repunit/10001.htm wskazuje że \(\displaystyle{ 10^{21} + 1 }\) nie dzieli się przez 43

Ano nie dzieli się, zgodnie z przypuszczeniem i dowodem.

Czyli 43 nie dzieli żadną z liczb \(\displaystyle{ 10 ^{N} +1}\) dla dowolnej liczby naturalnej N.

https://starwars.fandom.com/wiki/I_have_spoken Powiedziałem swoje nie ma takiego \(\displaystyle{ n}\) dla którego \(\displaystyle{ 43|10^n+1}\).

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.

Nie wiem jak to wynika z tego co pisałem. Może tak jest.

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ć?

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


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


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


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.