Как се решава това квадратично сравнение

[Гост]

Как да реша това квадратично сравнение
x^2 = 6 (mod 23)

[peyo]

Как да реша това квадратично сравнение
x^2 = 6 (mod 23)

Нямам представа какъв е нормалния начин за решаване на такива уравнения. Това обаче не ни пречи да го решим по какъвто начин искаме.

Този mod предполагам означава деление с остатък така, че уравнениято може да се напише като:
$x^2 = 23k + 6$

Където k някакво цяло число. Положително за предпочитане. Тогава:

$x = \sqrt{23k + 6}$

И сега ще бъде много удобно ако можем това под корена да представим като израз степен на двойката. За момента не се сещам добър начин. Вместо това ще изследваме сериите:

Код: Избери целия код

In [141]: for k in range(0,500):
     ...:     a = 23*k+6
     ...:     if int(sqrt(a)) == sqrt(a):
     ...:         print(k,a,sqrt(a))

5 121 11
6 144 12
50 1156 34
53 1225 35
141 3249 57
146 3364 58
278 6400 80
285 6561 81
461 10609 103
470 10816 104

Забелязваме нещо интересно:

In [134]: 34-11
Out[134]: 23

In [135]: 57-34
Out[135]: 23

In [136]: 103-80
Out[136]: 23

Първо решенията вървят по двойки едно до друго и второ разликата между съседните двойки е 23. Това ни е достатъчно да напишем отговора:

$ x= 23i + 11 \ , \ i \ge 0 \cup x= 23j + 12 \ , \ j \ge 0$

Да направим проверка:

Код: Избери целия код

In [143]: for i in range(0,10):
     ...:     print(i,(i*23 + 11), (i*23+12))
     ...:
0 11 12
1 34 35
2 57 58
3 80 81
4 103 104
5 126 127
6 149 150
7 172 173
8 195 196
9 218 219

Лоокс гоод.

[pal702004]

Как да реша това квадратично сравнение
x^2 = 6 (mod 23)

Като се провери $x$ от 5 до 11.

В случая сравнението е вярно при $x=11$, а значи всички решения са

$x=23k \pm 11, k \in \mathbb{Z}$

или по същата нотация: $x \equiv \pm 11 \pmod {23}$

[Гост]

схванах идеята
но отговора е 12

[pal702004]

схванах идеята
но отговора е 12

Отговорите са два. И ако наистина си схванал идеята, ще разбереш, че $-11\equiv 12 \pmod {23}$

(помисли има ли разлика м/у $23k+12$ и $23k-11,\; k \in \mathbb{Z}$)