znaleźc wielokrotność liczby, zbudowana z samych dziewiątek

[matinf]

Znajdź najmniejszą wielokrotność liczby \(\displaystyle{ 130013}\), której zapis w systemie dziesiątkowym składa się z samych dziewiątek.

Ja pokażę swoje rozwiązanie. Proszę o ocenę, a jeśli jest poprawne czy da się to rozwiązać nie znając rozkładu danej w zadaniu liczby na czynnik pierwsze ?


Same dziewiątki to liczba postaci:
\(\displaystyle{ 10^{n+1}-1}\).
I skoro dziesiątka jest względnie pierwsza z \(\displaystyle{ 130013}\), to biorąc funkcji Carmichel'a:
\(\displaystyle{ 10^{\lambda \left( 130013 \right) } \equiv 1\pmod{130013}}\)
\(\displaystyle{ \lambda \left( 130013 \right) = nww \left( \phi \left( 13 \right) , \phi \left( 73 \right) , \phi \left( 136 \right) \right) = 1224}\)
\(\displaystyle{ 10^{1224} - 1 \equiv 0\pmod{130013 }}\)

No i znalazłem, sprawdzałem, faktycznie ta liczba spełnia oczekiwania, a że użyłem fcji Carmichel'a to mamy najmniejszą.

Mnie jednak interesuje rozwiązanie bez wiedzy jaki jest rozkład \(\displaystyle{ 130013}\).

[Ponewor]

Funkcja Carmichaela tak nie działa. Gdybyś zamiast dzięsiątki miał tam jedynkę, to nadal jako rezultat otrzymałbyś \(\displaystyle{ 1224}\)? Ona zwraca najmniejszą liczbę \(\displaystyle{ a}\) taką, że \(\displaystyle{ k^{a} \equiv 1 \pmod{n}}\) dla wszystkich \(\displaystyle{ k}\) względnie pierwszych z \(\displaystyle{ n}\). Co nie oznacza, że dla niektórych \(\displaystyle{ k}\) mogą istnieć wykładniki mniejsze.

Rozkład, który tu podałeś jest niepoprawny, acz sądzę, że jest to jedynie literówka.

Sądzę, że akurat z faktu, że \(\displaystyle{ 130013=13 \cdot 10001}\) to tutaj należy skorzystać, bo nie przypadkiem jest widoczny gołym okiem.

[matinf]

Sądzę, że akurat z faktu, że \(\displaystyle{ 130013=13 \cdot 10001}\) to tutaj należy skorzystać, bo nie przypadkiem jest widoczny gołym okiem.

Tak, literówka.
\(\displaystyle{ 130013 = 13\cdot 73 \cdot 137}\)
Na gołe oko widać jedynie, że \(\displaystyle{ 130013=13 \cdot 100001}\).
Jakim cudem można wypatrzeć rozkład : \(\displaystyle{ 10001}\) ?


A to już rozumiem, ta funkcja po prostu mówi: To jest najmniejszy wykładnik, ale uniwersalny, że każda względnie pierwsza z modulnikiem podniesiona do niej daje resztę \(\displaystyle{ 1}\) z dzielenia przez modulnik (który nie musi być liczbą pierwszą).

Czyli generalnie rzecz biorąc, skoro dziesiątka jest względnie pierwsza z modulnikiem, to kongruencja napisana przeze mnie jest prawdziwa.

W takim razie, skoro nie mieszamy w to rozkładu (nielegalnie zdobytego ) to z funkcji eulera mamy, że
\(\displaystyle{ 10^{12\cdot\phi(10001)} \equiv 1 \pmod{130013}}\) - ta kongruencja zachodzi.
Jeśli więc istnieje mniejszy wykładnik, którego szukamy to musi być dzielnikiem \(\displaystyle{ 12\cdot\phi(10001)}\).
A więc może to być \(\displaystyle{ 6,7,8,...,}\) i wiele innych liczb, których tu nie wymieniłem.
Gdybym znał rozkład poradziłbym sobie zapewne, bo znalazłbym dzielnik, który dzieli tą liczbę jakoś.

Poddaję się na dziś. Napisz proszę pod spojlerem, może uda mi się odkryć zagadkę

[Ponewor]

1.:    

Spróbuj rozwiązać to samo zadanie tylko zamiast liczby \(\displaystyle{ 130013}\) zrób to dla \(\displaystyle{ 10001}\).

2.:    

Znajdź jakąkolwiek wielokrotność \(\displaystyle{ 10001}\) (niekoniecznie najmniejszą) składającą się z samych dziewiątek. Jakbyś to zrobił gdybyś nie posiadał żadnych mądrych narzędzi? Pokaż, że to jest właśnie ta najmniejsza.

[matinf]

Wykonałem wszystko co proponujesz.
Dla \(\displaystyle{ 10001}\) to jest liczba \(\displaystyle{ 99999999}\). Ale ta liczba nie dzieli się oczywiście przez \(\displaystyle{ 13}\)
Pokazanie, że jest najmniejsza jest łatwe z rachunku kongruencji. Ale jak przejść do modulnika \(\displaystyle{ 130013}\) ?

[Ponewor]

Następnym krokiem jest pokazanie, że:
1. \(\displaystyle{ 8 \mid n \Leftrightarrow 10001 \mid 10^{n}-1}\)

Potem musisz znaleźć analogiczny warunek na
2. \(\displaystyle{ 13 \mid 10^{n}-1}\)

Rozwiązaniem zadania będzie najmniejsza liczba całkowita dodatnia która spełnia oba warunki jednocześnie.

[matinf]

Oj, trudne to zadanie.

\(\displaystyle{ 8 \mid n \Leftrightarrow 10001 \mid 10^{n}-1}\)

Spróbuję tym zająć się wieczorem.

Potem musisz znaleźć analogiczny warunek na
\(\displaystyle{ 13 \mid 10^{n}-1}\)

A trudno ten warunek znaleźć ?


Rozumiem, że faktycznie te dwa warunki bardzo pomogą znaleźć rozwiązanie.
Ale po co w takim razie miałem rozwiązywać to dla liczby \(\displaystyle{ 100001}\) ?

[Ponewor]

No bo rozwiązując to dla liczby \(\displaystyle{ 10001}\) dowiedziałeś się, że \(\displaystyle{ 10001 \mid 10^{8}-1}\) co daje podstawę do udowodnienia pierwszego warunku. Nie jest trudno udowodnić go.

Ukryta treść:    

W prawo dowodzi się go trywialnie - wszak "sklejając" w zapisie dziesiętnym dwie liczby podzielne przez \(\displaystyle{ m}\) dalej otrzymamy liczbę podzielną przez \(\displaystyle{ m}\) (przypominam, że \(\displaystyle{ 10^{n}-1}\), to \(\displaystyle{ n}\) dziewiątek obok siebie).

Zaś w lewo musisz założyć nie wprost, że podzielność \(\displaystyle{ 10001 \mid 10^{n}-1}\) zachodzi i że \(\displaystyle{ n}\) daje niezerową resztę w dzieleniu przez \(\displaystyle{ 8}\) - \(\displaystyle{ n=8k+r}\). Skoro już odowodniliśmy nasz warunek w prawo to wiemy, że \(\displaystyle{ 10001 \mid 10^{8k}}\) i już wystarczy wykonać odpowiednie odejmowanie.

Drugi warunek łatwo znaleźć. Poszukujemy rzędu \(\displaystyle{ 10 \mod 13}\), a z MTF wiemy, że dzieli on \(\displaystyle{ 13-1=12}\), czyli szukamy go w skończonym zbiorze dzielników \(\displaystyle{ 12}\).

[matinf]

ok, czyli w takim razie \(\displaystyle{ 6 \mid n \Leftrightarrow 13 \mid 10^{n}-1}\)

Faktycznie te równoważności łatwo pokazać, ale trudniej na nie wpaść.

Wtedy, mamy, że najmniejsza taka liczba spełniająca te warunki to \(\displaystyle{ nww(8,6) = 24}\).
I faktycznie, \(\displaystyle{ 10^{24}\equiv 1\pmod{13\cdot 10001}}\)

Ale czy dowód z prawa na lewo nie wychodzi od razu z racji definicji rzędu ?

I może istnieją jakieś warunki, które są ogólniejsze, ale mają podobny sens ? (bo tutaj korzystaliśmy z własności liczby \(\displaystyle{ 10001}\))

[Ponewor]

Ale czy dowód z prawa na lewo nie wychodzi od razu z racji definicji rzędu ?

Nie wiem czy i jak się definiuje rząd dla liczby złożonej jaką jest \(\displaystyle{ 10001}\), więc dla bezpieczeństwa wolę tego pojęcia w odniesieniu do niej nie używać.

Zadanie w ogólniejszej wersji możemy rozwiązać np. gdy jak tutaj \(\displaystyle{ n}\) jest iloczynem różnych liczb pierwszych w pierwszych potęgach - wtedy znajdujemy rząd \(\displaystyle{ 10}\) względem każdej z tych liczb pierwszych i obliczamy \(\displaystyle{ nww}\).

[matinf]

Zadanie w ogólniejszej wersji możemy rozwiązać np. gdy jak tutaj \(\displaystyle{ n}\) jest iloczynem różnych liczb pierwszych w pierwszych potęgach - wtedy znajdujemy rząd \(\displaystyle{ 10}\) względem każdej z tych liczb pierwszych i obliczamy \(\displaystyle{ nww}\).

A cos odrobinę więcej możesz przedstawić tej treści ? (dokładniej)

[Ponewor]

Mamy \(\displaystyle{ n= \prod_{i=1}^{k}p_{i}}\)
Niech \(\displaystyle{ t_{i}}\) będzie rzędem \(\displaystyle{ 10 \mod p_{i}}\).
Wtedy \(\displaystyle{ 10^{nww\left(t_{1}, \ t_{2}, \ \ldots , \ t_{k}\right)}-1}\) jest poszukiwaną liczbą.

Jedyny problem to obliczanie tych rzędów. Nie znam żadnego algorytmu skuteczniejszego niż sprawdzanie kolejnych potęg czy samych dzielników \(\displaystyle{ p-1}\).

Dla przykładu wróćmy do naszego \(\displaystyle{ 130013=13 \cdot 73 \cdot 137}\).

\(\displaystyle{ p_{1}=13}\) i jak wiemy \(\displaystyle{ t_{1}=6}\).

\(\displaystyle{ p_{2}=73}\). Naszego rzędu będziemy szukać wśród \(\displaystyle{ 12}\) dzielników \(\displaystyle{ 72}\). \(\displaystyle{ 1}\) i \(\displaystyle{ 2}\) natychmiast odpadają. \(\displaystyle{ 3}\) po krótkich obliczeniach też. Zauważamy, że \(\displaystyle{ 10^{4} \equiv -1 \pmod{73}}\), więc \(\displaystyle{ t_{2}=8}\).

\(\displaystyle{ p_{3}=137}\). Naszego rzędu będziemy szukać wśród \(\displaystyle{ 8}\) dzielników \(\displaystyle{ 136}\). Tu znów rzędem okazuje się \(\displaystyle{ 8}\).

Nasz poszukiwany najmniejszy wykładnik, to \(\displaystyle{ nww\left(6, \ 8, \ 8\right)}\), a więc zgodnie z oczekiwaniami \(\displaystyle{ 24}\).

[matinf]

Dzięki wielkie za pomoc.