znalezc wszystkie rozwiazania kongruencji

[kriegor]

jak w temacie:
\(\displaystyle{ x^2\equiv -1\pmod{4225}}\)
nie wiem jak sie za to zabrac no bo owszem to jest rownowazne z

\(\displaystyle{ \begin{cases} x^2\equiv -1 \pmod{25}\\ x^2\equiv -1 \pmod{169}\end{cases}}\)
ale jakos nie widze zeby to cos upraszczalo

[Ponewor]

idąc dalej twoim sposobem można robić mod 5 i mod 13 i wyszło na razie:

\(\displaystyle{ \begin{cases} x \equiv 7 \pmod{25} \vee x \equiv 18 \pmod{25} \\ x \equiv 70 \pmod{25} \vee x \equiv 99 \pmod{169} \end{cases}}\)

i pewnie uda się coś z tego zaraz wycisnąć, ale pewnie i tak zaraz przyjdzie ktoś kto ma gotowe algorytmy na takie rzeczy.

[kriegor]

co znaczy "robic mod 5 i mod 13" ?
bo jesli to to co mysle to nie mozna, a mysle ze chodzi Ci o rozbicie kazdej z kongruencji 25 i 169 na dwie tzn mod 5 i mod 13
a modulniki w chinskim o resztach maja byc parami wzglednie pierwsze wiec potegi liczby pierwszej nie mozna juz potraktowac chinskim o resztach

[Ponewor]

Ja nie korzystałem z żadnego twierdzenia.


\(\displaystyle{ x^2\equiv -1 \pmod{25} \Rightarrow x^2\equiv -1 \pmod{5} \Rightarrow x\equiv 2 \pmod{5} \vee x\equiv 3\pmod{5} \Rightarrow x\equiv 2 \pmod{25} \vee x\equiv 3\pmod{25} \vee x\equiv 7 \pmod{25} \vee x\equiv 8\pmod{25} \vee \\ x\equiv 12 \pmod{25} \vee x\equiv 13\pmod{25} \vee x\equiv 17 \pmod{25} \vee x\equiv 18\pmod{25} \vee \\ x\equiv 22 \pmod{25} \vee x\equiv 23\pmod{25}}\)

Więc teraz ograniczyliśmy się do sprawdzenia 10 przypadków. Można uprościć sobie robotę zauważając, że wystarczy sprawdzić tylko pierwsze 5 przypadków. Analogicznie mod 169. Tutaj przypadków do sprawdzenia ręcznie jest 13. Na windowsowym kalkulatorku z włączoną historią trwa to niecałe pół minutki.

Pomysłu jak z tego sklecić 4225 na razie nie mam.

[ksisquare]

\(\displaystyle{ 4225 = 5^2 \cdot 13^2}\)

Kod: Zaznacz cały

http://pari.math.u-bordeaux.fr/

for(x = 1, 4224, if( Mod(x,4225)^2 == -1, print(x " " x^2 % 5 " " x^2 % 13)))

Kod: Zaznacz cały

268     4       12
1282    4       12
2943    4       12
3957    4       12