Pewne równanie modulo - poszukiwane wartości

[Morfeo]

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

[dec1]

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

[Morfeo]

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.

[Premislav]

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ść.

[Morfeo]

Kurcze zapomniałem dodać we wzorku \(\displaystyle{ c}\).

Powinien wyglądać tak:

\(\displaystyle{ n^{2} = 2^{10000} c + 2}\)

Już edytowałem post.

[Premislav]

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

[Morfeo]

A jakiś pomysł aby rozgryźć przykładowo coś takiego:

\(\displaystyle{ n^{2} = 2^{10000} c + 1}\)

Tutaj już to chyba nie jest tak oczywiste.

[Premislav]

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.