Quadratic deductions by simple modulus

Revision en1, by EJIC_B_KEDAX, 2024-07-29 00:54:10

Hello, Codeforces!

Today I'm going to talk about an unpopular technique in number theory.

Definition and elementary properties

Def. Let $$$p > 2$$$ be a prime number, then we will call all $$$1 \le x \le p - 1$$$ modulo $$$p$$$ such that the equation $$$a^2 \equiv x \pmod{p}$$$ has solutions and quadratic non-subtraction otherwise. Note that $$$0$$$ is neither quadratic deduction nor quadratic non-deduction.

Theorem: Quadratic deduction and cradratic non-deduction are equally divided.

“Proof”

It turns out that all numbers split into pairs $$$x$$$ and $$$-x$$$, so each quadratic deduction has exactly $$$2$$$ roots, with each number being the root of some quadratic deduction $$$\implies$$$ of quadratic deductions of exactly $$$\frac{p - 1}{2}$$$ $$$\implies$$$ of quadratic non-deductions $$$p - 1 - \frac{p - 1}{2} = \frac{p - 1}{2}$$$.

Theorem: Denote by

Unable to parse markup [type=CF_MATHJAX]

$$$H \cdot B = H$$$
$$$H \cdot H = B$$$

.

“Proof”

$$$B \cdot B = B$$$

Let $$$x$$$ and $$$y$$$ be quadratic deductions, let $$$a^2 \equiv x \pmod{p}$$$

Unable to parse markup [type=CF_MATHJAX]

$$$. Then $$$(ab)^2 \equiv xy \pmod{p}$.

$$$H \cdot B = H$$$

Let $$$x$$$ be a quadratic nondeduction and $$$y$$$ be a quadratic deduction, we prove that $$$\frac{1}{y}$$$ is also a quadratic deduction. Let $$$b^2 \equiv y \pmod{p}$$$, then $$$(\frac{1}{b})^2 \equiv \frac{1}{y} \pmod{p}$$$.

$$$x \cdot y \equiv z \pmod{p}$$$

Unable to parse markup [type=CF_MATHJAX]

is a quadratic deduction, then $$$x \equiv z \cdot \frac{1}{y} \pmod{p}$$$ $$$\implies$$$ $$$x$$$ is quadratically deductible, since $$$z$$$ is quadratically deductible and $$$\frac{1}{y}$$$ is quadratically deductible. The contradiction $$$\implies$$$ $$$z$$$ is quadratically non-deductive.

$$$H \cdot H = B$$$

Let $$$x$$$ and $$$y$$$ be quadratic nondeductions, $$$x \cdot y \equiv z \pmod{p}$$$ and $$$z$$$ a quadratic nondeduction, and $$$a_1, a_2, a_3 \cdots, a_{\frac{p - 1}{2}}$$$

Unable to parse markup [type=CF_MATHJAX]

. All numbers in this set are quadratic nonconvex, but there are $$$2$$$ equal numbers in the set $$$\frac{p + 1}{2}$$$, and this is more than the quadratic nonconvex $$$\implies$$$ in the set. Note that if $$$xk \equiv xl \pmod{p}$$$ and $$$x$$$ is not a multiple of $$$p$$$, then $$$k \equiv l \pmod{p}$$$. So in the set $$$a_1, a_2, a_3 \cdots, a_{\frac{p - 1}{2}}, y$$$ there are equal numbers, but in this set all numbers are different ($$$a_i \ne a_j$$$ since we took different quadratic deductions, and $$$y \ne a_i$$$ since $$$y$$$ is quadratic non-deduction and $$$a_i$$$ is quadratic deduction). Contradiction, so $$$z$$$ is a quadratic deduction. .

With these two theorems, we can already solve 103428K - Tiny Stars.

How to check if the number is deductive or non-deductive?

There are several ways to check if a number is quadratic deduction. In this blog, we will look at just one of them, you can read about [Gauss's lemma](https://en.wikipedia.org/wiki/Gauss%27s_lemma_(number_theory)) and law of quadratic reciprocity.

Euler's criterion

$$$a$$$ is a quadratic deduction modulo $$$p$$$ if and only if $$$a^{{\frac{p - 1}{2}}} \equiv 1 \pmod{p}$$$, and a quadratic non-deduction if and only if $$$a^{\frac{p - 1}{2}} \equiv -1 \pmod{p}$$$.

“Proof”

Let $$$a$$$ be a quadratic deduction and $$$x^2 \equiv a \pmod{p}$$$, then $$$a^{\frac{p - 1}{2}} \equiv 1 \pmod{p}$$$, since $$$(x^2)^{\frac{p - 1}{2}} = x^{p - 1} \equiv 1 \pmod{p}$$$, and this is true by Fermat's small theorem.

Consider the polynomial $$$x^{{\frac{p - 1}{2}} - 1$$$ modulo $$$p$$$, its degree is $$$\frac{p - 1}{2}$$$ and we have already found it has $$$\frac{p - 1}{2}$$$ roots $$$\implies$$$ no more roots $$$\implies$$$ if $$$b$$$ is quadratically non-degenerate, then $$$b^{\frac{p - 1}{2}} \equiv -1 \pmod{p}$$$.

Consequence: $$$-1$$$ is quadratically deductible if and only if $$$p = 4k + 1$$$, for some natural $$$k$$$, and quadratically non-deductible if and only if $$$p = 4k + 3$$$, for some natural $$$k$$$.

Clearly, the complexity of the number check is $$$O(\log_2p)$$$.

“Code”

bool check(int a, int p) { return power(a, (p — 1) / 2, p) == 1; } ~~~~

Finding $$$i$$$ modulo $$$p$$$

Def. $$$i$$$ is such a number that $$$i^2 = -1$$$ $$$\implies$$$ $$$i$$$ modulo $$$p$$$ let us call such a number that $$$i ^ 2 \equiv -1 \pmod{p}$$$.

Algorithm: If $$$p = 4k + 3$$$ for some natural $$$k$$$, then there is no such $$$i$$$. If $$$p = 2$$$, then $$$i = 1$$$. Otherwise consider the quadratic non-deduction of $$$a$$$, by Euler's criterion we know that $$$a^{\frac{p - 1}{2}}} \equiv -1 \pmod{p}$$$, then $$$a^{\frac{p - 1}{4}} \equiv i \pmod{p}$$$. All that remains is to find a quadratic non-deduction, for this we take a random $$$1 \le a \le p - 1$$$ and check it for $$$O(\log_2p)$$$, if it is a quadratic deduction then take another random $$$a$$$. Since the deductions and non-deductions are equal, we need $$$O(1)$$$ of such checks, so the total complexity of the algorithm is $$$O(\log_2p)$$$.

“Code”

int power(int a, int x, int mod) { int res = 1; while (x) { if (x % 2 == 1) { res = 1ll * res * a % mod; } a = 1ll * a * a * a % mod; x /= 2; } return res; }

bool check(int a, int p) { return power(a, (p — 1) / 2, p) == 1; }

int find_i(int p) { if (p % 4 == 3) { return -1; } if (p == 2) { return 1; } while (true) { int a = mt() % (p — 1) + 1; if (!check(a, p)) { return power(a, (p — 1) / 4, p); } } } ~~~~

Tags math, number theory

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en11 English EJIC_B_KEDAX 2024-07-30 15:37:55 0 (published)
ru16 Russian EJIC_B_KEDAX 2024-07-30 15:37:29 0 (опубликовано)
en10 English EJIC_B_KEDAX 2024-07-30 15:21:42 8
ru15 Russian EJIC_B_KEDAX 2024-07-30 15:14:38 11
en9 English EJIC_B_KEDAX 2024-07-30 15:14:09 74
en8 English EJIC_B_KEDAX 2024-07-29 01:34:33 29 Tiny change: 's, so the total complexity of the al' -> 's, so the expected running time of the al'
ru14 Russian EJIC_B_KEDAX 2024-07-29 01:34:09 26
en7 English EJIC_B_KEDAX 2024-07-29 01:32:56 96
en6 English EJIC_B_KEDAX 2024-07-29 01:30:19 1 Tiny change: 'y="Proof">.\nFirst, l' -> 'y="Proof">\nFirst, l'
en5 English EJIC_B_KEDAX 2024-07-29 01:29:57 117
en4 English EJIC_B_KEDAX 2024-07-29 01:26:48 424
ru13 Russian EJIC_B_KEDAX 2024-07-29 01:19:13 55
en3 English EJIC_B_KEDAX 2024-07-29 01:18:47 97 Tiny change: 's's lemma](https://en' -> 's's lemma] https://en'
en2 English EJIC_B_KEDAX 2024-07-29 01:09:44 23
en1 English EJIC_B_KEDAX 2024-07-29 00:54:10 6734 Initial revision for English translation (saved to drafts)
ru12 Russian EJIC_B_KEDAX 2024-07-29 00:46:05 1 Мелкая правка: 'Привет Codeforce' -> 'Привет, Codeforce'
ru11 Russian EJIC_B_KEDAX 2024-07-22 02:26:00 5
ru10 Russian EJIC_B_KEDAX 2024-07-22 02:23:16 1674 Мелкая правка: 'ществует. Иначе ра' -> 'ществует. Если $p = 2$, то $i = 1$. Иначе ра'
ru9 Russian EJIC_B_KEDAX 2024-07-22 01:53:33 2378 Мелкая правка: 'oiler>\n\n' -> 'oiler>\n\nНахождение $i$ по модулю $p$\n------------------'
ru8 Russian EJIC_B_KEDAX 2024-07-22 00:46:55 17 Мелкая правка: ' while (x) {\n ' -> ' while (x != 0) {\n '
ru7 Russian EJIC_B_KEDAX 2024-07-22 00:20:46 2467 Мелкая правка: '428K].\n\nКак пров' -> '428K].\n\n==================\nКак пров'
ru6 Russian EJIC_B_KEDAX 2024-07-21 22:58:36 18
ru5 Russian EJIC_B_KEDAX 2024-07-21 22:46:10 73 Мелкая правка: '**Опр.** П' -> '[problem:103428K]**Опр.** П'
ru4 Russian EJIC_B_KEDAX 2024-07-21 22:40:56 1656 Мелкая правка: 'd{p}$.\n\n$$H \c' -> 'd{p}$.\n\n\n$$H \c'
ru3 Russian EJIC_B_KEDAX 2024-07-21 21:39:52 325 Мелкая правка: 'oiler>\n\n' -> 'oiler>\n\n\n'
ru2 Russian EJIC_B_KEDAX 2024-07-21 21:30:49 482 Мелкая правка: 'n**Теорема**: Квадратич' -> 'n**Теорема:** Квадратич'
ru1 Russian EJIC_B_KEDAX 2024-07-21 21:12:13 344 Первая редакция (сохранено в черновиках)