szukanie zaawansowane
 [ Posty: 8 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 7 maja 2016, o 10:26 
Użytkownik

Posty: 33
Lokalizacja: z daleka
Poszukujemy rozwiązań równania:

(n^{2} - 2)  \% k = x

gdzie k jest liczbą pierwszą.

Dane są k i x. Szukana to n.

Dla przykładu dla:

(n^{2} - 2)  \% 127 = 122

prawidłowe wyniki to:

n = 39
n = 88

Czy istnieje jakiś sposób aby zawsze prosto licząc "na palcach" wyznaczyć wartości n?
Góra
Mężczyzna Offline
PostNapisane: 7 maja 2016, o 14:02 
Użytkownik

Posty: 718
Rozwiązać równanie w całkowitych n^2=127c+122-(-2) (c to dowolna całkowita)

Dla c=11 otrzymasz n=39, a dla c=60 otrzymasz n=88. Dalej będziesz otrzymywał liczby postaci n=127c+39 i 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 39+88=127, czyli wystarczy znaleźć pierwsze rozwiązanie, a drugie z 127-n_1=n_2
Góra
Mężczyzna Offline
PostNapisane: 7 maja 2016, o 18:09 
Użytkownik

Posty: 33
Lokalizacja: z daleka
Ok.

Trochę więc zredukujmy problem.

Weźmy równanie w całkowitych:

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.
Góra
Mężczyzna Offline
PostNapisane: 7 maja 2016, o 18:11 
Użytkownik

Posty: 12615
Nie ma potrzeby realizowania tego na komputerze:
prawa strona dzieli się przez dwa, więc gdyby n było rozwiązaniem, to n^{2} dzieliłoby się przez 2, ale skoro n całkowite, to 2|n^{2} \Rightarrow 4|n^{2}, ale 2^{10000}+2\equiv 2\pmod{4}, sprzeczność.
Góra
Mężczyzna Offline
PostNapisane: 7 maja 2016, o 18:16 
Użytkownik

Posty: 33
Lokalizacja: z daleka
Kurcze zapomniałem dodać we wzorku c.

Powinien wyglądać tak:

n^{2} =  2^{10000} c + 2

Już edytowałem post.
Góra
Mężczyzna Offline
PostNapisane: 7 maja 2016, o 18:19 
Użytkownik

Posty: 12615
Jeżeli 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 2 musiałoby dzielić n^{2}, co prowadzi do wniosku, że 4 dzieli n^{2}, a to jest sprzeczność, bo reszta z dzielenia 2^{10000}c przez 4 to jest zero, więc dla liczby większej o 2 to jest 2.
Góra
Mężczyzna Offline
PostNapisane: 7 maja 2016, o 18:24 
Użytkownik

Posty: 33
Lokalizacja: z daleka
A jakiś pomysł aby rozgryźć przykładowo coś takiego:

n^{2} =  2^{10000} c + 1

Tutaj już to chyba nie jest tak oczywiste.
Góra
Mężczyzna Offline
PostNapisane: 7 maja 2016, o 18:46 
Użytkownik

Posty: 12615
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 0 lub 1 z dzielenia przez 3, a zatem ponieważ 2^{10000}\equiv 1\pmod{3}, zatem nie może być c\equiv 1\pmod{3}, jeśli chcemy, by jakieś rozwiązanie istniało.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 8 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 równanie z symbolem newtona.  apacz  5
 [zadanie] Rozwiąż równanie  My4tic  1
 równanie - zadanie 4  fishman4  2
 Rozwiąż równanie z silnią  kuzio87  1
 równanie z silnią  rObO87  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl