znaleźc wielokrotność liczby, zbudowana z samych dziewiątek
-
- Użytkownik
- Posty: 1922
- Rejestracja: 26 mar 2012, o 18:52
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 695 razy
- Pomógł: 4 razy
znaleźc wielokrotność liczby, zbudowana z samych dziewiątek
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}\).
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}\).
Ostatnio zmieniony 5 wrz 2014, o 23:17 przez Ponewor, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
- Ponewor
- Moderator
- Posty: 2218
- Rejestracja: 30 sty 2012, o 21:05
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 70 razy
- Pomógł: 297 razy
znaleźc wielokrotność liczby, zbudowana z samych dziewiątek
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.
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.
-
- Użytkownik
- Posty: 1922
- Rejestracja: 26 mar 2012, o 18:52
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 695 razy
- Pomógł: 4 razy
znaleźc wielokrotność liczby, zbudowana z samych dziewiątek
Tak, 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.
\(\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ę
-
- Użytkownik
- Posty: 1922
- Rejestracja: 26 mar 2012, o 18:52
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 695 razy
- Pomógł: 4 razy
znaleźc wielokrotność liczby, zbudowana z samych dziewiątek
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}\) ?
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
- Moderator
- Posty: 2218
- Rejestracja: 30 sty 2012, o 21:05
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 70 razy
- Pomógł: 297 razy
znaleźc wielokrotność liczby, zbudowana z samych dziewiątek
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.
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.
-
- Użytkownik
- Posty: 1922
- Rejestracja: 26 mar 2012, o 18:52
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 695 razy
- Pomógł: 4 razy
znaleźc wielokrotność liczby, zbudowana z samych dziewiątek
Oj, trudne to zadanie.
\(\displaystyle{ 8 \mid n \Leftrightarrow 10001 \mid 10^{n}-1}\)
Spróbuję tym zająć się wieczorem.
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}\) ?
\(\displaystyle{ 8 \mid n \Leftrightarrow 10001 \mid 10^{n}-1}\)
Spróbuję tym zająć się wieczorem.
A trudno ten warunek znaleźć ?Potem musisz znaleźć analogiczny warunek na
\(\displaystyle{ 13 \mid 10^{n}-1}\)
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
- Moderator
- Posty: 2218
- Rejestracja: 30 sty 2012, o 21:05
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 70 razy
- Pomógł: 297 razy
znaleźc wielokrotność liczby, zbudowana z samych dziewiątek
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.
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}\).
Ukryta treść:
-
- Użytkownik
- Posty: 1922
- Rejestracja: 26 mar 2012, o 18:52
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 695 razy
- Pomógł: 4 razy
znaleźc wielokrotność liczby, zbudowana z samych dziewiątek
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}\))
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
- Moderator
- Posty: 2218
- Rejestracja: 30 sty 2012, o 21:05
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 70 razy
- Pomógł: 297 razy
znaleźc wielokrotność liczby, zbudowana z samych dziewiątek
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ć.matinf pisze:Ale czy dowód z prawa na lewo nie wychodzi od razu z racji definicji rzędu ?
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}\).
-
- Użytkownik
- Posty: 1922
- Rejestracja: 26 mar 2012, o 18:52
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 695 razy
- Pomógł: 4 razy
znaleźc wielokrotność liczby, zbudowana z samych dziewiątek
Ponewor pisze:
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
- Moderator
- Posty: 2218
- Rejestracja: 30 sty 2012, o 21:05
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 70 razy
- Pomógł: 297 razy
znaleźc wielokrotność liczby, zbudowana z samych dziewiątek
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}\).
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}\).