Pewne równanie modulo - poszukiwane wartości
-
- Użytkownik
- Posty: 32
- Rejestracja: 8 wrz 2015, o 19:21
- Płeć: Mężczyzna
- Lokalizacja: z daleka
- Podziękował: 1 raz
Pewne równanie modulo - poszukiwane wartości
Poszukujemy rozwiązań równania:
\(\displaystyle{ (n^{2} - 2) \% k = x}\)
gdzie \(\displaystyle{ k}\) jest liczbą pierwszą.
Dane są \(\displaystyle{ k}\) i \(\displaystyle{ x}\). Szukana to \(\displaystyle{ n}\).
Dla przykładu dla:
\(\displaystyle{ (n^{2} - 2) \% 127 = 122}\)
prawidłowe wyniki to:
\(\displaystyle{ n = 39}\)
\(\displaystyle{ n = 88}\)
Czy istnieje jakiś sposób aby zawsze prosto licząc "na palcach" wyznaczyć wartości \(\displaystyle{ n}\)?
\(\displaystyle{ (n^{2} - 2) \% k = x}\)
gdzie \(\displaystyle{ k}\) jest liczbą pierwszą.
Dane są \(\displaystyle{ k}\) i \(\displaystyle{ x}\). Szukana to \(\displaystyle{ n}\).
Dla przykładu dla:
\(\displaystyle{ (n^{2} - 2) \% 127 = 122}\)
prawidłowe wyniki to:
\(\displaystyle{ n = 39}\)
\(\displaystyle{ n = 88}\)
Czy istnieje jakiś sposób aby zawsze prosto licząc "na palcach" wyznaczyć wartości \(\displaystyle{ n}\)?
Pewne równanie modulo - poszukiwane wartości
Rozwiązać równanie w całkowitych \(\displaystyle{ n^2=127c+122-(-2)}\) (\(\displaystyle{ c}\) to dowolna całkowita)
Dla \(\displaystyle{ c=11}\) otrzymasz \(\displaystyle{ n=39}\), a dla \(\displaystyle{ c=60}\) otrzymasz \(\displaystyle{ n=88}\). Dalej będziesz otrzymywał liczby postaci \(\displaystyle{ n=127c+39}\) i \(\displaystyle{ n=127c+88}\), które oczywiście też są rozwiązaniami równania z zadania.
Nie mam pomysłu jak to zrobić jeszcze prościej. Może można by było wykorzystać fakt, że \(\displaystyle{ 39+88=127}\), czyli wystarczy znaleźć pierwsze rozwiązanie, a drugie z \(\displaystyle{ 127-n_1=n_2}\)
Dla \(\displaystyle{ c=11}\) otrzymasz \(\displaystyle{ n=39}\), a dla \(\displaystyle{ c=60}\) otrzymasz \(\displaystyle{ n=88}\). Dalej będziesz otrzymywał liczby postaci \(\displaystyle{ n=127c+39}\) i \(\displaystyle{ n=127c+88}\), które oczywiście też są rozwiązaniami równania z zadania.
Nie mam pomysłu jak to zrobić jeszcze prościej. Może można by było wykorzystać fakt, że \(\displaystyle{ 39+88=127}\), czyli wystarczy znaleźć pierwsze rozwiązanie, a drugie z \(\displaystyle{ 127-n_1=n_2}\)
-
- Użytkownik
- Posty: 32
- Rejestracja: 8 wrz 2015, o 19:21
- Płeć: Mężczyzna
- Lokalizacja: z daleka
- Podziękował: 1 raz
Pewne równanie modulo - poszukiwane wartości
Ok.
Trochę więc zredukujmy problem.
Weźmy równanie w całkowitych:
\(\displaystyle{ n^{2} = 2^{10000} c + 2}\)
Jak to policzyć dość szybko? Nie mówię tutaj oczywiście o liczeniu w pamięci, a o realizację na komputerze.
Trochę więc zredukujmy problem.
Weźmy równanie w całkowitych:
\(\displaystyle{ n^{2} = 2^{10000} c + 2}\)
Jak to policzyć dość szybko? Nie mówię tutaj oczywiście o liczeniu w pamięci, a o realizację na komputerze.
Ostatnio zmieniony 7 maja 2016, o 18:14 przez Morfeo, łącznie zmieniany 1 raz.
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Pewne równanie modulo - poszukiwane wartości
Nie ma potrzeby realizowania tego na komputerze:
prawa strona dzieli się przez dwa, więc gdyby \(\displaystyle{ n}\) było rozwiązaniem, to \(\displaystyle{ n^{2}}\) dzieliłoby się przez \(\displaystyle{ 2}\), ale skoro \(\displaystyle{ n}\) całkowite, to \(\displaystyle{ 2|n^{2} \Rightarrow 4|n^{2}}\), ale \(\displaystyle{ 2^{10000}+2\equiv 2\pmod{4}}\), sprzeczność.
prawa strona dzieli się przez dwa, więc gdyby \(\displaystyle{ n}\) było rozwiązaniem, to \(\displaystyle{ n^{2}}\) dzieliłoby się przez \(\displaystyle{ 2}\), ale skoro \(\displaystyle{ n}\) całkowite, to \(\displaystyle{ 2|n^{2} \Rightarrow 4|n^{2}}\), ale \(\displaystyle{ 2^{10000}+2\equiv 2\pmod{4}}\), sprzeczność.
-
- Użytkownik
- Posty: 32
- Rejestracja: 8 wrz 2015, o 19:21
- Płeć: Mężczyzna
- Lokalizacja: z daleka
- Podziękował: 1 raz
Pewne równanie modulo - poszukiwane wartości
Kurcze zapomniałem dodać we wzorku \(\displaystyle{ c}\).
Powinien wyglądać tak:
\(\displaystyle{ n^{2} = 2^{10000} c + 2}\)
Już edytowałem post.
Powinien wyglądać tak:
\(\displaystyle{ n^{2} = 2^{10000} c + 2}\)
Już edytowałem post.
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Pewne równanie modulo - poszukiwane wartości
Jeżeli \(\displaystyle{ c}\) jest liczbą całkowitą, to nic to nie zmienia, bo wtedy i tak prawa strona jest podzielna przez dwa jako suma liczb parzystych, a więc \(\displaystyle{ 2}\) musiałoby dzielić \(\displaystyle{ n^{2}}\), co prowadzi do wniosku, że \(\displaystyle{ 4}\) dzieli \(\displaystyle{ n^{2}}\), a to jest sprzeczność, bo reszta z dzielenia \(\displaystyle{ 2^{10000}c}\) przez \(\displaystyle{ 4}\) to jest zero, więc dla liczby większej o \(\displaystyle{ 2}\) to jest \(\displaystyle{ 2}\).
-
- Użytkownik
- Posty: 32
- Rejestracja: 8 wrz 2015, o 19:21
- Płeć: Mężczyzna
- Lokalizacja: z daleka
- Podziękował: 1 raz
Pewne równanie modulo - poszukiwane wartości
A jakiś pomysł aby rozgryźć przykładowo coś takiego:
\(\displaystyle{ n^{2} = 2^{10000} c + 1}\)
Tutaj już to chyba nie jest tak oczywiste.
\(\displaystyle{ n^{2} = 2^{10000} c + 1}\)
Tutaj już to chyba nie jest tak oczywiste.
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Pewne równanie modulo - poszukiwane wartości
No ja nie mam pomysłów, nie znam się na algorytmach.
Można ręcznie wykluczyć pewne możliwości, np. kwadrat liczby całkowitej daje reszty \(\displaystyle{ 0}\) lub \(\displaystyle{ 1}\) z dzielenia przez \(\displaystyle{ 3}\), a zatem ponieważ \(\displaystyle{ 2^{10000}\equiv 1\pmod{3}}\), zatem nie może być \(\displaystyle{ c\equiv 1\pmod{3}}\), jeśli chcemy, by jakieś rozwiązanie istniało.
Można ręcznie wykluczyć pewne możliwości, np. kwadrat liczby całkowitej daje reszty \(\displaystyle{ 0}\) lub \(\displaystyle{ 1}\) z dzielenia przez \(\displaystyle{ 3}\), a zatem ponieważ \(\displaystyle{ 2^{10000}\equiv 1\pmod{3}}\), zatem nie może być \(\displaystyle{ c\equiv 1\pmod{3}}\), jeśli chcemy, by jakieś rozwiązanie istniało.