Рассмотрим ситуацию, когда $$$x^2 \equiv y^2 \pmod{p}$$$, это равносильно тому, что $$$x^2 - y^2 \equiv 0 \pmod{p}$$$. Используем формулу разности квадратов, получим $$$(x - y) \cdot (x + y) \equiv 0 \pmod{p}$$$. Отсюда следует, что либо $$$x - y \equiv 0 \pmod{p}$$$, либо $$$x + y \equiv 0 \pmod{p}$$$, то есть либо $$$x \equiv y \pmod{p}$$$, либо $$$x \equiv -y \pmod{p}$$$.

Получается, что все числа разбиваются на пары $$$x$$$ и $$$-x$$$, значит у каждого квадратичного вычета ровно $$$2$$$ корня, при этом каждое число является корнем какого-то квадратичного вычета $$$\implies$$$ квадратичных вычетов ровно $$$\frac{p - 1}{2}$$$ $$$\implies$$$ квадратичных невычетов $$$p - 1 - \frac{p - 1}{2} = \frac{p - 1}{2}$$$.

Пусть $$$x$$$ и $$$y$$$ квадратичные вычеты, пусть $$$a^2 \equiv x \pmod{p}$$$ и $$$b^2 \equiv y \pmod{p}$$$. Тогда $$$(ab)^2 \equiv xy \pmod{p}$$$.

Пусть $$$x$$$ квадратичный невычет, а $$$y$$$ квадратичный вычет, докажем, что $$$\frac{1}{y}$$$ тоже квадратичный вычет. Пусть $$$b^2 \equiv y \pmod{p}$$$, тогда $$$(\frac{1}{b})^2 \equiv \frac{1}{y} \pmod{p}$$$.

$$$x \cdot y \equiv z \pmod{p}$$$, предположим, что $$$z$$$ квадратичный вычет, тогда $$$x \equiv z \cdot \frac{1}{y} \pmod{p}$$$ $$$\implies$$$ $$$x$$$ квадратичный вычет, так как $$$z$$$ квадратичный вычет и $$$\frac{1}{y}$$$ квадратичный вычет. Противоречие $$$\implies$$$ $$$z$$$ квадратичный невычет.

Пусть $$$x$$$ и $$$y$$$ квадратичные невычеты, $$$x \cdot y \equiv z \pmod{p}$$$ и $$$z$$$ квадратичный невычет, а $$$a_1, a_2, a_3 \cdots, a_{\frac{p - 1}{2}}$$$ все квадратичные вычеты. Рассмотрим следующий набор вычетов $$$xa_1, xa_2, xa_3, \cdots, xa_{\frac{p - 1}{2}}, xy$$$. В этом наборе все числа квадратичные невычеты, но чисел в наборе $$$\frac{p + 1}{2}$$$, а это больше чем квадратичных невычетов $$$\implies$$$ в наборе есть $$$2$$$ равных числа. Заметим, что если $$$xk \equiv xl \pmod{p}$$$ и $$$x$$$ не кратно $$$p$$$, то $$$k \equiv l \pmod{p}$$$. Значит в наборе $$$a_1, a_2, a_3 \cdots, a_{\frac{p - 1}{2}}, y$$$ есть равные числа, но в этом наборе все числа различны ($$$a_i \ne a_j$$$, так как мы взяли различные квадратичные вычеты, а $$$y \ne a_i$$$, так как $$$y$$$ квадратичный невычет, а $$$a_i$$$ квадратичный вычет). Противоречие, значит $$$z$$$ квадратичный вычет.

Для начала докажем, что если $$$a$$$ не делится на $$$p$$$, то $$$a^{\frac{p - 1}{2}} \equiv \pm 1 \pmod{p}$$$. По малой теореме Ферма $$$a^{p - 1} \equiv 1 \pmod{p}$$$, выше было доказано, что любой квадратичный вычет имеет ровно $$$2$$$ корня, у $$$1$$$ это $$$1$$$ и $$$-1$$$. $$$(a^{\frac{p - 1}{2}})^2 = a^{p - 1}$$$ $$$\implies$$$ $$$a^{\frac{p - 1}{2}} \equiv \pm 1 \pmod{p}$$$.

Пусть $$$a$$$ квадратичный вычет и $$$x^2 \equiv a \pmod{p}$$$, тогда $$$a^{\frac{p - 1}{2}} \equiv 1 \pmod{p}$$$, так как $$$(x^2)^{\frac{p - 1}{2}} = x^{p - 1} \equiv 1 \pmod{p}$$$, а это верно по малой теореме Ферма.

Рассмотрим многочлен $$$x^{\frac{p - 1}{2}} - 1$$$ по модулю $$$p$$$, его степень $$$\frac{p - 1}{2}$$$ и мы уже нашли у него $$$\frac{p - 1}{2}$$$ корней $$$\implies$$$ больше корней у него нет $$$\implies$$$ если $$$b$$$ квадратичный невычет, то $$$b^{\frac{p - 1}{2}} \equiv -1 \pmod{p}$$$.

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

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

mt19937_64 mt(123);

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 % 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);
        }
    }
}