Liczby kwadratowe i niekwadratowe modulo. Wybrane zagadnienia

22.04.2023

Element odwrotny modulo $m$

Twierdzenie K1
Niech $m\in {\mathbb{Z}}_{+}$. Dla liczby $k$ istnieje taka liczba $x$, że

$xk\equiv 1(\mathrm{mod}m)$

wtedy i tylko wtedy, gdy $gcd(k,m)=1$.

Dowód

$⟹$

Z założenia istnieje taka liczba $x$, że

$xk\equiv 1(\mathrm{mod}m)$

Zatem dla pewnego $r\in \mathbb{Z}$ jest

$xk=1+rm$

Czyli $xk-rm=1$. Wynika stąd, że $gcd(k,m)$ dzieli $1$, co oznacza, że $gcd(k,m)=1$.

$⟸$

Z założenia $gcd(k,m)=1$. Z lematu Bézouta (zobacz C71) wynika, że istnieją takie liczby całkowite $x,y$, że

$kx+my=1$

Zatem modulo $m$ dostajemy

$kx\equiv 1(\mathrm{mod}m)$

Co kończy dowód.
□

Definicja K2
Niech $m\in {\mathbb{Z}}_{+}$. Liczbę $x$ taką, że

$x\cdot k\equiv 1(\mathrm{mod}m)$

będziemy nazywali elementem odwrotnym liczby $k$ modulo $m$ i oznaczali jako $k^{-1}$.

Uwaga K3
Oznaczenie elementu odwrotnego ma naturalne uzasadnienie. Zauważmy, że jeżeli $b\mid a$ oraz $b$ ma element odwrotny modulo $m$, to prawdziwa jest kongruencja

$\frac{a}{b}\equiv a{b}^{-1}(\mathrm{mod}m)$

Istotnie

$\frac{a}{b}=\frac{a}{b}\cdot 1\equiv \frac{a}{b}\cdot b{b}^{-1}\equiv a{b}^{-1}(\mathrm{mod}m)$

W PARI/GP odwrotność liczby $a$ modulo $m$ znajdujemy, wpisując Mod(a, m)^(-1).

Twierdzenie K4
Niech $p$ będzie liczbą pierwszą nieparzystą, a liczby $a,b$ będą względnie pierwsze z $p$. Jeżeli liczby $a,b$ są różne modulo $p$, to ich elementy odwrotne $a^{-1},b^{-1}$ też są różne modulo $p$.

Dowód

Z założenia $a\not\equiv b(\mathrm{mod}p)$. Gdyby było

$a^{-1}\equiv b^{-1}(\mathrm{mod}p)$

to mielibyśmy

$a^{-1}ab\equiv b^{-1}ab(\mathrm{mod}p)$

Czyli

$b\equiv a(\mathrm{mod}p)$

Wbrew uczynionemu założeniu. Co kończy dowód.
□

Twierdzenie K5
Niech $p$ będzie liczbą pierwszą nieparzystą, zbiór $R=\{1,2,\dots ,p-1\}$, a zbiór $S$ będzie identyczny ze zbiorem $R$ modulo $p$. Jeżeli liczby $x_k\in S$ przebiegają cały zbiór $S$, to liczby $x_k^{-1}$ przebiegają zbiór $T$ identyczny ze zbiorem $R$ modulo $p$.

Dowód

Z założenia zbiory $R$ i $S$ są identyczne modulo $R$. Zatem każdej liczbie $k\in R$ odpowiada dokładnie jedna liczba $x_k\in S$ taka, że

$x_k\equiv k(\mathrm{mod}p)$

Ponieważ $gcd(k,p)=1$, to również $gcd(x_k,p)=1$. Zatem liczba $x_k$ ma element odwrotny $x_k^{-1}$ modulo $p$. Ponieważ wszystkie liczby $x_k$ są różne modulo $p$, to elementy odwrotne $x_k^{-1}$ też są wszystkie różne modulo $p$. Ponieważ liczb $x_k^{-1}$ jest dokładnie $p-1$, to tworzą one pewien zbiór $T$ identyczny ze zbiorem $R$ modulo $p$. Co kończy dowód.
□

Twierdzenie K6
Niech $p$ będzie liczbą pierwszą nieparzystą.

Jeżeli $a$ jest liczbą kwadratową (odpowiednio niekwadratową) modulo $p$, to element odwrotny liczby $a$ modulo $p$ istnieje i jest liczbą kwadratową (odpowiednio niekwadratową) modulo $p$.

Jeżeli $a,b$ są liczbami kwadratowymi (odpowiednio niekwadratowymi) modulo $p$, to istnieje taka liczba $r$, że $a\equiv b{r}^2(\mathrm{mod}p)$

Dowód

Z założenia $a$ jest liczbą kwadratową (niekwadratową) modulo $p$, zatem $gcd(a,p)=1$, czyli element odwrotny liczby $a$ modulo $p$ istnieje. Mamy

$1={\left(\frac{1}{p}\right)}_L={\left(\frac{a{a}^{-1}}{p}\right)}_L={\left(\frac{a}{p}\right)}_L\cdot {\left(\frac{a^{-1}}{p}\right)}_L$

Zatem musi być

${\left(\frac{a^{-1}}{p}\right)}_L={\left(\frac{a}{p}\right)}_L$

Co należało pokazać.

Niech $a,b$ będą liczbami kwadratowymi (niekwadratowymi). Iloczyn $a{b}^{-1}$ jest liczbą kwadratową, bo

${\left(\frac{a{b}^{-1}}{p}\right)}_L={\left(\frac{a}{p}\right)}_L\cdot {\left(\frac{b^{-1}}{p}\right)}_L={\left(\frac{a}{p}\right)}_L\cdot {\left(\frac{b}{p}\right)}_L={\left(\frac{\pm 1}{p}\right)}_L\cdot {\left(\frac{\pm 1}{p}\right)}_L={\left(\frac{\pm 1}{p}\right)}_L^2=1$

Zatem istnieje taka liczba $r$, że

$a{b}^{-1}\equiv r^2(\mathrm{mod}p)$

Czyli

$a\equiv b{r}^2(\mathrm{mod}p)$

Co należało pokazać.
□

Przykłady sum symboli Legendre'a

Twierdzenie K7
Niech $p$ będzie liczbą pierwszą nieparzystą, $a,d\in \mathbb{Z}$ i $p\nmid d$. Pokazać, że

$\sum _{k=1}^{p-1}{\left(\frac{k}{p}\right)}_L=\sum _{k=0}^{p-1}{\left(\frac{k}{p}\right)}_L=0$

$\sum _{k=1}^{p-1}{\left(\frac{k^2}{p}\right)}_L=\sum _{k=0}^{p-1}{\left(\frac{k^2}{p}\right)}_L=p-1$

$\sum _{k=0}^{p-1}{\left(\frac{a+kd}{p}\right)}_L=0$

Dowód

Punkt 1.

Wystarczy zauważyć, że wśród liczb $1,2,\dots ,p-1$ jest $\frac{p-1}{2}$ liczb kwadratowych modulo $p$ i $\frac{p-1}{2}$ liczb niekwadratowych modulo $p$. Zatem

$\sum _{k=1}^{p-1}{\left(\frac{k}{p}\right)}_L=\frac{p-1}{2}\cdot 1+\frac{p-1}{2}\cdot (-1)=0$

Punkt 2.

Wystarczy zauważyć, że

${\left(\frac{k^2}{p}\right)}_L={\left(\frac{k}{p}\right)}_L^2$

oraz że wśród liczb $1,2,\dots ,p-1$ jest $\frac{p-1}{2}$ liczb kwadratowych modulo $p$ i $\frac{p-1}{2}$ liczb niekwadratowych modulo $p$. Zatem

$\sum _{k=1}^{p-1}{\left(\frac{k}{p}\right)}_L=\frac{p-1}{2}\cdot 1^2+\frac{p-1}{2}\cdot (-1{)}^2=p-1$

Punkt 3.

Z założenia liczby $p$ i $d$ są względnie pierwsze. Z twierdzenia C55 wiemy, że reszty $r_1,r_2,\dots ,r_p$ z dzielenia $p$ kolejnych liczb postaci

$x_k=a+kd$

przez liczbę $p$ są wszystkie różne i tworzą zbiór $S=\{0,1,\dots ,p-1\}$. Czyli wśród reszt $r_1,r_2,\dots ,r_p$ jest $\frac{p-1}{2}$ liczb kwadratowych modulo $p$, tyle samo liczb niekwadratowych modulo $p$, a jedna z tych reszt jest podzielna przez $p$. Z własności symbolu Legendre'a wiemy, że licznik wpływa na wartość symbolu jedynie modulo mianownik (zobacz J29 p. 2). Zatem możemy napisać

$\sum _{k=0}^{p-1}{\left(\frac{a+kd}{p}\right)}_L=\sum _{j=0}^{p-1}{\left(\frac{r_j}{p}\right)}_L=\frac{p-1}{2}\cdot 1+\frac{p-1}{2}\cdot (-1)+0=0$

Co należało pokazać.
□

Twierdzenie K8* (George Pólya, Iwan Winogradow, 1918)
Jeżeli $p$ jest liczbą pierwszą nieparzystą i $m,n\in {\mathbb{N}}_0$, to prawdziwe jest oszacowanie

$\left|\sum _{t=m}^{m+n}{\left(\frac{t}{p}\right)}_L\right|<\sqrt{p}\log p$

Twierdzenie K9
Jeżeli $p$ jest liczbą pierwszą nieparzystą i $a,b\in \mathbb{Z}$, to

$\sum _{k=0}^{p-1}{\left(\frac{k+a}{p}\right)}_L{\left(\frac{k+b}{p}\right)}_L=\{\begin{array}{ll}-1& \text{gdy }p\nmid (a-b)\\ p-1& \text{gdy }p\mid (a-b)\end{array}$

Dowód

1. Przypadek, gdy $\mathit{p}\mathbf{\mid }\mathbf{(}\mathit{a}\mathbf{-}\mathit{b}\mathbf{)}$

Z założenia $b\equiv a(\mathrm{mod}p)$

$\sum _{k=0}^{p-1}{\left(\frac{k+a}{p}\right)}_L{\left(\frac{k+b}{p}\right)}_L=\sum _{k=0}^{p-1}{\left(\frac{k+a}{p}\right)}_L{\left(\frac{k+a}{p}\right)}_L=\sum _{k=0}^{p-1}{\left(\frac{k+a}{p}\right)}_L^2$

Z twierdzenia C55 wiemy, że reszty $r_1,r_2,\dots ,r_p$ z dzielenia $p$ kolejnych liczb postaci

$x_k=a+k$

przez liczbę $p$ są wszystkie różne i tworzą zbiór $S=\{0,1,\dots ,p-1\}$. Czyli wśród reszt $r_1,r_2,\dots ,r_p$ jest $\frac{p-1}{2}$ liczb kwadratowych modulo $p$, tyle samo liczb niekwadratowych modulo $p$, a jedna z tych reszt jest podzielna przez $p$. Z własności symbolu Legendre'a wiemy, że licznik wpływa na wartość symbolu jedynie modulo mianownik (zobacz J29 p. 2). Zatem możemy napisać

$\sum _{k=0}^{p-1}{\left(\frac{k+a}{p}\right)}_L^2=\sum _{k=0}^{p-1}{\left(\frac{r_k}{p}\right)}_L^2=p-1$

Co należało pokazać.

2. Przypadek, gdy $\mathit{p}\mathbf{\nmid }\mathbf{(}\mathit{a}\mathbf{-}\mathit{b}\mathbf{)}$

Kładąc $j=k+a$ i sumując od $a$ do $p-1+a$, otrzymujemy

$\sum _{k=0}^{p-1}{\left(\frac{k+a}{p}\right)}_L{\left(\frac{k+b}{p}\right)}_L=\sum _{j=a}^{p-1+a}{\left(\frac{j}{p}\right)}_L{\left(\frac{j+b-a}{p}\right)}_L$

Wśród $p$ kolejnych liczb $a,a+1,\dots ,p-1+a$ istnieje dokładnie jedna liczba podzielna przez $p$. Możemy ją pominąć, bo nie wnosi ona wkładu do wyliczanej sumy.

$\sum _{k=0}^{p-1}{\left(\frac{k+a}{p}\right)}_L{\left(\frac{k+b}{p}\right)}_L=\underset{p\nmid j}{\sum _{j=a}^{p-1+a}}{\left(\frac{j}{p}\right)}_L{\left(\frac{j+b-a}{p}\right)}_L$

$=\underset{p\nmid j}{\sum _{j=a}^{p-1+a}}{\left(\frac{j}{p}\right)}_L{\left(\frac{j+(b-a)j{j}^{-1}}{p}\right)}_L$

$=\underset{p\nmid j}{\sum _{j=a}^{p-1+a}}{\left(\frac{j^2}{p}\right)}_L{\left(\frac{1+(b-a)j^{-1}}{p}\right)}_L$

$=\underset{p\nmid j}{\sum _{j=a}^{p-1+a}}{\left(\frac{1+(b-a)j^{-1}}{p}\right)}_L$

Z własności symbolu Legendre'a wiemy, że licznik wpływa na wartość symbolu jedynie modulo mianownik. Wiemy też, że gdy liczby $j$ przebiegają zbiór identyczny (modulo $p$) ze zbiorem $R=\{1,2,\dots ,p-1\}$, to liczby $j^{-1}$ przebiegają pewien zbiór $S$ identyczny (modulo $p$) ze zbiorem $R$ (zobacz K5). Zatem od sumowania po $j$ możemy przejść do sumowania po $r\in R$.

$\sum _{k=0}^{p-1}{\left(\frac{k+a}{p}\right)}_L{\left(\frac{k+b}{p}\right)}_L=\sum _{r=1}^{p-1}{\left(\frac{1+(b-a)r}{p}\right)}_L$

$=-{\left(\frac{1}{p}\right)}_L+\sum _{r=0}^{p-1}{\left(\frac{1+(b-a)r}{p}\right)}_L$

$=-1$

Ostatnia z wypisanych sum jest równa zero, co wynika z trzeciego wzoru twierdzenia K7 i faktu, że $p\nmid (b-a)$. Co należało pokazać.
□

Twierdzenie K10
Jeżeli $p$ jest liczbą pierwszą nieparzystą i $n\in \mathbb{Z}$, to

$\sum _{k=0}^{p-1}{\left(\frac{k^2+n}{p}\right)}_L=\{\begin{array}{ll}-1& \text{gdy }p\nmid n\\ p-1& \text{gdy }p\mid n\end{array}$

Dowód

Przypadek, gdy $\mathit{p}\mathbf{\mid }\mathit{n}$

Z drugiego wzoru twierdzenia K7 otrzymujemy

$\sum _{k=0}^{p-1}{\left(\frac{k^2+n}{p}\right)}_L=\sum _{k=0}^{p-1}{\left(\frac{k^2}{p}\right)}_L=p-1$

Przypadek, gdy $\mathit{p}\mathbf{\nmid }\mathit{n}$

Jeżeli liczby $a,b$ są obie liczbami kwadratowymi lub obie liczbami niekwadratowymi modulo $p$, to istnieje taka liczba $r$, że

$a\equiv b{r}^2(\mathrm{mod}p)$

(zobacz K6). Zatem

$S(a)=\sum _{k=0}^{p-1}{\left(\frac{k^2+a}{p}\right)}_L$

$=\sum _{k=0}^{p-1}{\left(\frac{k^2+b{r}^2}{p}\right)}_L$

$=\sum _{k=0}^{p-1}{\left(\frac{r^2[(k{r}^{-1}{)}^2+b]}{p}\right)}_L$

$={\left(\frac{r^2}{p}\right)}_L\sum _{k=0}^{p-1}{\left(\frac{(k{r}^{-1}{)}^2+b}{p}\right)}_L$

$=\sum _{k=0}^{p-1}{\left(\frac{(k{r}^{-1}{)}^2+b}{p}\right)}_L$

Z twierdzenia C55 wiemy, że gdy $k$ przebiega zbiór $T=\{0,1,\dots ,p-1\}$, to $k{r}^{-1}$ przebiega zbiór $T^{\prime }$ identyczny ze zbiorem $T$ modulo $p$. Zatem

$S(a)=\sum _{x=0}^{p-1}{\left(\frac{x^2+b}{p}\right)}_L=S(b)$

Wynika stąd, że dla wszystkich liczb kwadratowych (odpowiednio niekwadratowych) modulo $p$ wyrażenie $S(n)$ ma taką samą wartość i jeśli wybierzemy liczby $a,b$ tak, aby jedna była liczbą kwadratową, a druga liczbą niekwadratową modulo $p$, to możemy napisać

$\sum _{n=1}^{p-1}S(n)=\frac{p-1}{2}(S(a)+S(b))$

Z drugiej strony

$\sum _{n=1}^{p-1}S(n)=\sum _{n=1}^{p-1}\sum _{k=0}^{p-1}{\left(\frac{k^2+n}{p}\right)}_L$

$=\sum _{k=0}^{p-1}\sum _{n=1}^{p-1}{\left(\frac{k^2+n}{p}\right)}_L$

$=\sum _{k=0}^{p-1}[-{\left(\frac{k^2}{p}\right)}_L+\sum _{n=0}^{p-1}{\left(\frac{k^2+n}{p}\right)}_L]$

$=-\sum _{k=0}^{p-1}{\left(\frac{k}{p}\right)}_L^2$

$=-(p-1)$

bo z twierdzenia K7 wiemy, że

$\sum _{n=0}^{p-1}{\left(\frac{n+k^2}{p}\right)}_L=0$

Łącząc uzyskane rezultaty, dostajemy

$-(p-1)=\frac{p-1}{2}(S(a)+S(b))$

Zatem

$S(a)+S(b)=-2$

Z twierdzenia K9 mamy

$S(-1)=\sum _{k=0}^{p-1}{\left(\frac{k^2-1}{p}\right)}_L=\sum _{k=0}^{p-1}{\left(\frac{k-1}{p}\right)}_L{\left(\frac{k+1}{p}\right)}_L=-1$

bo $p\nmid 2$. Dla ustalenia uwagi przyjmijmy, że $a$ jest liczbą kwadratową, a $b$ jest liczbą niekwadratową modulo $p$. Jeżeli $-1$ jest liczbą kwadratową modulo $p$, to $S(a)=-1$ i natychmiast otrzymujemy, że $S(b)=-1$. Jeżeli $-1$ jest liczbą niekwadratową modulo $p$, to $S(b)=-1$ i natychmiast otrzymujemy, że $S(a)=-1$. Zatem bez względu na to, czy $n$ jest liczbą kwadratową, czy liczbą niekwadratową modulo $p$, musi być $S(n)=-1$. Co należało pokazać.
□

Zadanie K11
Pokazać, że jeżeli $p$ jest liczbą pierwszą nieparzystą i $r,s\in \mathbb{Z}$, to

$\sum _{k=0}^{p-1}{\left(\frac{k^2+rk+s}{p}\right)}_L=\{\begin{array}{ll}-1& \text{gdy }p\nmid (r^2-4s)\\ p-1& \text{gdy }p\mid (r^2-4s)\end{array}$

Rozwiązanie

$\sum _{k=0}^{p-1}{\left(\frac{k^2+rk+s}{p}\right)}_L=\sum _{k=0}^{p-1}{\left(\frac{2^2}{p}\right)}_L{\left(\frac{k^2+rk+s}{p}\right)}_L$

$=\sum _{k=0}^{p-1}{\left(\frac{4k^2+4rk+4s}{p}\right)}_L$

$=\sum _{k=0}^{p-1}{\left(\frac{(2k+r{)}^2+4s-r^2}{p}\right)}_L$

Z twierdzenia C55 wiemy, że gdy $k$ przebiega zbiór $T=\{0,1,\dots ,p-1\}$, to $2k+r$ przebiega zbiór $T^{\prime }$ identyczny ze zbiorem $T$ modulo $p$. Zatem

$\sum _{k=0}^{p-1}{\left(\frac{k^2+rk+s}{p}\right)}_L=\sum _{x=0}^{p-1}{\left(\frac{x^2+4s-r^2}{p}\right)}_L$

Z twierdzenia K10 wynika natychmiast teza dowodzonego twierdzenia.
□

Twierdzenie K12
Jeżeli $p$ jest liczbą pierwszą nieparzystą i $n\in \mathbb{Z}$, to dla sumy

$S(n)=\sum _{k=0}^{p-1}{\left(\frac{k(k^2+n)}{p}\right)}_L$

prawdziwe są następujące wzory

(a) $S(n)=0\text{gdy }p=4k+3$

(b) $|S(n)|<2\sqrt{p}\text{gdy }p=4k+1$

Dowód

Punkt (a)

Zauważmy, że zbiory $R=\{0,1,2,\dots ,p-1\}$ oraz $T=\{-p+1,-p+2,\dots ,-p+(p-1),0\}$ są identyczne modulo $p$. Z własności symbolu Legendre'a wiemy, że licznik wpływa na wartość symbolu jedynie modulo mianownik (zobacz J29 p.2). Zatem możemy sumowanie po $k\in R$ zastąpić sumowaniem po $j\in T.$ Otrzymujemy

$S(n)=\sum _{j=-p+1}^0{\left(\frac{j(j^2+n)}{p}\right)}_L$

Kładąc $j=-r$ i sumując po $r$ od $0$ do $p-1$, dostajemy

$S(n)=\sum _{r=0}^{p-1}{\left(\frac{-r}{p}\right)}_L{\left(\frac{(-r{)}^2+n}{p}\right)}_L=\sum _{r=0}^{p-1}{\left(\frac{-1}{p}\right)}_L{\left(\frac{r}{p}\right)}_L{\left(\frac{r^2+n}{p}\right)}_L={\left(\frac{-1}{p}\right)}_{L}S(n)$

Jeżeli $p=4k+3$, to $S(n)=-S(n)$, czyli $S(n)=0$.

Punkt (b)

Pomysł dowodu zaczerpnęliśmy z materiałów szkoleniowych Międzynarodowej Olimpiady Matematycznej.

Jeżeli liczby $a,b$ są obie liczbami kwadratowymi lub obie liczbami niekwadratowymi modulo $p$, to istnieje taka liczba $r$, że

$a\equiv b{r}^2(\mathrm{mod}p)$

(zobacz K6). Zatem

$S(a)=S(b{r}^2)=\sum _{k=0}^{p-1}{\left(\frac{k(k^2+b{r}^2)}{p}\right)}_L$

$=\sum _{k=0}^{p-1}{\left(\frac{r^3(k{r}^{-1})[(k{r}^{-1}{)}^2+b]}{p}\right)}_L$

$={\left(\frac{r^3}{p}\right)}_L\sum _{k=0}^{p-1}{\left(\frac{(k{r}^{-1})[(k{r}^{-1}{)}^2+b]}{p}\right)}_L$

$={\left(\frac{r}{p}\right)}_L\sum _{k=0}^{p-1}{\left(\frac{(k{r}^{-1})[(k{r}^{-1}{)}^2+b]}{p}\right)}_L$

Z twierdzenia C55 wiemy, że gdy $k$ przebiega zbiór $T=\{0,1,\dots ,p-1\}$, to $k{r}^{-1}$ przebiega zbiór $T^{\prime }$ identyczny ze zbiorem $T$ modulo $p$. Zatem

$S(a)={\left(\frac{r}{p}\right)}_L\sum _{x=0}^{p-1}{\left(\frac{x(x^2+b)}{p}\right)}_L={\left(\frac{r}{p}\right)}_{L}S(b)$

Czyli $S(a{)}^2=S(b{)}^2$. Wynika stąd, że dla wszystkich liczb kwadratowych (odpowiednio niekwadratowych) modulo $p$ wyrażenie $S(n{)}^2$ ma taką samą wartość i jeśli wybierzemy liczby $a,b$ tak, aby jedna była liczbą kwadratową, a druga liczbą niekwadratową modulo $p$, to prawdziwa jest równość

$\sum _{n=1}^{p-1}S(n{)}^2=\frac{p-1}{2}(S(a{)}^2+S(b{)}^2)$

Jak łatwo zauważyć $S(0)=0$, zatem możemy napisać

$\sum _{n=0}^{p-1}S(n{)}^2=\frac{p-1}{2}(S(a{)}^2+S(b{)}^2)$

Z drugiej strony

$S(n{)}^2=\sum _{k=1}^{p-1}{\left(\frac{k(k^2+n)}{p}\right)}_L\sum _{j=1}^{p-1}{\left(\frac{j(j^2+n)}{p}\right)}_L$

$=\sum _{k=1}^{p-1}\sum _{j=1}^{p-1}{\left(\frac{k(k^2+n)}{p}\right)}_L{\left(\frac{j(j^2+n)}{p}\right)}_L$

$=\sum _{k=1}^{p-1}\sum _{j=1}^{p-1}{\left(\frac{kj(k^2+n)(j^2+n)}{p}\right)}_L$

Zatem

$\sum _{n=0}^{p-1}S(n{)}^2=\sum _{n=0}^{p-1}\sum _{k=1}^{p-1}\sum _{j=1}^{p-1}{\left(\frac{kj(k^2+n)(j^2+n)}{p}\right)}_L$

$=\sum _{k=1}^{p-1}\sum _{j=1}^{p-1}{\left(\frac{kj}{p}\right)}_L\sum _{n=0}^{p-1}{\left(\frac{(n+k^2)(n+j^2)}{p}\right)}_L$

Z twierdzenia K9 wiemy, że

$\sum _{n=0}^{p-1}{\left(\frac{(n+k^2)(n+j^2)}{p}\right)}_L=\{\begin{array}{ll}-1& \text{gdy }p\nmid (k^2-j^2)\\ p-1& \text{gdy }p\mid (k^2-j^2)\end{array}$

Zbadajmy, kiedy $p\mid (k^2-j^2)$, czyli kiedy $p\mid [(k-j)(k+j)]$. Mamy

• $0⩽|k-j|⩽p-2$

• $2⩽k+j⩽2p-2$

Zatem $p\mid [(k-j)(k+j)]$ gdy

• $j=k$

• $j=p-k$

Pozwala to zapisać rozpatrywaną sumę w postaci

$\sum _{n=0}^{p-1}S(n{)}^2=\sum _{k=1}^{p-1}\sum _{j=1}^{p-1}{\left(\frac{kj}{p}\right)}_L\cdot \left\{\begin{array}{rl}-1& \text{gdy }j\ne k\text{ i }j\ne p-k\\ p-1& \text{gdy }j=k\text{ lub }j=p-k\end{array}\right\}$

$=(p-1)\underset{j=k\text{ lub }j=p-k}{\sum _{k=1}^{p-1}\sum _{j=1}^{p-1}}{\left(\frac{kj}{p}\right)}_L-\underset{j\ne k\text{ i }j\ne p-k}{\sum _{k=1}^{p-1}\sum _{j=1}^{p-1}}{\left(\frac{kj}{p}\right)}_L$

$=(p-1)[\sum _{k=1}^{p-1}{\left(\frac{k^2}{p}\right)}_L+\sum _{k=1}^{p-1}{\left(\frac{k(p-k)}{p}\right)}_L]-\sum _{k=1}^{p-1}\sum _{j=1}^{p-1}{\left(\frac{kj}{p}\right)}_L+\underset{j=k\text{ lub }j=p-k}{\sum _{k=1}^{p-1}\sum _{j=1}^{p-1}}{\left(\frac{kj}{p}\right)}_L$

$=(p-1)[(p-1)+\sum _{k=1}^{p-1}{\left(\frac{-k^2}{p}\right)}_L]-\sum _{k=1}^{p-1}{\left(\frac{k}{p}\right)}_L\sum _{j=1}^{p-1}{\left(\frac{j}{p}\right)}_L+\sum _{k=1}^{p-1}{\left(\frac{k^2}{p}\right)}_L+\sum _{k=1}^{p-1}{\left(\frac{k(p-k)}{p}\right)}_L$

$=(p-1)[(p-1)+{\left(\frac{-1}{p}\right)}_L\sum _{k=1}^{p-1}{\left(\frac{k^2}{p}\right)}_L]+(p-1)+\sum _{k=1}^{p-1}{\left(\frac{-k^2}{p}\right)}_L$

$=(p-1)\cdot 2(p-1)+(p-1)+(p-1)$

$=2p(p-1)$

Zauważmy, że ${\left(\frac{-1}{p}\right)}_L=1$, bo $p=4k+1$.

Ponieważ wcześniej pokazaliśmy, że

$\sum _{n=0}^{p-1}S(n{)}^2=\frac{p-1}{2}(S(a{)}^2+S(b{)}^2)$

to otrzymujemy

$\frac{p-1}{2}(S(a{)}^2+S(b{)}^2)=2p(p-1)$

Czyli

$S(a{)}^2+S(b{)}^2=4p$

Wynika stąd, że bez względu na to, czy $n$ jest liczbą kwadratową, czy liczbą niekwadratową modulo $p$, prawdziwe jest oszacowanie

$|S(n)|⩽2\sqrt{p}$

Równość $S(n{)}^2=4p$ nie jest możliwa, bo dzielnik pierwszy $p$ występuje po prawej stronie w potędze nieparzystej. Zatem mamy nieco silniejsze oszacowanie

$|S(n)|<2\sqrt{p}$

Co kończy dowód.
□

Twierdzenie K13
Jeżeli $p$ jest liczbą pierwszą nieparzystą i $a,b\in \mathbb{Z}$, to dla sumy

$S(a,b)=\sum _{x=0}^{p-1}{\left(\frac{x^3+ax+b}{p}\right)}_L$

prawdziwe są następujące wzory

(a) $S(a,b)=-{\left(\frac{6b}{p}\right)}_L\text{gdy }p\mid (4a^3+27b^2)$

(b) $|S(a,b)|<2\sqrt{p}\text{gdy }p\nmid (4a^3+27b^2)$

Dowód

Niech $p⩾5$. W ogólnym przypadku interesująca nas suma ma postać

$\sum _{t=0}^{p-1}{\left(\frac{a{t}^3+b{t}^2+ct+d}{p}\right)}_L$

gdzie $p\nmid a$. Mnożąc licznik przez $a^2$ nie zmieniamy wartości sumy

$\sum _{t=0}^{p-1}{\left(\frac{a^3{t}^3+a^{2}b{t}^2+a^{2}ct+a^{2}d}{p}\right)}_L$

Podstawiając $x\equiv at+r(\mathrm{mod}p)$, dostajemy

$\sum _{x=0}^{p-1}{\left(\frac{x^3+x^2(b-3r)+x[ac-r(2b-3r)]+[a^{2}d-acr+r^2(b-r)]}{p}\right)}_L$

bo, gdy $t$ przebiega zbiór $\{0,1,\dots ,p-1\}$, to (modulo $p$) liczby $at+r$ przebiegają taki sam zbiór (zobacz C55). Ponieważ $p⩾5$, to liczbę $r$ możemy wybrać tak, aby było

$3r\equiv b(\mathrm{mod}p)$

Ostatecznie otrzymujemy

$\sum _{x=0}^{p-1}{\left(\frac{x^3+x(ac-3r^2)+(a^{2}d-acr+2r^3)}{p}\right)}_L$

Widzimy, że bez zmniejszania ogólności, możemy ograniczyć się do badania sumy postaci

$S(a,b)=\sum _{x=0}^{p-1}{\left(\frac{x^3+ax+b}{p}\right)}_L$

Liczbę $-(4a^3+27b^2)$ nazywamy wyróżnikiem wielomianu $x^3+ax+b$.

Pokażemy, że w przypadku, gdy $4a^3+27b^2\equiv 0(\mathrm{mod}p)$ i $p⩾3$ prawdziwy jest wzór

$S(a,b)=\sum _{x=0}^{p-1}{\left(\frac{x^3+ax+b}{p}\right)}_L=-{\left(\frac{6b}{p}\right)}_L$

W przypadku, gdy $p=3$ z warunku $4a^3+27b^2\equiv 0(\mathrm{mod}3)$ wynika, że $3\mid a$. Zakładając, że reszta z dzielenia liczby $b$ przez $3$ wynosi $r$, otrzymujemy

$S(a,b)=\sum _{x=0}^2{\left(\frac{x^3+b}{3}\right)}_L={\left(\frac{b}{3}\right)}_L+{\left(\frac{1+b}{3}\right)}_L+{\left(\frac{8+b}{3}\right)}_L={\left(\frac{r}{3}\right)}_L+{\left(\frac{r+1}{3}\right)}_L+{\left(\frac{r+2}{3}\right)}_L={\left(\frac{0}{3}\right)}_L+{\left(\frac{1}{3}\right)}_L+{\left(\frac{2}{3}\right)}_L=0$

Jeżeli $p⩾5$ i $p\mid a$, to $p\mid b$ i łatwo znajdujemy, że

$S(a,b)=\sum _{x=0}^{p-1}{\left(\frac{x^3+ax+b}{p}\right)}_L=\sum _{x=0}^{p-1}{\left(\frac{x^3}{p}\right)}_L=0$

Jeżeli $p⩾5$ i $p\nmid a$, to

$x^3+ax+b\equiv (x-x_1)(x-x_2{)}^2(\mathrm{mod}p)$

gdzie

$x_1\equiv 3b{a}^{-1}(\mathrm{mod}p)$

$x_2\equiv -3b{2}^{-1}{a}^{-1}(\mathrm{mod}p)$

Co Czytelnik może łatwo sprawdzić, pamiętając o tym, że $27b^2\cdot 2^{-2}{a}^{-3}\equiv -1(\mathrm{mod}p)$. Mamy

$S(a,b)=\sum _{x=0}^{p-1}{\left(\frac{x-x_2}{p}\right)}_L^2{\left(\frac{x-x_1}{p}\right)}_L$

Niech $t=x-x_2$. Jeżeli $x$ przebiega zbiór $\{0,1,\dots ,p-1\}$, to (modulo $p$) $t$ przebiega taki sam zbiór (zobacz C55). Zatem

$S(a,b)=\sum _{t=0}^{p-1}{\left(\frac{t}{p}\right)}_L^2{\left(\frac{t+x_2-x_1}{p}\right)}_L=\sum _{t=1}^{p-1}{\left(\frac{t+x_2-x_1}{p}\right)}_L=-{\left(\frac{x_2-x_1}{p}\right)}_L+\sum _{t=0}^{p-1}{\left(\frac{t+x_2-x_1}{p}\right)}_L=-{\left(\frac{x_2-x_1}{p}\right)}_L$

Uwzględniając, że

$x_2-x_1\equiv -3b{2}^{-1}{a}^{-1}-3b{a}^{-1}\equiv -3b{2}^{-1}{a}^{-1}-6b{2}^{-1}{a}^{-1}\equiv -9b{2}^{-1}{a}^{-1}(\mathrm{mod}p)$

otrzymujemy

$S(a,b)=-{\left(\frac{x_2-x_1}{p}\right)}_L=-{\left(\frac{-9b{2}^{-1}{a}^{-1}}{p}\right)}_L=-{\left(\frac{-2ab}{p}\right)}_L=-{\left(\frac{-8a^{3}b}{p}\right)}_L=-{\left(\frac{-2b\cdot (-27b^2)}{p}\right)}_L=-{\left(\frac{6b}{p}\right)}_L$

W przypadku, gdy $4a^3+27b^2\not\equiv 0(\mathrm{mod}p)$, pokażemy, że wartość sumy

$S(a,b)=\sum _{x=0}^{p-1}{\left(\frac{x^3+ax+b}{p}\right)}_L$

jest ściśle związana z ilością rozwiązań kongruencji

$y^2\equiv x^3+ax+b(\mathrm{mod}p)$

Niech $N_p$ oznacza ilość rozwiązań powyższej kongruencji i niech $N_{+},N_0,N_{-}$ oznaczają ilości liczb $k\in \{0,1,\dots ,p-1\}$, dla których symbol Legendre'a ${\left(\frac{x^3+ax+b}{p}\right)}_L$ jest równy odpowiednio $+1,0,-1$. Oczywiście

$N_{+}+N_0+N_{-}=p$

$S(a,b)=N_{+}-N_{-}$

Zauważmy, że jeżeli dla pewnego $x$ jest $p\mid (x^3+ax+b)$, to ${\left(\frac{x^3+ax+b}{p}\right)}_L=0$ i mamy dokładnie jedno rozwiązanie rozważanej kongruencji

$0^2\equiv x^3+ax+b(\mathrm{mod}p)$

Jeżeli dla pewnego $x$ jest ${\left(\frac{x^3+ax+b}{p}\right)}_L=+1$, to $p\nmid (x^3+ax+b)$, a liczba $x^3+ax+b$ jest liczbą kwadratową modulo $p$, czyli istnieje taka liczba $y\in \mathbb{Z}$, że

$y^2\equiv x^3+ax+b(\mathrm{mod}p)$

i mamy dwa rozwiązania rozpatrywanej kongruencji: jedno stanowi para $(x,y)$, a drugie para $(x,-y)$. Zatem

$N_p=2N_{+}+N_0$

Łatwo zauważamy, że

$N_p-p=(2N_{+}+N_0)-(N_{+}+N_0+N_{-})=N_{+}-N_{-}=S(a,b)$

W 1936 roku Helmut Hasse udowodnił, że

$|N_p-p|<2\sqrt{p}$

Elementarny dowód tego twierdzenia podał Jurij Manin.

Wynika stąd, że w przypadku, gdy $4a^3+27b^2\not\equiv 0(\mathrm{mod}p)$ prawdziwe jest oszacowanie

$|S(a,b)|=\left|\sum _{x=0}^{p-1}{\left(\frac{x^3+ax+b}{p}\right)}_L\right|<2\sqrt{p}$

Co należało pokazać.
□

Zadanie K14
Pokazać, że jeżeli $p⩾7$ jest liczbą pierwszą, to wśród liczb $1,2,\dots ,p-1$ istnieją:

• dwie kolejne liczby będące liczbami kwadratowymi modulo $p$
• dwie kolejne liczby będące liczbami niekwadratowymi modulo $p$

Rozwiązanie

Dla $p=7$ łatwo sprawdzamy, że twierdzenie jest prawdziwe.

Punkt 1.

Zauważmy, że przynajmniej jedna z liczb $2,5,10$ jest liczbą kwadratową. Zakładając, że tak nie jest, otrzymujemy natychmiast sprzeczność

$-1={\left(\frac{10}{p}\right)}_L={\left(\frac{2}{p}\right)}_L\cdot {\left(\frac{5}{p}\right)}_L=(-1)\cdot (-1)=1$

W zależności od tego, która z liczb $2,5,10$ jest liczbą kwadratową, mamy następujące pary kolejnych liczb kwadratowych

$2$	$1,2\text{ oraz }8,9$
$5$	$4,5$
$10$	$9,10$

Punkt 2.

Rozważmy wszystkie możliwe wartości ${\left(\frac{k}{p}\right)}_L$ dla $k=1,2,3,4$ i $p⩾11$. Zauważmy, że ${\left(\frac{6}{p}\right)}_L={\left(\frac{2}{p}\right)}_L\cdot {\left(\frac{3}{p}\right)}_L$.

$\mathit{k}$	$\mathbf{1}$	$\mathbf{2}$	$\mathbf{3}$	$\mathbf{4}$	$\mathbf{5}$	$\mathbf{6}$	$\mathbf{(}\mathbf{\dots }\mathbf{)}$	$\mathit{p}\mathbf{-}\mathbf{1}$
$\mathit{A}\mathbf{.}$	$1$	$1$	$1$	$1$	$$	$1$	$$	$$
$\mathit{B}\mathbf{.}$	$1$	$1$	$-1$	$1$	$$	$-1$	$$	$$
$\mathit{C}\mathbf{.}$	$1$	$-1$	$1$	$1$	$$	$-1$	$$	$$
$\mathit{D}\mathbf{.}$	$1$	$-1$	$-1$	$1$	$$	$1$	$$	$$

A. W tym przypadku liczby $2,3$ są liczbami kwadratowymi modulo $p$. Gdyby w pozostałych komórkach miało nie być ani jednej pary kolejnych liczb niekwadratowych modulo $p$, to musielibyśmy $\frac{p-1}{2}$ liczb niekwadratowych umieścić wśród pozostałych $p-5$ komórek tak, aby między nimi zawsze była liczba kwadratowa modulo $p$. Wartość ${\left(\frac{6}{p}\right)}_L$ wymusza, aby liczby niekwadratowe modulo $p$ umieszczać w komórkach „nieparzystych”. Po wypełnieniu tych komórek pozostaną nam dwie liczby, które będziemy zmuszeni umieścić w komórkach „parzystych”. Co oznacza, że muszą pojawić się dwie pary kolejnych liczb niekwadratowych modulo $p$.

B. i C. W tym przypadku dokładnie jedna z liczb $2,3$ jest liczbą kwadratową modulo $p$. Gdyby w pozostałych komórkach miało nie być ani jednej pary kolejnych liczb niekwadratowych modulo $p$, to musielibyśmy $\frac{p-3}{2}$ liczb niekwadratowych umieścić wśród pozostałych $p-5$ komórek tak, aby między nimi zawsze była liczba kwadratowa modulo $p$. Wartość ${\left(\frac{6}{p}\right)}_L$ wymusza, aby liczby niekwadratowe modulo $p$ umieszczać w komórkach „parzystych”. Po wypełnieniu tych komórek pozostanie nam jedna liczba, którą będziemy zmuszeni umieścić w komórce „nieparzystej”. Co oznacza, że musi pojawić się jedna para kolejnych liczb niekwadratowych modulo $p$.

D. W tym przypadku nie musimy niczego dowodzić, bo liczby $2,3$ są kolejnymi liczbami niekwadratowymi modulo $p$.
□

Uwaga K15
Wzmocnimy wynik uzyskany w poprzednim zadaniu. Zauważmy, jak użycie symbolu Legendre'a pozwala sformalizować problem.

Twierdzenie K16
Jeżeli $p$ jest liczbą pierwszą nieparzystą, to

• istnieje $\lfloor \frac{p-3}{4}\rfloor$ różnych par kolejnych liczb kwadratowych modulo $p$
• istnieje $\lfloor \frac{p-1}{4}\rfloor$ różnych par kolejnych liczb niekwadratowych modulo $p$

Dowód

Punkt 1.

Chcemy znaleźć ilość takich liczb $k\in \{1,2,\dots ,p-2\}$, dla których

${\left(\frac{k}{p}\right)}_L={\left(\frac{k+1}{p}\right)}_L=1$

Ilość liczb $k$ spełniających powyższy warunek łatwo zapisać korzystając z symbolu Legendre'a

$N=\frac{1}{4}\sum _{k=1}^{p-2}[1+{\left(\frac{k}{p}\right)}_L][1+{\left(\frac{k+1}{p}\right)}_L]$

Tylko w przypadku, gdy obie liczby $k$ i $k+1$ są liczbami kwadratowymi modulo $p$, iloczyn wyrażeń w nawiasach kwadratowych jest różny od zera i równy $4$ (stąd czynnik $\frac{1}{4}$ przed sumą).

$4N=\sum _{k=1}^{p-2}[1+{\left(\frac{k}{p}\right)}_L+{\left(\frac{k+1}{p}\right)}_L+{\left(\frac{k}{p}\right)}_L{\left(\frac{k+1}{p}\right)}_L]$

$=p-2+\sum _{k=1}^{p-2}{\left(\frac{k}{p}\right)}_L+\sum _{k=1}^{p-2}{\left(\frac{k+1}{p}\right)}_L+\sum _{k=1}^{p-2}{\left(\frac{k}{p}\right)}_L{\left(\frac{k+1}{p}\right)}_L$

Po kolei wyliczamy sumy po prawej stronie

$\sum _{k=1}^{p-2}{\left(\frac{k}{p}\right)}_L=-{\left(\frac{p-1}{p}\right)}_L+\sum _{k=1}^{p-1}{\left(\frac{k}{p}\right)}_L=-{\left(\frac{-1}{p}\right)}_L$

$\sum _{k=1}^{p-2}{\left(\frac{k+1}{p}\right)}_L=-{\left(\frac{1}{p}\right)}_L+\sum _{k=0}^{p-1}{\left(\frac{k+1}{p}\right)}_L=-1$

$\sum _{k=1}^{p-2}{\left(\frac{k}{p}\right)}_L{\left(\frac{k+1}{p}\right)}_L=\sum _{k=0}^{p-1}{\left(\frac{k}{p}\right)}_L{\left(\frac{k+1}{p}\right)}_L=-1$

(zobacz K7 i K9). Zatem

$N=\frac{1}{4}[p-4-{\left(\frac{-1}{p}\right)}_L]$

Czyli

$N=\{\begin{array}{ll}\frac{p-5}{4}& \text{ gdy }p=4k+1\\ \frac{p-3}{4}& \text{ gdy }p=4k+3\end{array}$

Powyższy wynik można zapisać w postaci

$N=\lfloor \frac{p-3}{4}\rfloor$

Punkt 2.

Chcemy znaleźć ilość takich liczb $k\in \{1,2,\dots ,p-2\}$, dla których

${\left(\frac{k}{p}\right)}_L={\left(\frac{k+1}{p}\right)}_L=-1$

Ilość liczb $k$ spełniających powyższy warunek łatwo zapisać korzystając z symbolu Legendre'a

$N=\frac{1}{4}\sum _{k=1}^{p-2}[-1+{\left(\frac{k}{p}\right)}_L][-1+{\left(\frac{k+1}{p}\right)}_L]$

Tylko w przypadku, gdy obie liczby $k$ i $k+1$ są liczbami niekwadratowymi modulo $p$, iloczyn wyrażeń w nawiasach kwadratowych jest różny od zera i równy $4$ (stąd czynnik $\frac{1}{4}$ przed sumą).

$4N=\sum _{k=1}^{p-2}[1-{\left(\frac{k}{p}\right)}_L-{\left(\frac{k+1}{p}\right)}_L+{\left(\frac{k}{p}\right)}_L{\left(\frac{k+1}{p}\right)}_L]$

$=p-2-\sum _{k=1}^{p-2}{\left(\frac{k}{p}\right)}_L-\sum _{k=1}^{p-2}{\left(\frac{k+1}{p}\right)}_L+\sum _{k=1}^{p-2}{\left(\frac{k}{p}\right)}_L{\left(\frac{k+1}{p}\right)}_L$

Wartości sum wyliczyliśmy już w punkcie 1. Zatem

$N=\frac{1}{4}[p-2+{\left(\frac{-1}{p}\right)}_L]$

Czyli

$N=\{\begin{array}{ll}\frac{p-1}{4}& \text{ gdy }p=4k+1\\ \frac{p-3}{4}& \text{ gdy }p=4k+3\end{array}$

Powyższy wynik można zapisać w postaci

$N=\lfloor \frac{p-1}{4}\rfloor$

Co należało pokazać.
□

Twierdzenie K17
Niech $p$ będzie liczbą pierwszą nieparzystą. Słowo „trójka” oznacza tutaj trzy kolejne liczby kwadratowe (niekwadratowe) modulo $p$.

Jeżeli $p=4k+3$, to liczba różnych trójek liczb kwadratowych (niekwadratowych) jest równa

$N=\lfloor \frac{p-3}{8}\rfloor$

Jeżeli $p=4k+1$, to liczba różnych trójek liczb niekwadratowych jest równa

$N=\frac{p-3-S(-1)}{8}>\frac{p-3-2\sqrt{p}}{8}$

Jeżeli $p=4k+1$, to liczba różnych trójek liczb kwadratowych jest równa

$N=\frac{p-15+S(-1)}{8}>\frac{p-15-2\sqrt{p}}{8}\text{ gdy }p=8k+1$

$N=\frac{p-7+S(-1)}{8}>\frac{p-7-2\sqrt{p}}{8}\text{ gdy }p=8k+5$

Gdzie przez $S(-1)$ oznaczyliśmy sumę

$S(-1)=\sum _{k=0}^{p-1}{\left(\frac{k(k^2-1)}{p}\right)}_L$

Dowód

Przypadek pierwszy: trójki liczb kwadratowych modulo $\mathit{p}$

Chcemy znaleźć ilość takich liczb $k\in \{2,3,\dots ,p-2\}$, dla których

${\left(\frac{k-1}{p}\right)}_L={\left(\frac{k}{p}\right)}_L={\left(\frac{k+1}{p}\right)}_L=+1$

Ilość liczb $k$ spełniających powyższy warunek łatwo zapisać korzystając z symbolu Legendre'a

$N=\frac{1}{8}\sum _{k=2}^{p-2}[1+{\left(\frac{k-1}{p}\right)}_L][1+{\left(\frac{k}{p}\right)}_L][1+{\left(\frac{k+1}{p}\right)}_L]$

Tylko w przypadku, gdy wszystkie trzy liczby $k-1,k,k+1$ są liczbami kwadratowymi modulo $p$, iloczyn wyrażeń w nawiasach kwadratowych jest różny od zera i równy $8$ (stąd czynnik $\frac{1}{8}$ przed sumą).

$8N=\sum _{k=2}^{p-2}[1+{\left(\frac{k-1}{p}\right)}_L+{\left(\frac{k}{p}\right)}_L+{\left(\frac{k+1}{p}\right)}_L+{\left(\frac{k-1}{p}\right)}_L{\left(\frac{k}{p}\right)}_L+{\left(\frac{k-1}{p}\right)}_L{\left(\frac{k+1}{p}\right)}_L+{\left(\frac{k}{p}\right)}_L{\left(\frac{k+1}{p}\right)}_L+{\left(\frac{k-1}{p}\right)}_L{\left(\frac{k}{p}\right)}_L{\left(\frac{k+1}{p}\right)}_L]$

$=p-3+\sum _{k=2}^{p-2}{\left(\frac{k-1}{p}\right)}_L+\sum _{k=2}^{p-2}{\left(\frac{k}{p}\right)}_L+\sum _{k=2}^{p-2}{\left(\frac{k+1}{p}\right)}_L+\sum _{k=2}^{p-2}{\left(\frac{k-1}{p}\right)}_L{\left(\frac{k}{p}\right)}_L+\sum _{k=2}^{p-2}{\left(\frac{k-1}{p}\right)}_L{\left(\frac{k+1}{p}\right)}_L+\sum _{k=2}^{p-2}{\left(\frac{k}{p}\right)}_L{\left(\frac{k+1}{p}\right)}_L+\sum _{k=2}^{p-2}{\left(\frac{k(k^2-1)}{p}\right)}_L$

Po kolei wyliczamy sumy po prawej stronie

$\sum _{k=2}^{p-2}{\left(\frac{k-1}{p}\right)}_L=-{\left(\frac{-1}{p}\right)}_L-{\left(\frac{-2}{p}\right)}_L$

$\sum _{k=2}^{p-2}{\left(\frac{k}{p}\right)}_L=-1-{\left(\frac{-1}{p}\right)}_L$

$\sum _{k=2}^{p-2}{\left(\frac{k+1}{p}\right)}_L=-1-{\left(\frac{2}{p}\right)}_L$

$\sum _{k=2}^{p-2}{\left(\frac{k-1}{p}\right)}_L{\left(\frac{k}{p}\right)}_L=-1-{\left(\frac{2}{p}\right)}_L$

$\sum _{k=2}^{p-2}{\left(\frac{k-1}{p}\right)}_L{\left(\frac{k+1}{p}\right)}_L=-1-{\left(\frac{-1}{p}\right)}_L$

$\sum _{k=2}^{p-2}{\left(\frac{k}{p}\right)}_L{\left(\frac{k+1}{p}\right)}_L=-1-{\left(\frac{2}{p}\right)}_L$

$\sum _{k=2}^{p-2}{\left(\frac{k(k^2-1)}{p}\right)}_L=\sum _{k=0}^{p-1}{\left(\frac{k(k^2-1)}{p}\right)}_L=S(-1)$

(zobacz K7, K9 i K12). Oznaczenie $S(-1)$ nawiązuje do oznaczenia wprowadzonego w twierdzeniu K12. Wykorzystamy też znalezione w tym twierdzeniu oszacowanie $|S(-1)|$.

Zatem

$8N=p-8-3{\left(\frac{-1}{p}\right)}_L-3{\left(\frac{2}{p}\right)}_L-{\left(\frac{-2}{p}\right)}_L+S(-1)$

Jeżeli $p=8k+1$

$N=\frac{p-15+S(-1)}{8}>\frac{p-15-2\sqrt{p}}{8}$

Jeżeli $p=8k+3$

$N=\frac{p-3}{8}$

Jeżeli $p=8k+5$

$N=\frac{p-7+S(-1)}{8}>\frac{p-7-2\sqrt{p}}{8}$

Jeżeli $p=8k+7$

$N=\frac{p-7}{8}$

Przypadek drugi: trójki liczb niekwadratowych modulo $\mathit{p}$

Chcemy znaleźć ilość takich liczb $k\in \{2,3,\dots ,p-2\}$, dla których

${\left(\frac{k-1}{p}\right)}_L={\left(\frac{k}{p}\right)}_L={\left(\frac{k+1}{p}\right)}_L=-1$

Ilość liczb $k$ spełniających powyższy warunek łatwo zapisać korzystając z symbolu Legendre'a

$N=-\frac{1}{8}\sum _{k=2}^{p-2}[-1+{\left(\frac{k-1}{p}\right)}_L][-1+{\left(\frac{k}{p}\right)}_L][-1+{\left(\frac{k+1}{p}\right)}_L]$

Tylko w przypadku, gdy wszystkie trzy liczby $k-1,k,k+1$ są liczbami niekwadratowymi modulo $p$, iloczyn wyrażeń w nawiasach kwadratowych jest różny od zera i równy $-8$ (stąd czynnik $-\frac{1}{8}$ przed sumą).

$8N=\sum _{k=2}^{p-2}[1-{\left(\frac{k-1}{p}\right)}_L-{\left(\frac{k}{p}\right)}_L-{\left(\frac{k+1}{p}\right)}_L+{\left(\frac{k-1}{p}\right)}_L{\left(\frac{k}{p}\right)}_L+{\left(\frac{k-1}{p}\right)}_L{\left(\frac{k+1}{p}\right)}_L+{\left(\frac{k}{p}\right)}_L{\left(\frac{k+1}{p}\right)}_L-{\left(\frac{k-1}{p}\right)}_L{\left(\frac{k}{p}\right)}_L{\left(\frac{k+1}{p}\right)}_L]$

$=p-3-\sum _{k=2}^{p-2}{\left(\frac{k-1}{p}\right)}_L-\sum _{k=2}^{p-2}{\left(\frac{k}{p}\right)}_L-\sum _{k=2}^{p-2}{\left(\frac{k+1}{p}\right)}_L+\sum _{k=2}^{p-2}{\left(\frac{k-1}{p}\right)}_L{\left(\frac{k}{p}\right)}_L+\sum _{k=2}^{p-2}{\left(\frac{k-1}{p}\right)}_L{\left(\frac{k+1}{p}\right)}_L+\sum _{k=2}^{p-2}{\left(\frac{k}{p}\right)}_L{\left(\frac{k+1}{p}\right)}_L-\sum _{k=2}^{p-2}{\left(\frac{k(k^2-1)}{p}\right)}_L$

Wartości sum już policzyliśmy, rozpatrując przypadek liczb kwadratowych modulo $p$. Zatem

$8N=p-4+{\left(\frac{-1}{p}\right)}_L-{\left(\frac{2}{p}\right)}_L+{\left(\frac{-2}{p}\right)}_L-S(-1)$

Jeżeli $p=8k+1$

$N=\frac{p-3-S(-1)}{8}>\frac{p-3-2\sqrt{p}}{8}$

Jeżeli $p=8k+3$

$N=\frac{p-3}{8}$

Jeżeli $p=8k+5$

$N=\frac{p-3-S(-1)}{8}>\frac{p-3-2\sqrt{p}}{8}$

Jeżeli $p=8k+7$

$N=\frac{p-7}{8}$

Co kończy dowód.
□

Uwaga K18
Korzystając z twierdzenia K17, łatwo można pokazać, że każda liczba pierwsza $p⩾19$ ma co najmniej dwie różne trójki kolejnych liczb kwadratowych modulo $p$ i co najmniej dwie różne trójki kolejnych liczb niekwadratowych modulo $p$.

Najmniejsze liczby niekwadratowe modulo

 

A. Najmniejsze dodatnie liczby niekwadratowe modulo $p$

Przykład K19
W tabeli przedstawiliśmy najmniejsze dodatnie liczby niekwadratowe modulo $p$

$\mathit{m}$	$3$	$5$	$7$	$9$	$11$	$13$	$15$	$17$	$19$	$21$	$23$	$25$	$27$	$29$	$31$	$33$	$35$	$37$	$39$	$41$	$43$	$45$	$47$	$49$	$51$
$\mathbb{n}\mathbf{(}\mathit{p}\mathbf{)}$	$2$	$2$	$3$	$-$	$2$	$2$	$-$	$3$	$2$	$-$	$5$	$-$	$-$	$2$	$3$	$-$	$-$	$2$	$-$	$3$	$2$	$-$	$5$	$-$	$-$

Uwaga K20
Do wyszukiwania liczb $\mathbb{n}=\mathbb{n}(p)$ Czytelnik może wykorzystać prostą funkcję napisaną w PARI/GP

A(p) = 
{
if( p == 2, return(0) );
if( !isprime(p), return(0) );
forprime(q = 2, p, if( jacobi(q, p) == -1, return(q) ));
}

Zauważmy, że choć wyliczamy symbol Jacobiego, to jest to w rzeczywistości symbol Legendre'a, bo wiemy, że liczba $p$ jest liczbą pierwszą (w przypadku, gdy $p$ jest liczbą złożoną, funkcja zwraca zero).

Twierdzenie K21
Niech $\mathbb{n}\in {\mathbb{Z}}_{+}$ i niech $p$ będzie liczbą pierwszą nieparzystą. Jeżeli $\mathbb{n}$ jest najmniejszą liczbą niekwadratową modulo $p$, to jest liczbą pierwszą.

Dowód

Przypuśćmy, że $\mathbb{n}=ab$ jest liczbą złożoną, gdzie $1<a,b<\mathbb{n}$. Z założenia $\mathbb{n}$ jest najmniejszą liczbą niekwadratową modulo $p$, zatem liczby $a,b$ są liczbami kwadratowymi modulo $p$. Z definicji liczb kwadratowych muszą istnieć takie liczby $r,s$, że

$r^2\equiv a(\mathrm{mod}p)$

$s^2\equiv b(\mathrm{mod}p)$

Skąd wynika, że

$\mathbb{n}=ab\equiv (rs{)}^2(\mathrm{mod}p)$

Wbrew założeniu, że $\mathbb{n}$ jest liczbą niekwadratową modulo $p$.
□

Zadanie K22
Pokazać, że najmniejszą liczbą niekwadratową modulo $p$ jest

•  liczba $2$ wtedy i tylko wtedy, gdy $p=8k\pm 3$
•  liczba $3$ wtedy i tylko wtedy, gdy $p=24k\pm 7$
•  liczba $⩾5$ wtedy i tylko wtedy, gdy $p=24k\pm 1$

Rozwiązanie

Z właściwości symbolu Legendre'a (zobacz J29 p.7) wiemy, że

${\left(\frac{2}{p}\right)}_L=\{\begin{array}{ll}1& \text{gdy }p\equiv 1,7(\mathrm{mod}8)\\ -1& \text{gdy }p\equiv 3,5(\mathrm{mod}8)\end{array}$

Wynika stąd natychmiast, dla liczb pierwszych $p$ postaci $8k\pm 3$ (i tylko dla takich liczb) liczba $2$ jest liczbą niekwadratową, czyli również najmniejszą liczbą niekwadratową modulo $p$.

Z zadania J41 wynika, że liczba $3$ jest liczbą niekwadratową jedynie dla liczb pierwszych postaci $12k\pm 5$. Zatem dla liczb pierwszych, które są jednocześnie postaci $p=8k\pm 1$ i $p=12j\pm 5$, liczba $3$ jest najmniejszą liczbą niekwadratową modulo $p$. Z czterech warunków

$p=8k+1\text{i}p=12j+5$

$p=8k+1\text{i}p=12j+7$

$p=8k+7\text{i}p=12j+5$

$p=8k+7\text{i}p=12j+7$

Drugi i trzeci nie są możliwe, bo modulo $4$ otrzymujemy

$p\equiv 1(\mathrm{mod}4)\text{i}p\equiv 3(\mathrm{mod}4)$

$p\equiv 3(\mathrm{mod}4)\text{i}p\equiv 1(\mathrm{mod}4)$

a z pierwszego i czwartego mamy

$3p=24k+3\text{i}2p=24j+10⟹p=24(k-j)-7⟹p\equiv -7(\mathrm{mod}24)$

$3p=24k+21\text{i}2p=24j+14⟹p=24(k-j)+7⟹p\equiv 7(\mathrm{mod}24)$

Zauważmy, że problem mogliśmy zapisać w postaci układu kongruencji

$p\equiv \pm 1(\mathrm{mod}8)$

$p\equiv \pm 5(\mathrm{mod}12)$

Gdyby moduły tych kongruencji były względnie pierwsze, to każdemu wyborowi znaków odpowiadałaby pewna kongruencja równoważna (zobacz J3). Widzimy, że w przypadku, gdy moduły nie są względnie pierwsze, kongruencja równoważna może istnieć, ale nie musi. Rozwiązując taki problem, wygodnie jest skorzystać z programu PARI/GP. Wystarczy wpisać

chinese(Mod(1, 8), Mod(5, 12)) = Mod(17, 24)
chinese(Mod(1, 8), Mod(-5, 12)) - błąd 
chinese(Mod(-1, 8), Mod(5, 12)) - błąd 
chinese(Mod(-1, 8), Mod(-5, 12)) = Mod(7, 24)

Ostatni punkt zadania rozwiążemy tą metodą. Liczba większa lub równa $5$ jest najmniejszą liczbą niekwadratową modulo $p$ wtedy i tylko wtedy, gdy liczby $2$ i $3$ są liczbami kwadratowymi modulo $p$, co oznacza, że liczba pierwsza $p$ spełnia kongruencje

$p\equiv \pm 1(\mathrm{mod}8)$

$p\equiv \pm 1(\mathrm{mod}12)$

Postępując jak wyżej, otrzymujemy

chinese(Mod(1, 8), Mod(1, 12)) = Mod(1, 24)
chinese(Mod(1, 8), Mod(-1, 12)) - błąd 
chinese(Mod(-1, 8), Mod(1, 12)) - błąd 
chinese(Mod(-1, 8), Mod(-1, 12)) = Mod(23, 24)

Co należało pokazać.
□

Twierdzenie K23
Dla każdej liczby pierwszej $p_n$ istnieje nieskończenie wiele takich liczb pierwszych $q$, że $p_n$ jest najmniejszą liczbą niekwadratową modulo $q$.

Dowód

Niech $2,p_2,\dots ,p_{n-1},p_n$ będą kolejnymi liczbami pierwszymi. Wybierzmy liczbę $u$ tak, aby spełniała układ kongruencji

$\begin{array}{rl}u& \equiv 1(\mathrm{mod}8p_2\cdot \dots \cdot p_{n-1})\\ u& \equiv a(\mathrm{mod}{p}_n)\end{array}$

gdzie $a$ oznacza dowolną liczbą niekwadratową modulo $p_n$. Na podstawie chińskiego twierdzenia o resztach (zobacz J3) powyższy układ kongruencji może być zapisany w postaci kongruencji równoważnej

$u\equiv c(\mathrm{mod}8p_2\cdot \dots \cdot p_n)$

Zauważmy, że żadna z liczb pierwszych $p_k$, gdzie $1⩽k⩽n$ nie dzieli liczby $c$, bo mielibyśmy

$u\equiv 0(\mathrm{mod}{p}_k)$

wbrew wypisanemu wyżej układowi kongruencji. Zatem $gcd(c,8p_2\cdot \dots \cdot p_n)=1$ i z twierdzenia Dirichleta (zobacz C27) wiemy, że wśród liczb $u$ spełniających kongruencję $u\equiv c(\mathrm{mod}8p_2\cdot \dots \cdot p_n)$ występuje nieskończenie wiele liczb pierwszych (bo wśród tych liczb są liczby postaci $8p_2\cdot \dots \cdot p_n\cdot k+c$, gdzie $k\in {\mathbb{Z}}_{+}$). Oznaczmy przez $q$ dowolną z tych liczb pierwszych.

Ponieważ $q\equiv 1(\mathrm{mod}8)$, to ${\left(\frac{2}{q}\right)}_L=1$ (zobacz J29), a dla wszystkich liczb pierwszych nieparzystych $p_k<p_n$ mamy

${\left(\frac{p_k}{q}\right)}_L={\left(\frac{q}{p_k}\right)}_L\cdot (-1{)}^{\frac{q-1}{2}\cdot \frac{p_k-1}{2}}={\left(\frac{q}{p_k}\right)}_L={\left(\frac{c}{p_k}\right)}_L={\left(\frac{1}{p_k}\right)}_L=1$

bo $8\mid (q-1)$. Dla liczby pierwszej $p_n$ jest

${\left(\frac{p_n}{q}\right)}_L={\left(\frac{q}{p_n}\right)}_L\cdot (-1{)}^{\frac{q-1}{2}\cdot \frac{p_n-1}{2}}={\left(\frac{q}{p_n}\right)}_L={\left(\frac{c}{p_n}\right)}_L={\left(\frac{a}{p_n}\right)}_L=-1$

Zatem wszystkie liczby pierwsze mniejsze od $p_n$ są liczbami kwadratowymi modulo $q$, a liczba pierwsza $p_n$ jest najmniejszą liczbą niekwadratową modulo $q$. Zauważmy, że $q$ była dowolnie wybraną liczbą pierwszą z nieskończenie wielu liczb pierwszych występujących w ciągu arytmetycznym $8p_2\cdot \dots \cdot p_n\cdot k+c$, gdzie $k\in {\mathbb{Z}}_{+}$. Co kończy dowód.
□

Twierdzenie K24 (Sarvadaman Chowla)
Istnieje niekończenie wiele liczb pierwszych $p$ takich, że najmniejsza liczba niekwadratowa modulo $p$ jest większa od $\frac{\log p}{2L\log 2}$, gdzie $L$ jest stałą Linnika.

Dowód

Niech $a=4P(m)$, gdzie $P(m)$ jest iloczynem wszystkich liczb pierwszych nie większych od $m$. Z twierdzenia Dirichleta (zobacz C27) wiemy, że w ciągu arytmetycznym $u_k=ak+1$ występuje nieskończenie wiele liczb pierwszych. Niech $p$ oznacza dowolną z nich.

Ponieważ $p\equiv 1(\mathrm{mod}8)$, to

${\left(\frac{2}{p}\right)}_L=1$

(zobacz J29 p.7). Oczywiście $p\equiv 1(\mathrm{mod}4)$, zatem dla dowolnej liczby pierwszej nieparzystej $q_i⩽m$ z twierdzenia J29 p.9 otrzymujemy

${\left(\frac{q_i}{p}\right)}_L={\left(\frac{p}{q_i}\right)}_L={\left(\frac{ak+1}{q_i}\right)}_L={\left(\frac{1}{q_i}\right)}_L=1$

Wynika stąd, że najmniejsza liczba niekwadratowa modulo $p$ jest większa od $m$. Wiemy też, że (zobacz A9)

$a=4P(m)<4\cdot 4^m=4^{m+1}$

Załóżmy teraz, że $p$ jest najmniejszą liczbą pierwszą w ciągu arytmetycznym $u_k=ak+1$, a liczba $m$ została wybrana tak, że liczba $a=4P(m)$ jest dostatecznie duża i możliwe jest skorzystanie z twierdzenia Linnika (zobacz C30). Dostajemy natychmiast oszacowanie

$p=p_{min}(a,1)<a^L$

gdzie $L$ jest stałą Linnika (możemy przyjąć $L=5$). Łącząc powyższe oszacowania, łatwo otrzymujemy oszacowanie najmniejszej liczby niekwadratowej modulo $p$

$\mathbb{n}(p)⩾m+1>{\log }_{4}a=\frac{\log a}{\log 4}=\frac{\log a^L}{2L\log 2}>\frac{\log p}{2L\log 2}$

Każdemu wyborowi innej liczby $m^{\prime }>m$ takiej, że $P(m^{\prime })>P(m)$ odpowiada inna liczba pierwsza $p^{\prime }$ taka, że $\mathbb{n}(p^{\prime })>\frac{\log p^{\prime }}{2L\log 2}$, zatem liczb pierwszych $p$ dla których najmniejsza liczba niekwadratowa modulo $p$ jest większa od $\frac{\log p}{2L\log 2}$ jest nieskończenie wiele.
□

Uwaga K25
W twierdzeniu K23 pokazaliśmy, że dla każdej liczby pierwszej $\mathbb{n}$ istnieją takie liczby pierwsze $p$, że $\mathbb{n}$ jest najmniejszą liczbą niekwadratową modulo $p$. Zatem zbiór $S_{\mathbb{n}}$ liczb pierwszych takich, że dla każdej liczby $p\in S_{\mathbb{n}}$ liczba $\mathbb{n}$ jest najmniejszą liczbą niekwadratową modulo $p$ jest zbiorem niepustym. Wynika stąd, że zbiór $S_{\mathbb{n}}$ ma element najmniejszy i możemy te najmniejsze liczby pierwsze łatwo znaleźć – wystarczy w PARI/GP napisać proste polecenie

forprime(n = 2, 50, forprime(p = 2, 10^10, if( A(p) == n, print(n, "   ", p); break() )))

W tabeli przedstawiamy uzyskane rezultaty (zobacz też A000229).

$\mathbb{n}$	$2$	$3$	$5$	$7$	$11$	$13$	$17$	$19$	$23$	$29$	$31$	$37$	$41$	$43$	$47$
$\mathit{p}$	$3$	$7$	$23$	$71$	$311$	$479$	$1559$	$5711$	$10559$	$18191$	$31391$	$422231$	$701399$	$366791$	$3818929$

Uwaga K26
Z nierówności Pólyi-Winogradowa (zobacz K8) wynika natychmiast oszacowanie najmniejszej liczby niekwadratowej modulo $p$. Ponieważ najdłuższy ciąg kolejnych liczb kwadratowych modulo $p$ nie może być dłuższy od $\lfloor \sqrt{p}\log p\rfloor$, to

$\mathbb{n}(p)⩽\lfloor \sqrt{p}\log p\rfloor +1<\sqrt{p}\log p+1$

Pokażemy, że powyższe oszacowanie można łatwo wzmocnić.

Twierdzenie K27
Niech $p$ będzie liczbą pierwszą nieparzystą, a $\mathbb{n}$ będzie najmniejszą liczbą niekwadratową modulo $p$. Prawdziwe jest oszacowanie

$\mathbb{n}(p)<\sqrt{p}+\frac{1}{2}$

Dowód

Ponieważ $\mathbb{n}\nmid p$, to z oszacowania $x-1<\lfloor x\rfloor ⩽x$ wynika, że

$\frac{p}{\mathbb{n}}-1<\lfloor \frac{p}{\mathbb{n}}\rfloor <\frac{p}{\mathbb{n}}$

$p<\mathbb{n}\lfloor \frac{p}{\mathbb{n}}\rfloor +\mathbb{n}<p+\mathbb{n}$

Niech $u=\lfloor \frac{p}{\mathbb{n}}\rfloor +1$, mamy

$0<\mathbb{n}u-p<\mathbb{n}$

Liczba $\mathbb{n}u-p$ musi być liczbą kwadratową modulo $p$, zatem

$1={\left(\frac{\mathbb{n}u-p}{p}\right)}_L={\left(\frac{\mathbb{n}}{p}\right)}_L\cdot {\left(\frac{u}{p}\right)}_L=-{\left(\frac{u}{p}\right)}_L$

Ale z założenia $\mathbb{n}$ jest najmniejszą liczbą taką, że ${\left(\frac{\mathbb{n}}{p}\right)}_L=-1$. Wynika stąd, że musi być $\mathbb{n}⩽u$ i łatwo znajdujemy, że

$\mathbb{n}⩽\lfloor \frac{p}{\mathbb{n}}\rfloor +1<\frac{p}{\mathbb{n}}+1$

${\mathbb{n}}^2<p+\mathbb{n}$

Ponieważ wypisane liczby są liczbami całkowitymi, to ostatnią nierówność możemy zapisać w postaci

${\mathbb{n}}^2⩽p+\mathbb{n}-1$

Skąd otrzymujemy

${(\mathbb{n}-\frac{1}{2})}^2⩽p-\frac{3}{4}$

$\mathbb{n}⩽\frac{1}{2}+\sqrt{p-\frac{3}{4}}<\frac{1}{2}+\sqrt{p}$

Co należało pokazać.
□

Twierdzenie K28*
Niech $p$ będzie liczbą pierwszą nieparzystą, a $\mathbb{n}$ będzie najmniejszą liczbą niekwadratową modulo $p$. Dla $p⩾5$ prawdziwe jest oszacowanie

$\mathbb{n}(p)⩽1.1\cdot p^{1/4}\log p$

Uwaga K29
Liczby $\mathbb{n}=\mathbb{n}(p)$ są zaskakująco małe. Średnia wartość $\mathbb{n}=\mathbb{n}(p)$, gdzie $p$ są nieparzystymi liczbami pierwszymi, jest równa

$\underset{x\to \mathrm{\infty }}{lim}\frac{1}{\pi (x)}\sum _{p⩽x}\mathbb{n}(p)=\sum _{k=1}^{\mathrm{\infty }}\frac{p_k}{2^k}=3.674643966\dots$

Uwaga K30
Możemy też badać najmniejsze nieparzyste liczby niekwadratowe modulo $p$. Pokażemy, że są one również liczbami pierwszymi. W tabeli przedstawiliśmy najmniejsze nieparzyste liczby niekwadratowe modulo $p$.

$\mathit{m}$	$5$	$7$	$9$	$11$	$13$	$15$	$17$	$19$	$21$	$23$	$25$	$27$	$29$	$31$	$33$	$35$	$37$	$39$	$41$	$43$	$45$	$47$	$49$	$51$
${\mathbb{n}}_{\mathbf{1}}\mathbf{(}\mathit{p}\mathbf{)}$	$3$	$3$	$-$	$7$	$5$	$-$	$3$	$3$	$-$	$5$	$-$	$-$	$3$	$3$	$-$	$-$	$5$	$-$	$3$	$3$	$-$	$5$	$-$	$-$

Twierdzenie K31
Dla każdej liczby pierwszej $p⩾5$ najmniejsza nieparzysta liczba niekwadratowa modulo $p$ jest liczbą pierwszą mniejszą od $p$.

Dowód

Niech $S\subset \{1,2,\dots ,p-1\}$ będzie zbiorem wszystkich nieparzystych liczb niekwadratowych modulo $p$. Z twierdzenia J24 wiemy, że jeżeli $p$ jest liczbą pierwszą nieparzystą, to w zbiorze $\{1,2,\dots ,p-1\}$ jest dokładnie $\frac{p-1}{2}$ liczb kwadratowych modulo $p$ i tyle samo liczb niekwadratowych modulo $p$. W zbiorze $\{1,2,\dots ,p-1\}$ mamy też dokładnie $\frac{p-1}{2}$ liczb parzystych i tyle samo liczb nieparzystych.

Wszystkie liczby parzyste nie mogą być liczbami niekwadratowymi modulo $p$, bo $4=2^2<5⩽p$ jest parzystą liczbą kwadratową modulo $p$, czyli wśród liczb nieparzystych musi istnieć przynajmniej jedna liczba niekwadratowa modulo $p$. Wynika stąd, że zbiór $S$ nie jest zbiorem pustym, zatem ma element najmniejszy. Pokażemy, że najmniejszy element zbioru $S$ jest liczbą pierwszą.

Niech $3⩽{\mathbb{n}}_{\mathbf{1}}⩽p-2$ będzie najmniejszą nieparzystą liczbą niekwadratową modulo $p$. Wynika stąd, że każda liczba $a<{\mathbb{n}}_{\mathbf{1}}$ musi być liczbą parzystą lub liczbą kwadratową modulo $p$. Przypuśćmy, że ${\mathbb{n}}_{\mathbf{1}}$ jest liczbą złożoną, czyli ${\mathbb{n}}_{\mathbf{1}}=ab$, gdzie $1<a,b<{\mathbb{n}}_{\mathbf{1}}$. Zauważmy, że żadna z liczb $a,b$ nie może być liczbą parzystą, bo wtedy liczba ${\mathbb{n}}_{\mathbf{1}}$ również byłaby liczbą parzystą wbrew określeniu liczby ${\mathbb{n}}_{\mathbf{1}}$. Zatem obie liczby $a,b$ muszą być nieparzystymi liczbami kwadratowymi, co jest niemożliwe, bo

$-1={\left(\frac{{\mathbb{n}}_{\mathbf{1}}}{p}\right)}_J={\left(\frac{ab}{p}\right)}_J={\left(\frac{a}{p}\right)}_J\cdot {\left(\frac{b}{p}\right)}_J$

i jeden z czynników po prawej stronie musi być ujemny. Co oznacza, że jedna z liczb $a,b$ jest nieparzystą liczbą niekwadratową modulo $p$ mniejszą od ${\mathbb{n}}_{\mathbf{1}}$ wbrew określeniu liczby ${\mathbb{n}}_{\mathbf{1}}$. Uzyskana sprzeczność pokazuje, że liczba ${\mathbb{n}}_{\mathbf{1}}$ jest liczbą pierwszą. Co kończy dowód.
□

B. Najmniejsze dodatnie liczby niekwadratowe modulo $m$

Uwaga K32
Najmniejsze liczby niekwadratowe modulo $m$ są naturalnym uogólnieniem najmniejszych liczb niekwadratowych modulo $p.$ W jednym i drugim przypadku liczba $\mathbb{n}$ jest najmniejszą liczbą niekwadratową w zbiorze wszystkich liczb niekwadratowych dodatnich nie większych od $p$ lub $m.$ Dlatego będziemy je oznaczali również jako $\mathbb{n}(m).$

Definicja K33
Niech $m\in \mathbb{Z}$ i $m⩾3.$ Powiemy, że $\mathbb{n}(m)$ jest najmniejszą liczbą niekwadratową modulo $m$, gdy $\mathbb{n}$ jest najmniejszą liczbą dodatnią względnie pierwszą z $m$ taką, że kongruencja

$x^2\equiv \mathbb{n}(\mathrm{mod}m)$

nie ma rozwiązania.

Przykład K34
W tabeli przedstawiliśmy najmniejsze liczby niekwadratowe modulo $p$ i najmniejsze liczby niekwadratowe modulo $m.$

$\mathit{m}$	$3$	$5$	$7$	$9$	$11$	$13$	$15$	$17$	$19$	$21$	$23$	$25$	$27$	$29$	$31$	$33$	$35$	$37$	$39$	$41$	$43$	$45$	$47$	$49$	$51$
$\mathbb{n}\mathbf{(}\mathit{p}\mathbf{)}$	$2$	$2$	$3$	$-$	$2$	$2$	$-$	$3$	$2$	$-$	$5$	$-$	$-$	$2$	$3$	$-$	$-$	$2$	$-$	$3$	$2$	$-$	$5$	$-$	$-$
$\mathbb{n}\mathbf{(}\mathit{m}\mathbf{)}$	$2$	$2$	$3$	$2$	$2$	$2$	$2$	$3$	$2$	$2$	$5$	$2$	$2$	$2$	$3$	$2$	$2$	$2$	$2$	$3$	$2$	$2$	$5$	$3$	$2$

$\mathit{m}$	$4$	$6$	$8$	$10$	$12$	$14$	$16$	$18$	$20$	$22$	$24$	$26$	$28$	$30$	$32$	$34$	$36$	$38$	$40$	$42$	$44$	$46$	$48$	$50$	$52$
$\mathbb{n}\mathbf{(}\mathit{m}\mathbf{)}$	$3$	$5$	$3$	$3$	$5$	$3$	$3$	$5$	$3$	$7$	$5$	$5$	$3$	$7$	$3$	$3$	$5$	$3$	$3$	$5$	$3$	$5$	$5$	$3$	$3$

Uwaga K35
Do wyszukiwania liczb $\mathbb{n}(m)$ Czytelnik może wykorzystać prostą funkcję napisaną w PARI/GP

B(m) = 
{
local(p, res);
p = 1;
while( p < m,
       p = nextprime(p + 1);
       if( m%p == 0, next() );
       res = -1;
       for( k = 2, floor(m/2), if( k^2%m == p, res = 1; break() ) );
       if( res == -1, return(p) );
     );
}

Obliczenia można wielokrotnie przyspieszyć, modyfikując kod funkcji tak, aby uwzględniał pokazane niżej właściwości oraz parzystość liczby $m.$ Tutaj przedstawiamy tylko przykład, który wykorzystuje część tych możliwości.

Pokaż kod

B(m) = 
{
local(p, res, t);
t = m%8;
if( t == 3 || t == 5, return(2) );
t = m%12;
if( t == 4 || t == 8, return(3) );
t = m%24;
if( t == 9 || t == 15, return(2) );
if( t == 10 || t == 14, return(3) );
t = m%30;
if( t == 6 || t == 12 || t == 18 || t == 24, return(5) );
p = 1;
while( p < m,
       p = nextprime(p + 1);
       if( m%p == 0, next() );
       res = -1;
       for( k = 2, floor(m/2), if( k^2%m == p, res = 1; break() ) );
       if( res == -1, return(p) );
     );
}

Twierdzenie K36
Niech $m\in \mathbb{Z}$ i $m⩾3.$ Jeżeli $\mathbb{n}$ jest najmniejszą liczbą niekwadratową modulo $m$, to $\mathbb{n}$ jest liczbą pierwszą.

Dowód

Przypuśćmy, że $\mathbb{n}=ab$ jest liczbą złożoną, gdzie $1<a,b<\mathbb{n}.$ Z założenia $\mathbb{n}$ jest najmniejszą liczbą niekwadratową modulo $m$, zatem liczby $a,b$ są liczbami kwadratowymi modulo $m.$ Z definicji liczb kwadratowych muszą istnieć takie liczby $r,s$, że

$r^2\equiv a(\mathrm{mod}m)$

$s^2\equiv b(\mathrm{mod}m)$

Skąd wynika, że

$\mathbb{n}=ab\equiv (rs{)}^2(\mathrm{mod}m)$

Wbrew założeniu, że $\mathbb{n}$ jest liczbą niekwadratową modulo $m.$
□

Zadanie K37
Niech $m\in {\mathbb{Z}}_{+}$ i $\mathbb{n}(m)$ będzie najmniejszą liczbą niekwadratową modulo $m.$ Pokazać, że jeżeli $m=8k\pm 3$, to $\mathbb{n}(m)=2.$

Rozwiązanie

Z twierdzenia J36 wiemy, że ${\left(\frac{2}{m}\right)}_J=-1$, gdy $m=8k\pm 3.$ Wynika stąd, że $2$ jest liczbą niekwadratową modulo $m$, a jeśli tak, to musi być najmniejszą liczbą niekwadratową modulo $m.$ Co należało pokazać.
□

Zadanie K38
Niech $m\in {\mathbb{Z}}_{+}$ i $\mathbb{n}(m)$ będzie najmniejszą liczbą niekwadratową modulo $m.$ Pokazać, że jeżeli spełniony jest jeden z warunków

•   $4\mid m$ i $gcd(3,m)=1$
•   $m=12k\pm 4$

to $\mathbb{n}(m)=3.$

Rozwiązanie

Zauważmy, że $2$ nie może być najmniejszą liczbą niekwadratową modulo $m$, bo $2\mid m.$ Rozważmy kongruencję

$x^2\equiv 3(\mathrm{mod}m)$

Z założenia $4\mid m$, co nie wyklucza możliwości, że również $8\mid m.$ Ponieważ $4\nmid (3-1)$ i $8\nmid (3-1)$, to z twierdzenia J50 wynika, że kongruencja $x^2\equiv 3(\mathrm{mod}m)$ nie ma rozwiązania. Jeśli tylko $3\nmid m$, to $\mathbb{n}(m)=3.$ W pierwszym punkcie jest to założone wprost, w drugim łatwo widzimy, że $3\nmid (12k\pm 4).$

Można też zauważyć, że żądanie, aby $gcd(3,m)=1$, prowadzi do dwóch układów kongruencji

$\begin{array}{rl}m& \equiv 0(\mathrm{mod}4)\\ m& \equiv 1(\mathrm{mod}3)\end{array}$

oraz

$\begin{array}{rl}m& \equiv 0(\mathrm{mod}4)\\ m& \equiv 2(\mathrm{mod}3)\end{array}$

którym, na mocy chińskiego twierdzenia o resztach, odpowiadają dwie kongruencje równoważne

$m\equiv \pm 4(\mathrm{mod}12)$

Co należało pokazać.
□

Zadanie K39
Niech $m=24k\pm 10.$ Pokazać, że $\mathbb{n}(m)=3.$

Rozwiązanie

Zapiszmy $m$ w postaci $m=2m^{\prime }$, gdzie $m^{\prime }=12k\pm 5.$ Gdyby kongruencja

$x^2\equiv 3(\mathrm{mod}2m^{\prime })$

miała rozwiązanie, to również kongruencja

$x^2\equiv 3(\mathrm{mod}{m}^{\prime })$

miałaby rozwiązanie, ale jest to niemożliwe, bo ${\left(\frac{3}{m^{\prime }}\right)}_J=-1$ (zobacz J41), czyli $3$ jest liczbą niekwadratową modulo $m^{\prime }.$ Ponieważ $2\mid m$, to $2$ nie może być najmniejszą liczbą niekwadratową modulo $m.$ Wynika stąd, że $\mathbb{n}(m)=3.$
□

Twierdzenie K40
Niech $m\in {\mathbb{Z}}_{+}$ i $S_2=\{3,5,11,13,19,29,37,43,\dots \}$ będzie zbiorem liczb pierwszych $p$ takich, że ${\left(\frac{2}{p}\right)}_J=-1.$ Jeżeli $m$ jest liczbą nieparzystą podzielną przez $p\in S_2$, to $\mathbb{n}(m)=2.$

Dowód

Z założenia $p\mid m$ i ${\left(\frac{2}{p}\right)}_J=-1.$ Zatem kongruencja

$x^2\equiv 2(\mathrm{mod}m)$

nie ma rozwiązania (zobacz J50). Ponieważ $2\nmid m$, to $\mathbb{n}(m)=2.$

Uwaga: zbiór $S_2$ tworzą liczby pierwsze postaci $8k\pm 3$ (zobacz J36).
□

Twierdzenie K41
Niech $m\in {\mathbb{Z}}_{+}$ i $S_3=\{5,7,17,19,29,31,41,43,\dots \}$ będzie zbiorem liczb pierwszych $p$ takich, że ${\left(\frac{3}{p}\right)}_J=-1.$ Jeżeli $m$ jest liczbą parzystą niepodzielną przez $3$ i podzielną przez $p\in S_3$, to $\mathbb{n}(m)=3.$

Dowód

Z założenia $p\mid m$ i ${\left(\frac{3}{p}\right)}_J=-1.$ Zatem kongruencja

$x^2\equiv 3(\mathrm{mod}m)$

nie ma rozwiązania (zobacz J50). Ponieważ $2\mid m$ i $3\nmid m$, to $\mathbb{n}(m)=3.$

Uwaga: zbiór $S_3$ tworzą liczby pierwsze postaci $12k\pm 5$ (zobacz J41).
□

Twierdzenie K42
Jeżeli $m$ jest liczbą dodatnią podzielną przez $6$ i niepodzielną przez $5$, to $\mathbb{n}(m)=5.$

Dowód

Z założenia $3\mid m$ i ${\left(\frac{5}{3}\right)}_J={\left(\frac{2}{3}\right)}_J=-1.$ Zatem kongruencja

$x^2\equiv 5(\mathrm{mod}m)$

nie ma rozwiązania (zobacz J50). Ponieważ $2\mid m$, $3\mid m$ i $5\nmid m$, to $\mathbb{n}(m)=5.$
□

Twierdzenie K43
Niech $m\in {\mathbb{Z}}_{+}$ i $p⩾5$ będzie liczbą pierwszą. Jeżeli iloczyn wszystkich liczb pierwszych mniejszych od $p$ dzieli $m$ i $p\nmid m$, to $\mathbb{n}(m)=p$.

Dowód

Z twierdzenia K75 wiemy, że istnieje liczba pierwsza nieparzysta $q<p$ taka, że ${\left(\frac{p}{q}\right)}_J=-1.$ Z założenia $q\mid m$, zatem kongruencja

$x^2\equiv p(\mathrm{mod}m)$

nie ma rozwiązania (zobacz J50). Ponieważ wszystkie liczby pierwsze mniejsze od $p$ dzielą $m$, to $\mathbb{n}(m)=p$. Co należało pokazać.
□

Zadanie K44
Pokazać, że podanym w pierwszej kolumnie postaciom liczby $m$ odpowiadają wymienione w drugiej kolumnie wartości $\mathbb{n}(m).$

Postać liczby $\mathit{m}$	$\mathit{𝕟}\mathbf{(}\mathit{m}\mathbf{)}$	Uwagi
$m=24k\pm 9$	$2$	K40
$m=120k\pm 25$	$2$
$m=120k\pm 55$	$2$
$m=120k\pm 50$	$3$	K41
$m=30k\pm 6$	$5$	K42, K43
$m=30k\pm 12$	$5$
$m=210k\pm 30$	$7$	K43
$m=210k\pm 60$	$7$
$m=210k\pm 90$	$7$

Twierdzenie K45
Niech $m$ będzie liczbą nieparzystą, a $\mathbb{n}(m)$ będzie najmniejszą liczbą niekwadratową modulo $m.$ Mamy

$\begin{array}{lll}\mathbb{n}(2m)>\mathbb{n}(m)& & \text{gdy}\mathbb{n}(m)=2\\ \mathbb{n}(2m)=\mathbb{n}(m)& & \text{gdy}\mathbb{n}(m)>2\end{array}$

Dowód

Punkt 1.

W przypadku, gdy $\mathbb{n}(m)=2$, mamy $\mathbb{n}(2m)>2=\mathbb{n}(m)$, bo $\mathbb{n}(2m)$ musi być liczbą względnie pierwszą z $2m.$

Punkt 2.

Z definicji najmniejszej liczby niekwadratowej modulo $m$ wiemy, że kongruencja

$x^2\equiv \mathbb{n}(m)(\mathrm{mod}m)$

nie ma rozwiązania. Oznacza to, że istnieje liczba pierwsza nieparzysta $p$ taka, że $p\mid m$ i ${\left(\frac{\mathbb{n}(m)}{p}\right)}_J=-1.$ Ponieważ $p\mid 2m$, to wynika stąd natychmiast, że kongruencja

$x^2\equiv \mathbb{n}(m)(\mathrm{mod}2m)$

również nie ma rozwiązania (zobacz J50).

Zatem $\mathbb{n}(2m)⩽\mathbb{n}(m).$ Niech $q$ będzie liczbą pierwszą taką, że $2<q<\mathbb{n}(m).$ Kongruencję

$x^2\equiv q(\mathrm{mod}2m)(1)$

możemy zapisać w postaci układu kongruencji równoważnych (zobacz J1)

$\begin{array}{rl}{x}^2& \equiv q(\mathrm{mod}m)(2)\\ x^2& \equiv q(\mathrm{mod}2)(3)\end{array}$

Z definicji $q$ jest liczbą kwadratową modulo $m$, zatem kongruencja $(2)$ ma rozwiązanie – oznaczmy to rozwiązanie przez $x_0.$ Łatwo zauważamy, że liczba

$x_0^{\prime }=\{\begin{array}{ll}{x}_0& \text{gdy}{x}_0\equiv 1(\mathrm{mod}2)\\ x_0+m& \text{gdy}{x}_0\equiv 0(\mathrm{mod}2)\end{array}$

jest rozwiązaniem układu kongruencji $(2)$ i $(3)$, a tym samym kongruencja $(1)$ ma rozwiązanie dla każdego $2<q<\mathbb{n}(m).$ Wynika stąd, że $\mathbb{n}(2m)=\mathbb{n}(m).$
□

Twierdzenie K46
Niech $m$ będzie liczbą nieparzystą, a $\mathbb{n}(m)$ będzie najmniejszą liczbą niekwadratową modulo $m.$ Mamy

$\begin{array}{lllll}\mathbb{n}(4m)⩾5& & \mathbb{n}(m)=2& & \text{gdy }3\mid m\\ \mathbb{n}(4m)=3& & \mathbb{n}(m)⩾2& & \text{gdy }3\nmid m\end{array}$

Dowód

Punkt 1.

Z twierdzenia K40 wynika, że w przypadku, gdy $3\mid m$, to $\mathbb{n}(m)=2.$ Ponieważ $2\mid 4m$ i $3\mid 4m$, to $\mathbb{n}(4m)⩾5.$

Punkt 2.

Ponieważ $m$ jest liczbą nieparzystą, to $8\nmid 4m$, ale $4\mid 4m$ i $4\nmid (3-1)$, zatem z twierdzenia J50 wynika, że kongruencja

$x^2\equiv 3(\mathrm{mod}4m)$

nie ma rozwiązania. Ponieważ $2\mid 4m$ i $3\nmid 4m$, to $\mathbb{n}(4m)=3.$
□

Twierdzenie K47
Niech $p$ będzie liczbą pierwszą nieparzystą. Jeżeli $a$ jest liczbą niekwadratową modulo $p$ i $p\mid m$, to $a$ jest liczbą niekwadratową modulo $m.$

Dowód

Wiemy, że liczba $a$ jest liczbą kwadratową modulo $m$ wtedy i tylko wtedy, gdy kongruencja

$x^2\equiv a(\mathrm{mod}m)$

ma rozwiązanie. Przypuśćmy, że liczba $a$ jest liczbą kwadratową modulo $m.$ Zatem istnieje taka liczba $k\in \mathbb{Z}$, że

$k^2\equiv a(\mathrm{mod}m)$

Ponieważ z założenia $p\mid m$, to prawdziwa jest też kongruencja

$k^2\equiv a(\mathrm{mod}p)$

co przeczy założeniu, że liczba $a$ jest liczbą niekwadratową modulo $p.$
□

Twierdzenie K48
Niech $m⩾3$ będzie liczbą nieparzystą. Jeżeli liczba $\mathbb{n}=\mathbb{n}(m)$ jest najmniejszą liczbą niekwadratową modulo $m$, to istnieje taki dzielnik pierwszy $p$ liczby $m$, że $\mathbb{n}$ jest najmniejszą liczbą niekwadratową modulo $p.$

Dowód

Przypuśćmy, że taki dzielnik pierwszy nie istnieje. Zatem mamy zbiór dzielników pierwszych liczby $m$: $\{p_1,\dots ,p_s\}$ i powiązany z dzielnikami pierwszymi $p_k$ zbiór najmniejszych liczb niekwadratowych modulo $p_k$: $\{{\mathbb{n}}_1,\dots ,{\mathbb{n}}_s\}$, z których każda jest liczbą niekwadratową modulo $m$ (zobacz K47). Wynika stąd, że liczba $\mathbb{n}=\mathbb{n}(m)$ musi być mniejsza od każdej z liczb ${\mathbb{n}}_k.$

Z definicji liczba $\mathbb{n}=\mathbb{n}(m)$ jest liczbą niekwadratową modulo $m$, co oznacza, że kongruencja

$x^2\equiv \mathbb{n}(\mathrm{mod}m)$

nie ma rozwiązania. Niech $m=p_1^{{\alpha }_1}\cdot \dots \cdot p_s^{{\alpha }_s}.$ Zatem przynajmniej jedna z kongruencji

$x^2\equiv \mathbb{n}(\mathrm{mod}{p}_k^{{\alpha }_k})$

musi nie mieć rozwiązania (zobacz J11). Z twierdzenia J44 wiemy, że wtedy kongruencja

$x^2\equiv \mathbb{n}(\mathrm{mod}{p}_k)$

również nie ma rozwiązania. Zatem $\mathbb{n}$ jest liczbą niekwadratową modulo $p_k$ i $\mathbb{n}<{\mathbb{n}}_k$, co przeczy definicji liczby ${\mathbb{n}}_k.$
□

Twierdzenie K49
Niech $m⩾3$ będzie liczbą nieparzystą. Jeżeli $m=p_1^{{\alpha }_1}\cdot \dots \cdot p_s^{{\alpha }_s}$, to

$\mathbb{n}(m)=min(\mathbb{n}(p_1),\dots ,\mathbb{n}(p_s))$

gdzie $\mathbb{n}(m)$ jest najmniejszą liczbą kwadratową modulo $m$, a $\mathbb{n}(p_k)$ są najmniejszymi liczbami kwadratowymi modulo $p_k.$

Dowód

Twierdzenie to jest prostym wnioskiem z twierdzenia K48, ale musimy jeszcze pokazać, że $gcd(\mathbb{n}(m),m)=1.$ Przypuśćmy, że $p_k|\mathbb{n}(m)$ dla pewnego $1⩽k⩽s.$ Ponieważ $\mathbb{n}(m)$ jest liczbą pierwszą, to musi być $\mathbb{n}(m)=p_k$, ale wtedy

$\mathbb{n}(p_k)<p_k=\mathbb{n}(m)⩽\mathbb{n}(p_k)$

Otrzymana sprzeczność dowodzi, że $\mathbb{n}(m)$ jest względnie pierwsza z każdą z liczb pierwszych $p_i$, gdzie $1⩽i⩽s.$ Co kończy dowód.
□

Twierdzenie K50
Niech $m⩾3$ będzie liczbą nieparzystą, a $\mathbb{n}(m)$ jest najmniejszą liczbą niekwadratową modulo $m.$ Prawdziwe są oszacowania

$\mathbb{n}(m)<\sqrt{m}+\frac{1}{2}\text{dla }m⩾3$

$\mathbb{n}(m)⩽1.1\cdot m^{1/4}\log m\text{dla }m⩾5$

Dowód

Niech $p$ będzie dzielnikiem pierwszym liczby $m$ takim, że $\mathbb{n}(m)=\mathbb{n}(p)$ (z twierdzenia K48 wiemy, że taki dzielnik istnieje). Jeżeli prawdziwe jest oszacowanie $\mathbb{n}(p)<F(p)$, gdzie $F(x)$ jest funkcją rosnącą, to

$\mathbb{n}(m)=\mathbb{n}(p)<F(p)⩽F(m)$

Podane w twierdzeniu oszacowania wynikają natychmiast z twierdzeń K27 i K28.
□

Uwaga K51
Liczby $\mathbb{n}(m)$ są zaskakująco małe. Średnia wartość $\mathbb{n}=\mathbb{n}(m)$ wynosi

$\underset{x\to \mathrm{\infty }}{lim}\frac{1}{x}\sum _{m⩽x}\mathbb{n}(m)=2+\sum _{k=3}^{\mathrm{\infty }}\frac{p_k-1}{p_1\cdot \dots \cdot p_{k-1}}=2.920050977\dots$

C. Najmniejsze dodatnie liczby niekwadratowe $a$ takie, że ${\left(\frac{a}{m}\right)}_J=-1$

Przykład K52
W tabeli przedstawiliśmy najmniejsze liczby niekwadratowe modulo $p$, najmniejsze liczby niekwadratowe modulo $m$ i najmniejsze dodatnie liczby niekwadratowe $a$ takie, że ${\left(\frac{a}{m}\right)}_J=-1$.

$\mathit{m}$	$3$	$5$	$7$	$9$	$11$	$13$	$15$	$17$	$19$	$21$	$23$	$25$	$27$	$29$	$31$	$33$	$35$	$37$	$39$	$41$	$43$	$45$	$47$	$49$	$51$
$\mathbb{n}\mathbf{(}\mathit{p}\mathbf{)}$	$2$	$2$	$3$	$-$	$2$	$2$	$-$	$3$	$2$	$-$	$5$	$-$	$-$	$2$	$3$	$-$	$-$	$2$	$-$	$3$	$2$	$-$	$5$	$-$	$-$
$\mathbb{n}\mathbf{(}\mathit{m}\mathbf{)}$	$2$	$2$	$3$	$2$	$2$	$2$	$2$	$3$	$2$	$2$	$5$	$2$	$2$	$2$	$3$	$2$	$2$	$2$	$2$	$3$	$2$	$2$	$5$	$3$	$2$
$\mathit{c}\mathbf{(}\mathit{m}\mathbf{)}$	$2$	$2$	$3$	$-$	$2$	$2$	$7$	$3$	$2$	$2$	$5$	$-$	$2$	$2$	$3$	$5$	$2$	$2$	$7$	$3$	$2$	$2$	$5$	$-$	$2$

Uwaga K53
Do wyszukiwania liczb $c=c(m)$ Czytelnik może wykorzystać prostą funkcję napisaną w PARI/GP

C(m) = 
{
if( m%2 == 0, return(0) );
if( issquare(m), return(0) );
forprime(p = 2, m, if( jacobi(p, m) == -1, return(p) ));
}

Uwaga K54
Najmniejsze dodatnie liczby niekwadratowe $a$ takie, że ${\left(\frac{a}{m}\right)}_J=-1$ oznaczyliśmy jako $c(m)$. Zauważmy, że są to liczby inne od $\mathbb{n}(p)$ i $\mathbb{n}(m)$. Wystarczy zwrócić uwagę na występujące w tabeli liczby $\mathbb{n}(p)$, $\mathbb{n}(m)$ i $c(m)$ dla $m=15,33,39$. Różnice wynikają z innej definicji liczb $c(m)$ – jeżeli liczba $a$ jest liczbą niekwadratową modulo $m$, to symbol Jacobiego ${\left(\frac{a}{m}\right)}_J$ nie musi być równy $-1$. I tak czasami bywa, co bardzo dobrze pokazuje powyższa tabela.

Ponieważ $c(m)$ nie zawsze będzie najmniejszą liczbą kwadratową modulo $m$, to mamy natychmiast oszacowanie: $c(m)⩾\mathbb{n}(m)$ (poza przypadkami, gdy $m=n^2$).

Dla $c(m)$ nie są prawdziwe oszacowania podane w twierdzeniu K27. Łatwo zauważamy, że

$c=c(15)=7>\sqrt{15}+\frac{1}{2}\approx 4.37$

$c=c(39)=7>\sqrt{39}+\frac{1}{2}\approx 6.74$

$c=c(105)=11>\sqrt{105}+\frac{1}{2}\approx 10.75$

$c=c(231)=17>\sqrt{231}+\frac{1}{2}\approx 15.7$

Nie ma więcej takich przypadków dla $m<{10}^9$.

Twierdzenie K55
Niech $c,m\in {\mathbb{Z}}_{+}$ i niech $m⩾3$ będzie liczbą nieparzystą, a $c$ będzie najmniejszą liczbą taką, że ${\left(\frac{c}{m}\right)}_J=-1$. Liczba $c$ musi być liczbą pierwszą.

Dowód

Przypuśćmy, że $c=ab$ jest liczbą złożoną, gdzie $1<a,b<c$. Mamy

$-1={\left(\frac{c}{m}\right)}_J={\left(\frac{ab}{m}\right)}_J={\left(\frac{a}{m}\right)}_J$${\left(\frac{b}{m}\right)}_J$

Zatem jeden z czynników po prawej stronie musi być równy $-1$ wbrew definicji liczby $c$.
□

Liczby pierwsze postaci $x^2+n{y}^2$

Przykład K56
Przedstawiamy wszystkie rozkłady liczb naturalnych nie większych od $85$ na sumę postaci $x^2+y^2$, gdzie $x,y\in {\mathbb{N}}_0$. Rozkłady różniące się jedynie kolejnością liczb $x,y$ nie zostały uwzględnione.

$\mathit{n}$	$1$	$2$	$4$	$5$	$8$	$9$	$10$	$13$	$16$	$17$	$18$	$20$	$25$	$26$	$29$	$32$	$34$	$36$	$37$	$40$	$41$	$45$	$49$	$50$	$52$	$53$	$58$	$61$	$64$	$65$	$68$	$72$	$73$	$74$	$80$	$81$	$82$	$85$
$\mathit{x}\mathbf{,}\mathit{y}$	$1,0$	$1,1$	$2,0$	$2,1$	$2,2$	$3,0$	$3,1$	$3,2$	$4,0$	$4,1$	$3,3$	$4,2$	$5,0$	$5,1$	$5,2$	$4,4$	$5,3$	$6,0$	$6,1$	$6,2$	$5,4$	$6,3$	$7,0$	$7,1$	$6,4$	$7,2$	$7,3$	$6,5$	$8,0$	$8,1$	$8,2$	$6,6$	$8,3$	$7,5$	$8,4$	$9,0$	$9,1$	$9,2$
$\mathit{x}\mathbf{,}\mathit{y}$	$$	$$	$$	$$	$$	$$	$$	$$	$$	$$	$$	$$	$4,3$	$$	$$	$$	$$	$$	$$	$$	$$	$$	$$	$5,5$	$$	$$	$$	$$	$$	$7,4$	$$	$$	$$	$$	$$	$$	$$	$7,6$

Zauważmy, że liczba złożona $21$ nie ma rozkładu na sumę kwadratów, a liczba złożona $65$ ma dwa takie rozkłady. Obie liczby są postaci $4k+1$.

Przykład K57
Przedstawiamy wszystkie rozkłady liczb naturalnych nie większych od $73$ na sumę postaci $x^2+2y^2$, gdzie $x,y\in {\mathbb{N}}_0$.

$\mathit{n}$	$1$	$2$	$3$	$4$	$6$	$8$	$9$	$11$	$12$	$16$	$17$	$18$	$19$	$22$	$24$	$25$	$27$	$32$	$33$	$34$	$36$	$38$	$41$	$43$	$44$	$48$	$49$	$50$	$51$	$54$	$57$	$59$	$64$	$66$	$67$	$68$	$72$	$73$
$\mathit{x}\mathbf{,}\mathit{y}$	$1,0$	$0,1$	$1,1$	$2,0$	$2,1$	$0,2$	$3,0$	$3,1$	$2,2$	$4,0$	$3,2$	$4,1$	$1,3$	$2,3$	$4,2$	$5,0$	$5,1$	$0,4$	$5,2$	$4,3$	$6,0$	$6,1$	$3,4$	$5,3$	$6,2$	$4,4$	$7,0$	$0,5$	$7,1$	$6,3$	$7,2$	$3,5$	$8,0$	$8,1$	$7,3$	$6,4$	$8,2$	$1,6$
$\mathit{x}\mathbf{,}\mathit{y}$	$$	$$	$$	$$	$$	$$	$1,2$	$$	$$	$$	$$	$0,3$	$$	$$	$$	$$	$3,3$	$$	$1,4$	$$	$2,4$	$$	$$	$$	$$	$$	$$	$$	$1,5$	$2,5$	$5,4$	$$	$$	$4,5$	$$	$$	$0,6$	$$

Zauważmy, że liczba złożona $65$ nie ma rozkładu na sumę postaci $x^2+2y^2$, a liczba złożona $33$ ma dwa takie rozkłady. Obie liczby są postaci $8k+1$.

Zauważmy też, że liczba złożona $35$ nie ma rozkładu na sumę postaci $x^2+2y^2$, a liczba złożona $27$ ma dwa takie rozkłady. Obie liczby są postaci $8k+3$.

Przykład K58
Przedstawiamy wszystkie rozkłady liczb naturalnych nie większych od $103$ na sumę postaci $x^2+3y^2$, gdzie $x,y\in {\mathbb{N}}_0$.

$\mathit{n}$	$1$	$3$	$4$	$7$	$9$	$12$	$13$	$16$	$19$	$21$	$25$	$27$	$28$	$31$	$36$	$37$	$39$	$43$	$48$	$49$	$52$	$57$	$61$	$63$	$64$	$67$	$73$	$75$	$76$	$79$	$81$	$84$	$91$	$93$	$97$	$100$	$103$
$\mathit{x}\mathbf{,}\mathit{y}$	$1,0$	$0,1$	$2,0$	$2,1$	$3,0$	$3,1$	$1,2$	$4,0$	$4,1$	$3,2$	$5,0$	$0,3$	$5,1$	$2,3$	$6,0$	$5,2$	$6,1$	$4,3$	$6,2$	$7,0$	$7,1$	$3,4$	$7,2$	$6,3$	$8,0$	$8,1$	$5,4$	$0,5$	$8,2$	$2,5$	$9,0$	$9,1$	$8,3$	$9,2$	$7,4$	$10,0$	$10,1$
$\mathit{x}\mathbf{,}\mathit{y}$	$$	$$	$1,1$	$$	$$	$0,2$	$$	$2,2$	$$	$$	$$	$$	$4,2$	$$	$3,3$	$$	$$	$$	$0,4$	$1,4$	$5,3$	$$	$$	$$	$4,4$	$$	$$	$$	$7,3$	$$	$$	$6,4$	$4,5$	$$	$$	$5,5$	$$
$\mathit{x}\mathbf{,}\mathit{y}$	$$	$$	$$	$$	$$	$$	$$	$$	$$	$$	$$	$$	$1,3$	$$	$$	$$	$$	$$	$$	$$	$2,4$	$$	$$	$$	$$	$$	$$	$$	$1,5$	$$	$$	$3,5$	$$	$$	$$	$$	$$

Zauważmy, że liczba złożona $55$ nie ma rozkładu na sumę postaci $x^2+3y^2$, a liczba złożona $91$ ma dwa takie rozkłady. Obie liczby są postaci $6k+1$.

Twierdzenie K59
Jeżeli liczba nieparzysta postaci $Q=x^2+n{y}^2$, gdzie $n\in \{1,2,3\}$, ma dwa różne takie przedstawienia w liczbach całkowitych dodatnich, to jest liczbą złożoną.

Dowód

W dowodzie wyróżniliśmy miejsca, które wymagają oddzielnej analizy ze względu na wartość liczby $n$.

Niech

$Q=x^2+n{y}^2=a^2+n{b}^2$

$\mathit{n}\mathbf{=}\mathbf{1}$

Z założenia $Q$ jest liczbą nieparzystą, zatem liczby występujące w rozkładach $x^2+y^2=a^2+b^2$ muszą mieć przeciwną parzystość. Nie zmniejszając ogólności, możemy założyć, że liczby $x,a$ są nieparzyste, a liczby $y,b$ parzyste.

$\mathit{n}\mathbf{=}\mathbf{2}$

Z założenia $Q$ jest liczbą nieparzystą, zatem liczby $x,a$ występująca w rozkładach $x^2+2y^2=a^2+2b^2$ muszą być nieparzyste. Pokażemy, że liczby $y,b$ muszą mieć taką samą parzystość. Przypuśćmy, że $y$ jest parzysta, a $b$ nieparzysta, wtedy modulo $4$ dostajemy

$1+2\cdot 0\equiv 1+2\cdot 1(\mathrm{mod}4)$

Co jest niemożliwe.

$\mathit{n}\mathbf{=}\mathbf{3}$

Z założenia $Q$ jest liczbą nieparzystą, zatem liczby występujące w rozkładach $x^2+3y^2=a^2+3b^2$ muszą mieć przeciwną parzystość. Pokażemy, że liczby $x,a$ muszą mieć taką samą parzystość. Gdyby liczba $x$ była nieparzysta, a liczba $a$ parzysta, to modulo $4$ mielibyśmy

$1+3\cdot 0\equiv 0+3\cdot 1(\mathrm{mod}4)$

Co jest niemożliwe.

Z powyższego zestawienia wynika, że liczby $x,a$ i liczby $y,b$ mają taką samą parzystość. Mamy

$x^2-a^2=n(b^2-y^2)$

$(x-a)(x+a)=n(b-y)(b+y)$

Niech $f=gcd(x-a,b-y)$, zatem $f$ jest liczbą parzystą i

$x-a=fr,b-y=fs,gcd(r,s)=1$

Czyli

$r(x+a)=ns(y+b)$

ale liczby $r,s$ są względnie pierwsze, zatem $s\mid (x+a)$ i musi być

$x+a=ks⟹n(y+b)=kr$

Gdyby $k$ było liczbą nieparzystą, to liczby $r,s$ musiałyby być parzyste, co jest niemożliwe, bo $gcd(r,s)=1$. Zatem $k$ jest liczbą parzystą i $2s\mid (x+a)$, czyli możemy pokazać więcej. Musi być

$x+a=2ls⟹n(y+b)=2lr$

W przypadku gdy $n=2$ lub $n=3$, zauważmy, że $n\mid l$ lub $n\mid r$.

Łatwo otrzymujemy

$x=\frac{1}{2}(2ls+fr)$

$y=\frac{1}{2n}(2lr-nfs)$

Ostatecznie

$Q=x^2+n{y}^2$

$={[\frac{1}{2}(2ls+fr)]}^2+n{[\frac{1}{2n}(2lr-nfs)]}^2$

$=\frac{1}{4n}[n(2ls+fr{)}^2+(2lr-nfs{)}^2]$

$=\frac{1}{4n}[n(2ls{)}^2+n(fr{)}^2+(2lr{)}^2+(nfs{)}^2]$

$=\frac{1}{4n}[(2l{)}^2+n{f}^2](r^2+n{s}^2)$

$\mathit{n}\mathbf{=}\mathbf{1}$

$Q=\frac{1}{4}[(2l{)}^2+f^2](r^2+s^2)=[l^2+{\left(\frac{f}{2}\right)}^2](r^2+s^2)$

$\mathit{n}\mathbf{=}\mathbf{2}\mathbf{,}\mathbf{3}$

W zależności od tego, która z liczb $l,r$ jest podzielna przez $n$, możemy napisać

$Q=\frac{1}{4n}[(2l{)}^2+n{f}^2](r^2+n{s}^2)=\left[\frac{(2l{)}^2+n{f}^2}{4n}\right](r^2+n{s}^2)=\left[\frac{(2l{)}^2+n{f}^2}{4}\right]\left(\frac{r^2+n{s}^2}{n}\right)$

Co kończy dowód.
□

Uwaga K60
Zauważmy, że iloczyn liczb postaci $x^2+n{y}^2$ jest liczbą tej samej postaci.

$(a^2+n{b}^2)(x^2+n{y}^2)=(ax+nby{)}^2+n(ay-bx{)}^2$

$=(ax-nby{)}^2+n(ay+bx{)}^2$

Twierdzenie K61
Niech $x,y,a,b\in \mathbb{Z}$ i $n\in \{1,2,3\}$. Jeżeli liczba parzysta $Q=x^2+n{y}^2$, to $Q=2^{\alpha }R$, gdzie $R=a^2+n{b}^2$ jest liczbą nieparzystą.

Dowód

W szczególnym przypadku, gdy $R=1$, mamy $R=1^2+n\cdot 0^2$.

Dowód sprowadza się do podania wzorów, które pozwalają obniżyć wykładnik, z jakim liczba $2$ występuje w rozwinięciu na czynniki pierwsze liczby $Q$. Zauważmy, że wynik jest zawsze liczbą, której postać jest taka sama, jak postać liczby $Q$. Stosując te wzory odpowiednią ilość razy, otrzymujmy rozkład $Q=2^{\alpha }R$, gdzie $R$ jest liczbą nieparzystą postaci $a^2+n{b}^2$.

1. $\mathit{Q}\mathbf{=}{\mathit{x}}^{\mathbf{2}}\mathbf{+}{\mathit{y}}^{\mathbf{2}}$

a) jeżeli liczby $x,y$ są parzyste, to $\frac{Q}{4}={\left(\frac{x}{2}\right)}^2+{\left(\frac{y}{2}\right)}^2$

b) jeżeli liczby $x,y$ są nieparzyste, to $\frac{Q}{2}={\left(\frac{x+y}{2}\right)}^2+{\left(\frac{x-y}{2}\right)}^2$

2. $\mathit{Q}\mathbf{=}{\mathit{x}}^{\mathbf{2}}\mathbf{+}\mathbf{2}{\mathit{y}}^{\mathbf{2}}$

a) jeżeli liczby $x,y$ są parzyste, to $\frac{Q}{4}={\left(\frac{x}{2}\right)}^2+2{\left(\frac{y}{2}\right)}^2$

b) jeżeli liczba $x$ jest parzysta, a $y$ nieparzysta, to $\frac{Q}{2}=y^2+2{\left(\frac{x}{2}\right)}^2$

3. $\mathit{Q}\mathbf{=}{\mathit{x}}^{\mathbf{2}}\mathbf{+}\mathbf{3}{\mathit{y}}^{\mathbf{2}}$

a) jeżeli liczby $x,y$ są parzyste, to $\frac{Q}{4}={\left(\frac{x}{2}\right)}^2+3{\left(\frac{y}{2}\right)}^2$

b) jeżeli liczby $x,y$ są nieparzyste i $4\mid (x+y)$, to $\frac{Q}{4}={\left(\frac{x-3y}{4}\right)}^2+3{\left(\frac{x+y}{4}\right)}^2$

c) jeżeli liczby $x,y$ są nieparzyste i $4\mid (x-y)$, to $\frac{Q}{4}={\left(\frac{x+3y}{4}\right)}^2+3{\left(\frac{x-y}{4}\right)}^2$

Co należało pokazać.
□

Twierdzenie K62
Liczba pierwsza $p⩾3$ jest postaci

(a)  $4k+1$

(b)  $8k+1$ lub $8k+3$

(c)  $6k+1$

wtedy i tylko wtedy, gdy istnieje dokładnie jedna para liczb całkowitych dodatnich $x,y$, że

(a)  $p=x^2+y^2$

(b)  $p=x^2+2y^2$

(c)  $p=x^2+3y^2$

Dowód

$⟸$

Niech $n=1,2,3$. Z założenia liczba pierwsza $p⩾3$ może być przedstawiona w postaci $p=x_0^2+n{y}_0^2$, gdzie $x_0,y_0$ są liczbami takimi, że $1⩽x_0,y_0<p$. Zatem $p\nmid x_0$ i $p\nmid y_0$, a rozpatrując równanie $p=x_0^2+n{y}_0^2$ modulo $p$ dostajemy

$x_0^2+n{y}_0^2\equiv 0(\mathrm{mod}p)$

Zauważmy, że liczba $x_0$ jest rozwiązaniem kongruencji

$x^2\equiv -n{y}_0^2(\mathrm{mod}p)$

Wynika stąd, że liczba $-n{y}_0^2$ jest liczbą kwadratową modulo $p$. Zatem

${\left(\frac{-n{y}_0^2}{p}\right)}_J={\left(\frac{-n}{p}\right)}_J\cdot {\left(\frac{y_0^2}{p}\right)}_J={\left(\frac{-n}{p}\right)}_J=1$

Z twierdzenia J36 i zadania J40 otrzymujemy natychmiast

(a) jeżeli ${\left(\frac{-1}{p}\right)}_J=1$, to liczba pierwsza $p$ musi być postaci $4k+1$

(b) jeżeli ${\left(\frac{-2}{p}\right)}_J=1$, to liczba pierwsza $p$ musi być postaci $8k+1$ lub $8k+3$

(c) jeżeli ${\left(\frac{-3}{p}\right)}_J=1$, to liczba pierwsza $p$ musi być postaci $6k+1$

Co należało pokazać.

$⟹$

A. Istnienie rozwiązania kongruencji ${\mathit{x}}^{\mathbf{2}}\mathbf{+}\mathit{n}{\mathit{y}}^{\mathbf{2}}\mathbf{\equiv }\mathbf{0}\mathbf{(}\mathrm{mod}\mathit{p}\mathbf{)}$

Z założenia liczba pierwsza $p⩾3$ jest postaci

(a)  $4k+1$

(b)  $8k+1$ lub $8k+3$

(c)  $6k+1$

Wynika stąd, że dla (a) $n=1$, (b) $n=2$, (c) $n=3$ mamy

${\left(\frac{-n}{p}\right)}_J=1$

(zobacz J36 i J40) i liczba $-n$ jest liczbą kwadratową modulo $p$. Zatem kongruencja

$x^2\equiv -n(\mathrm{mod}p)$

ma rozwiązanie, czyli istnieje taka liczba $k$, że

$k^2+n\equiv 0(\mathrm{mod}p)$

Zauważmy, że liczby $x_0=k$ i $y_0=1$ są szczególnymi przypadkami rozwiązania kongruencji

$x^2+n{y}^2\equiv 0(\mathrm{mod}p)$

W przypadku (a), korzystając z twierdzenia Wilsona (zobacz J18), liczbę $x_0$ możemy jawnie wypisać: $x_0=\left(\frac{p-1}{2}\right)!$

B. Zmniejszenie rozwiązania początkowego

Niech liczby $x_0,y_0$ takie, że $p\nmid x_0$ i $p\nmid y_0$ spełniają kongruencję

$x_0^2+n{y}_0^2\equiv 0(\mathrm{mod}p)$

Wybierzmy liczby $r,s$ tak, aby były najbliższymi liczbami całkowitymi odpowiednio dla liczb $\frac{x_0}{p}$ i $\frac{y_0}{p}$. Z definicji mamy

$|\frac{x_0}{p}-r|⩽\frac{1}{2}\text{i}|\frac{y_0}{p}-s|⩽\frac{1}{2}$

Zatem

$|x_0-rp|⩽\frac{p}{2}\text{i}|y_0-sp|⩽\frac{p}{2}$

Ponieważ liczby po lewej stronie nierówności są liczbami całkowitymi, to nigdy nie będą równe liczbie $\frac{p}{2}$, gdzie $p$ jest liczbą nieparzystą. Pozwala to wzmocnić wypisane nierówności.

$|x_0-rp|<\frac{p}{2}\text{i}|y_0-sp|<\frac{p}{2}$

Wynika stąd, że dla dowolnego rozwiązania początkowego $x_0,y_0$ możemy wybrać liczby

$x=x_0-rp\text{i}y=y_0-sp$

takie, że $p\nmid x$ oraz $p\nmid y$ i dla których

$0<x^2+n{y}^2<{\left(\frac{p}{2}\right)}^2+n{\left(\frac{p}{2}\right)}^2=\frac{(n+1)p}{4}\cdot p$

Ponieważ modulo $p$ jest $x\equiv x_0$ i $y\equiv y_0$, to liczby $x,y$ spełniają kongruencję

$x^2+n{y}^2\equiv 0(\mathrm{mod}p)$

Zatem wynikające z powyższej kongruencji równanie

$x^2+n{y}^2=mp$

ma rozwiązanie dla liczb

$|x|<\frac{p}{2},|y|<\frac{p}{2},1⩽m<\frac{(n+1)p}{4}$

Pomysł ze zmniejszaniem liczb stanowiących rozwiązanie za chwilę wykorzystamy ponownie i będzie to istotny element dowodu.

C. Metoda nieskończonego schodzenia Fermata

Pomysł dowodu został zaczerpnięty z książki Hardy'ego i Wrighta.

Jeżeli w rozwiązaniu $m=1$, to $p=x^2+n{y}^2$ i twierdzenie jest udowodnione. W przypadku gdy $m>1$ wskażemy sposób postępowania, który pozwoli nam z istniejącego rozwiązania równania

$x^2+n{y}^2=mp$

otrzymać nowe rozwiązanie tej samej postaci

$x_1^2+n{y}_1^2=m_{1}p$

takie, że $1⩽m_1<m$. Powtarzając tę procedurę odpowiednią ilość razy, otrzymamy rozwiązanie $x_k,y_k,m_k$, gdzie $m_k=1$. Istnienie takiej procedury stanowi dowód prawdziwości twierdzenia.

Zauważmy, że podział na parzyste i nieparzyste liczby $m$ jest konieczny tylko w przypadku gdy $n=3$. W pozostałych przypadkach nie musimy wzmacniać nierówności, aby prawdziwe było oszacowanie $1⩽m_1<m$.

Przypadek, gdy $\mathit{m}\mathbf{>}\mathbf{1}$ jest liczbą parzystą

Jeżeli $m>1$ jest liczbą parzystą, to z twierdzenia K61 wiemy, że liczba $x^2+n{y}^2$ może być zapisana w postaci

$x^2+n{y}^2=2^{\alpha }(x_1^2+n{y}_1^2)$

gdzie $x_1^2+n{y}_1^2$ jest liczbą nieparzystą. Wystarczy położyć $m_1=\frac{m}{2^{\alpha }}$, aby z istniejącego rozwiązania otrzymać nowe rozwiązanie tej samej postaci

$x_1^2+n{y}_1^2=m_{1}p$

gdzie $m_1$ jest liczbą nieparzystą i $1⩽m_1<m$.

Przypadek, gdy $\mathit{m}\mathbf{>}\mathbf{1}$ jest liczbą nieparzystą

Niech liczby $r,s$ będą liczbami całkowitymi najbliższymi liczbom $\frac{x}{m}$ i $\frac{y}{m}$. Z definicji mamy

$|\frac{x}{m}-r|⩽\frac{1}{2}\text{i}|\frac{y}{m}-s|⩽\frac{1}{2}$

Zatem

$|x-rm|⩽\frac{m}{2}\text{i}|y-sm|⩽\frac{m}{2}$

Ponieważ liczby po lewej stronie nierówności są liczbami całkowitymi, to nigdy nie będą równe liczbie $\frac{m}{2}$, gdzie $m$ jest liczbą nieparzystą. Pozwala to wzmocnić wypisane nierówności.

$|x-rm|<\frac{m}{2}\text{i}|y-sm|<\frac{m}{2}$

Połóżmy

$a=x-rm\text{i}b=y-sm$

Zauważmy, że liczba $m$ nie może jednocześnie dzielić liczb $x$ i $y$, bo mielibyśmy $m^2\mid (x^2+n{y}^2)$, czyli $m\mid p$, co jest niemożliwe. Zatem przynajmniej jedna z liczb $a,b$ musi być różna od $0$.

Rozpatrując równanie $x^2+n{y}^2=mp$ modulo $m$ i uwzględniając, że

$x\equiv a(\mathrm{mod}m)$

$y\equiv b(\mathrm{mod}m)$

otrzymujemy

$a^2+n{b}^2\equiv 0(\mathrm{mod}m)$

Mamy też oszacowanie

$0<a^2+n{b}^2<{\left(\frac{m}{2}\right)}^2+n\cdot {\left(\frac{m}{2}\right)}^2=\frac{(n+1)m^2}{4}=\frac{(n+1)m}{4}\cdot m$

Wynika stąd, że istnieje taka liczba $m_1$ spełniająca warunek $1⩽m_1<\frac{(n+1)m}{4}$, że

$a^2+n{b}^2=m_{1}m$

Mnożąc stronami powyższe równanie i równanie $x^2+n{y}^2=mp$, otrzymujemy

$m_1{m}^{2}p=(a^2+n{b}^2)(x^2+n{y}^2)$

$=(ax+nby{)}^2+n(ay-bx{)}^2$

(zobacz K60). Zauważmy teraz, że

$ax+nby=(x-rm)x+n(y-sm)y$

$=x^2-rmx+n{y}^2-nsmy$

$=m(p-rx-nsy)$

$=m{x}_1$

$ay-bx=(x-rm)y-(y-sm)x$

$=xy-rmy-yx+smx$

$=m(sx-ry)$

$=m{y}_1$

Gdzie oznaczyliśmy

$x_1=p-rx-nsy$

$y_1=sx-ry$

Wynika stąd, że

$m_1{m}^{2}p=(m{x}_1{)}^2+n(m{y}_1{)}^2$

Zatem

$x_1^2+n{y}_1^2=m_{1}p$

gdzie

$1⩽m_1<\frac{(n+1)m}{4}$

Czyli powtarzając odpowiednią ilość razy opisaną powyżej procedurę, otrzymamy $m_k=1$.

D. Jednoznaczność rozkładu

Z założenia $p$ jest liczbą pierwszą, zatem jednoznaczność rozkładu wynika z twierdzenia K59. Co kończy dowód.
□

Uwaga K63
Udowodnione wyżej twierdzenie można wykorzystać do znalezienia rozkładu liczby pierwszej $p$ postaci $4k+1$ na sumę dwóch kwadratów. Dla dużych liczb pierwszych funkcja działa wolno, bo dużo czasu zajmuje obliczanie silni.

Pokaż kod

SumOfTwoSquares(p) = 
{
local(m, r, s, x, y, x1, y1);
if( p%4 <> 1 || !isprime(p), return("Error") );
x = 1;
for(k = 2, (p-1)/2, x = (x*k)%p); \\ x = { [(p-1)/2]! } % p
x = x - round(x/p)*p;
y = 1;
m = (x^2 + y^2)/p;
while( m > 1,
       r = round(x/m);
       s = round(y/m);
       x1 = p - r*x - s*y;
       y1 = r*y - s*x;
       x = x1;
       y = y1;
       m = (x^2 + y^2)/p;
     );
return([ abs(x), abs(y), p ]);
}

Zadanie K64
Niech liczby pierwsze $p,q$ będą postaci $4k+1$, a liczba pierwsza $r$ będzie postaci $4k+3$. Pokazać, że

•   liczby $r,pr$ i $r^2$ nie rozkładają się na sumę dwóch kwadratów liczb całkowitych dodatnich
•   liczby $p$, $2p$, $p^2$ i $p{r}^2$ mają jeden rozkład na sumę dwóch kwadratów liczb całkowitych dodatnich
•   liczba $pq$, $p\ne q$ ma dwa rozkłady na sumę dwóch kwadratów liczb całkowitych dodatnich

Rozwiązanie

Punkt 1.

Ponieważ liczby $r$ i $pr$ są postaci $4k+3$, to modulo $4$ mamy

$r,pr\equiv 3(\mathrm{mod}4)$

Suma $x^2+y^2$ musi być liczbą nieparzystą, zatem liczby $x,y$ muszą mieć przeciwną parzystość i modulo $4$ mamy

$x^2+y^2\equiv 1(\mathrm{mod}4)$

Przypuśćmy, że

$r^2=x^2+y^2$

gdzie $x,y\in {\mathbb{Z}}_{+}$. Liczby $x,y$ muszą mieć przeciwną parzystość, zatem $x\ne y$. Z twierdzenia J22 wynika, że liczba $x^2+y^2$ musi mieć dzielnik pierwszy postaci $4k+1$, co w sposób oczywisty jest niemożliwe.

Punkt 2.

W przypadku liczby pierwszej $p$ odpowiedzi udziela twierdzenie K62. Niech $p=x^2+y^2$, mamy

$2p=(x+y{)}^2+(x-y{)}^2$

$p^2=(x^2-y^2{)}^2+(2xy{)}^2$

$p{r}^2=(rx{)}^2+(ry{)}^2$

Punkt 3.

Niech $p=x^2+y^2$ i $q=a^2+b^2$. Ze wzorów podanych w uwadze K60 mamy

$pq=(a^2+b^2)(x^2+y^2)=(ax+by{)}^2+(ay-bx{)}^2$

$=(ax-by{)}^2+(ay+bx{)}^2$

Co należało pokazać.
□

Twierdzenia o istnieniu liczb pierwszych kwadratowych i niekwadratowych modulo

Zadanie K65
Niech $s=\pm 1$. Zbadać podzielność liczby $p-s{a}^2$

• przez $4$, gdy $p=4k+r$, gdzie $r=1,3$
• przez $8$, gdy $p=8k+r$, gdzie $r=1,3,5,7$

Rozwiązanie

Problem sprowadza się do uzyskania odpowiedzi, kiedy kongruencja

$p-s{a}^2\equiv 0(\mathrm{mod}{2}^n)$

gdzie $n=2,3$, ma rozwiązanie. Podstawiając, dostajemy

$2^{n}k+r\equiv s{a}^2(\mathrm{mod}{2}^n)$

$s{a}^2\equiv r(\mathrm{mod}{2}^n)$

$a^2\equiv sr(\mathrm{mod}{2}^n)$

Z twierdzenia J49 wiemy, że aby powyższa kongruencja miała rozwiązanie, musi być $2^n\mid (sr-1)$, co jest możliwe tylko, gdy

$s=\{\begin{array}{ll}1& \text{gdy }r=1\\ -1& \text{gdy }r=3\end{array}$

dla $2^n=4$ i gdy

$s=\{\begin{array}{ll}1& \text{gdy }r=1\\ -1& \text{gdy }r=7\end{array}$

dla $2^n=8$. Dla $2^n=8$ i $r=3,5$ rozpatrywana kongruencja nie ma rozwiązania.
□

Uwaga K66
Poniżej udowodnimy trzy twierdzenia dotyczące istnienia liczb pierwszych, które są liczbami kwadratowymi modulo $p$. Pomysł ujęcia problemu zaczerpnęliśmy z pracy Alexandru Gicy. Zadanie K65 należy traktować jako uzupełnienie do dowodu twierdzenia K67. Z zadania łatwo widzimy, że powiązanie liczby $s$ z postacią liczby pierwszej $p$ nie jest przypadkowe.

Zauważmy, że twierdzenia ograniczają się do liczb pierwszych $p$, ponieważ dla liczb złożonych nieparzystych $m>0$ wynik ${\left(\frac{q}{m}\right)}_J=1$ nie oznacza, że liczba pierwsza $q$ jest liczbą kwadratową modulo $m$.

W tabeli przedstawiamy najmniejsze liczby pierwsze $q$ postaci $4k+1$ kwadratowe modulo $p$.

$\mathit{p}$	$3$	$5$	$7$	$11$	$13$	$17$	$19$	$23$	$29$	$31$	$37$	$41$	$43$	$47$	$53$	$59$	$61$	$67$	$71$	$73$	$79$	$83$	$89$	$97$
$\mathit{q}$	$13$	$29$	$29$	$5$	$17$	$13$	$5$	$13$	$5$	$5$	$41$	$5$	$13$	$17$	$13$	$5$	$5$	$17$	$5$	$37$	$5$	$17$	$5$	$53$

W kolejnej tabeli przedstawiamy najmniejsze liczby pierwsze $q$ postaci $4k+3$ kwadratowe modulo $p$.

$\mathit{p}$	$3$	$5$	$7$	$11$	$13$	$17$	$19$	$23$	$29$	$31$	$37$	$41$	$43$	$47$	$53$	$59$	$61$	$67$	$71$	$73$	$79$	$83$	$89$	$97$
$\mathit{q}$	$7$	$11$	$11$	$3$	$3$	$19$	$7$	$3$	$7$	$7$	$3$	$23$	$11$	$3$	$7$	$3$	$3$	$19$	$3$	$3$	$11$	$3$	$11$	$3$

Twierdzenie K67
Jeżeli $p⩾11$ jest liczbą pierwszą i $p\ne 17$, to istnieje liczba pierwsza $q<p$ postaci $4k+3$ kwadratowa modulo $p$.

Dowód

Niech

$s=\{\begin{array}{ll}1& \text{gdy }p\text{ jest postaci }4k+1\\ -1& \text{gdy }p\text{ jest postaci }4k+3\end{array}$

Dla ustalonych liczb $n$ i $s$ rozważmy liczbę $u(a)=\frac{p-s{a}^2}{2^n}$ taką, że $3⩽u(a)<p$. Jeżeli liczba ta jest postaci $4k+3$, to ma dzielnik pierwszy $q<p$ postaci $4k+3$ (zobacz C21). Zatem możemy napisać $u(a)=tq$, co oznacza, że

$p-s{a}^2=2^{n}u(a)=2^{n}tq$

Czyli

$p\equiv s{a}^2(\mathrm{mod}q)$

i otrzymujemy

${\left(\frac{q}{p}\right)}_J=s\cdot {\left(\frac{p}{q}\right)}_J=s\cdot {\left(\frac{s{a}^2}{q}\right)}_J=s\cdot {\left(\frac{s}{q}\right)}_J\cdot {\left(\frac{a^2}{q}\right)}_J=s\cdot {\left(\frac{s}{q}\right)}_J=1$

Zatem liczba $q<p$ jest liczbą kwadratową modulo $p$.

Pomysł dowodu polega na wskazaniu kilku liczb $u(a_1),\dots ,u(a_r)$ takich, że

$3⩽u(a_1)<\dots <u(a_r)<p$

z których jedna musi być postaci $4k+3$.

Przypadek pierwszy: $\mathit{p}\mathbf{\equiv }\mathbf{3}\mathbf{(}\mathrm{mod}\mathbf{8}\mathbf{)}$

Mamy $s=-1$ i przyjmujemy $n=2$. Rozważmy liczby

$3⩽\frac{p+1}{4}<\frac{p+9}{4}<p$

Oszacowania są jednocześnie spełnione dla $p⩾11$. Z założenia $p=8k+3$, zatem rozpatrywane liczby to $\{2k+1,2k+3\}$. Ponieważ są to dwie kolejne liczby nieparzyste, to jedna z nich jest postaci $4k+3$.

Przypadek drugi: $\mathit{p}\mathbf{\equiv }\mathbf{5}\mathbf{(}\mathrm{mod}\mathbf{8}\mathbf{)}$

Mamy $s=+1$ i przyjmujemy $n=2$. Rozważmy liczby

$3⩽\frac{p-9}{4}<\frac{p-1}{4}<p$

Oszacowania są jednocześnie spełnione dla $p⩾21$. Z założenia $p=8k+5$, zatem rozpatrywane liczby to $\{2k-1,2k+1\}$. Ponieważ są to dwie kolejne liczby nieparzyste, to jedna z nich jest postaci $4k+3$.

Przypadek trzeci: $\mathit{p}\mathbf{\equiv }\mathbf{7}\mathbf{(}\mathrm{mod}\mathbf{8}\mathbf{)}$

Mamy $s=-1$ i przyjmujemy $n=3$. Rozważmy liczby

$3⩽\frac{p+1}{8}<\frac{p+9}{8}<\frac{p+25}{8}<\frac{p+49}{8}<p$

Oszacowania są jednocześnie spełnione dla $p⩾23$. Z założenia $p=8k+7$, zatem rozpatrywane liczby to $\{k+1,k+2,k+4,k+7\}$. Jeżeli $k\equiv r(\mathrm{mod}4)$, to modulo $4$ mamy zbiór $\{r+1,r+2,r,r+3\}$. Zatem jedna z liczb w tym zbiorze jest postaci $4k+3$.

Przypadek czwarty: $\mathit{p}\mathbf{\equiv }\mathbf{1}\mathbf{(}\mathrm{mod}\mathbf{8}\mathbf{)}$

Mamy $s=+1$ i przyjmujemy $n=3$. Rozważmy liczby

$3⩽\frac{p-49}{8}<\frac{p-25}{8}<\frac{p-9}{8}<\frac{p-1}{8}<p$

Oszacowania są jednocześnie spełnione dla $p⩾73$. Z założenia $p=8k+1$, zatem rozpatrywane liczby to $\{k-6,k-3,k-1,k\}$. Jeżeli $k\equiv r(\mathrm{mod}4)$, to modulo $4$ mamy zbiór $\{r+2,r+1,r+3,r\}$. Zatem jedna z liczb w tym zbiorze jest postaci $4k+3$.

Pozostaje sprawdzić twierdzenie dla liczb pierwszych $p<73$. Co kończy dowód.
□

Twierdzenie K68
Jeżeli $p⩾11$ jest liczbą pierwszą postaci $8k+1$ lub $8k+3$, to istnieje liczba pierwsza $q<p$ postaci $4k+1$ kwadratowa modulo $p$.

Dowód

W przypadku, gdy liczba pierwsza $p$ jest postaci $8k+1$ lub $8k+3$, to istnieją takie liczby całkowite dodatnie $x,y$, że $p=x^2+2y^2$ (zobacz K62). Ponieważ z założenia $p⩾11$, to musi być $x\ne y$. Z twierdzenia J22 wynika, że liczba $x^2+y^2$ ma dzielnik pierwszy $q$ postaci $4k+1$. Łatwo widzimy, że $q⩽x^2+y^2<x^2+2y^2=p$.

Modulo $q$ możemy napisać

$x^2+y^2\equiv 0(\mathrm{mod}q)$

Liczba pierwsza $q<p$ nie może dzielić $y$, bo mielibyśmy $q\mid x$, czyli $q\mid p$, co jest niemożliwe. Rozpatrując równość $p=x^2+2y^2$ modulo $q$, dostajemy

$p\equiv y^2(\mathrm{mod}q)$

Wynika stąd natychmiast (zobacz J36 p.9)

${\left(\frac{q}{p}\right)}_J={\left(\frac{p}{q}\right)}_J={\left(\frac{y^2}{q}\right)}_J=1$

Co kończy dowód.
□

Twierdzenie K69
Jeżeli $p⩾19$ jest liczbą pierwszą postaci $12k+7$, to istnieje liczba pierwsza $q<p$ postaci $4k+1$ kwadratowa modulo $p$.

Dowód

Z założenia $p\equiv 1(\mathrm{mod}6)$, zatem istnieją takie liczby $x,y\in {\mathbb{Z}}_{+}$, że $p=x^2+3y^2$ (zobacz K62). Liczby $x,y$ muszą mieć przeciwną parzystość i być względnie pierwsze. Gdyby liczba $x$ była nieparzysta, to modulo $4$ mielibyśmy

$1+3\cdot 0\equiv 3(\mathrm{mod}4)$

Co jest niemożliwe. Zatem $x=2k$, a liczba $y$ musi być nieparzysta. Otrzymujemy

$p=4k^2+3y^2=4(k^2+y^2)-y^2$

Ponieważ $p$ jest liczbą pierwszą, to jedynie w przypadku gdy $k=y=1$ możliwa jest sytuacja, że $k=y$. Mielibyśmy wtedy $p=7$, ale z założenia musi być $p⩾19$. Wynika stąd, że $k\ne y$, zatem liczba $k^2+y^2$ ma dzielnik pierwszy $q$ postaci $4k+1$ (zobacz J22). Oczywiście $q⩽k^2+y^2<4k^2+3y^2=p$.

Modulo $q$ możemy napisać

$k^2+y^2\equiv 0(\mathrm{mod}q)$

Liczba pierwsza $q$ nie może dzielić $y$, bo mielibyśmy $q\mid k$, czyli $q\mid p$, co jest niemożliwe. Rozpatrując równość $p=4(k^2+y^2)-y^2$ modulo $q$, dostajemy

$p\equiv -y^2(\mathrm{mod}q)$

Wynika stąd natychmiast (zobacz J36 p.9 i p.6)

${\left(\frac{q}{p}\right)}_J={\left(\frac{p}{q}\right)}_J={\left(\frac{-y^2}{q}\right)}_J={\left(\frac{-1}{q}\right)}_J\cdot {\left(\frac{y^2}{q}\right)}_J={\left(\frac{-1}{q}\right)}_J=1$

Co kończy dowód.
□

Twierdzenia K68 i K69 można uogólnić na wszystkie liczby pierwsze.
Twierdzenie K70*
Jeżeli $p⩾11$ jest liczbą pierwszą i $p\ne 13,37$, to istnieje liczba pierwsza $q<p$ postaci $4k+1$ kwadratowa modulo $p$.

Uwaga K71
W tabeli przedstawiamy najmniejsze liczby pierwsze $q$ postaci $4k+1$ niekwadratowe modulo $m$.

$\mathit{m}$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$	$13$	$14$	$15$	$16$	$17$	$18$	$19$	$20$	$21$	$22$	$23$	$24$	$25$	$26$	$27$	$28$	$29$	$30$	$31$	$32$	$33$	$34$	$35$	$36$	$37$	$38$	$39$	$40$
$\mathit{q}$	$-$	$5$	$-$	$13$	$5$	$5$	$5$	$5$	$13$	$13$	$5$	$5$	$5$	$13$	$5$	$5$	$5$	$13$	$13$	$5$	$13$	$5$	$5$	$13$	$5$	$5$	$5$	$17$	$13$	$13$	$5$	$5$	$5$	$13$	$5$	$5$	$13$	$5$	$13$

W kolejnej tabeli przedstawiamy najmniejsze liczby pierwsze $q$ postaci $4k+3$ niekwadratowe modulo $m$.

$\mathit{m}$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$	$13$	$14$	$15$	$16$	$17$	$18$	$19$	$20$	$21$	$22$	$23$	$24$	$25$	$26$	$27$	$28$	$29$	$30$	$31$	$32$	$33$	$34$	$35$	$36$	$37$	$38$	$39$	$40$
$\mathit{q}$	$-$	$11$	$3$	$3$	$11$	$3$	$3$	$11$	$3$	$7$	$7$	$7$	$3$	$7$	$3$	$3$	$11$	$3$	$3$	$11$	$7$	$7$	$7$	$3$	$7$	$11$	$3$	$3$	$7$	$3$	$3$	$7$	$3$	$3$	$7$	$19$	$3$	$7$	$3$

Twierdzenie K72
Jeżeli $m⩾7$ jest liczbą całkowitą postaci $4k+3$, to istnieje liczba pierwsza $q<m$ postaci $4k+3$ niekwadratowa modulo $m$.

Dowód

Ponieważ liczba $m-4⩾3$ jest postaci $4k+3$, to ma dzielnik pierwszy $q<m$ postaci $4k+3$ (zobacz C21). Czyli $m-4=kq$ i z twierdzenia J36 p.9 dostajemy

${\left(\frac{q}{m}\right)}_J=-{\left(\frac{m}{q}\right)}_J=-{\left(\frac{kq+4}{q}\right)}_J=-{\left(\frac{4}{q}\right)}_J=-1$

Zatem $q$ jest liczbą niekwadratową modulo $m$. Co należało pokazać.
□

Można też pokazać, że
Twierdzenie K73*
A. Jeżeli $p⩾13$ jest liczbą pierwszą, to istnieje liczba pierwsza $q<p$ postaci $4k+1$ niekwadratowa modulo $p$.

B. Jeżeli $p⩾5$ jest liczbą pierwszą, to istnieje liczba pierwsza $q<p$ postaci $4k+3$ niekwadratowa modulo $p$.

Zauważmy, że twierdzenie K73 można łatwo uogólnić na liczby całkowite dodatnie.
Twierdzenie K74
A. Jeżeli $m⩾6$ jest liczbą całkowitą i $m\ne 10,11$, to istnieje liczba pierwsza $q<m$ postaci $4k+1$ niekwadratowa modulo $m$.

B. Jeżeli $m⩾4$ jest liczbą całkowitą i $m\ne 6,9$, to istnieje liczba pierwsza $q<m$ postaci $4k+3$ niekwadratowa modulo $m$.

Dowód

Punkt B

Rozważmy liczby $m$ postaci $m=2^a{3}^b$.

Jeżeli $3\mid m$, to $11$ jest liczbą niekwadratową modulo $m$, bo ${\left(\frac{11}{3}\right)}_J=-1$ (zobacz J50 i K47).

Jeżeli $3\nmid m$, ale $8\mid m$, to $8\nmid (11-1)$, zatem liczba $11$ jest liczbą niekwadratową modulo $m$ (zobacz J50).

Jeżeli $3\nmid m$ i $8\nmid m$, ale $4\mid m$, to $4\nmid (11-1)$, zatem liczba $11$ jest liczbą niekwadratową modulo $m$ (zobacz J50).

Jeżeli $m=2$, to łatwo zauważamy, że nie istnieją liczby niekwadratowe modulo $2$.

Zbierając:

• jeśli liczba $m⩾12$ nie ma dzielnika pierwszego $p⩾5$, czyli jest postaci $m=2^a{3}^b$, to liczba pierwsza $q=11$ jest mniejsza od $m$, jest postaci $4k+3$ i jest liczbą niekwadratową modulo $m$.
• jeśli liczba $m⩾12$ ma dzielnik pierwszy $p⩾5$, to istnieje liczba pierwsza $q<p⩽m$ taka, że $q$ jest postaci $4k+3$ i jest liczbą niekwadratową modulo $m$ (zobacz K73 i K47).

Pozostaje wypisać dla liczb $3⩽m⩽11$ najmniejsze liczby niekwadratowe, które są liczbami pierwszymi postaci $4k+3$.

for(m = 3, 15, forprimestep(q = 3, 100, 4, if( isQR(q,m) == -1, print(m, "  ", q); break() )))

$\mathit{m}$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$	$13$	$14$	$15$
$\mathit{q}$	$11$	$3$	$3$	$11$	$3$	$3$	$11$	$3$	$7$	$7$	$7$	$3$	$7$

Widzimy, że twierdzenie jest prawdziwe dla $m⩾4$, o ile $m\ne 6,9$.

Punkt A

Rozważmy liczby $m$ postaci $m=2^a{3}^b{5}^c{7}^d{11}^e$.

Jeżeli jedna z liczb $3,5,7,11$ dzieli $m$, to $17$ jest liczbą niekwadratową modulo $m$, bo ${\left(\frac{17}{3}\right)}_J={\left(\frac{17}{5}\right)}_J={\left(\frac{17}{7}\right)}_J={\left(\frac{17}{11}\right)}_J=-1$.

Jeżeli żadna z liczb $3,5,7,11$ nie dzieli $m$, ale $8\mid m$, to $8\nmid (5-1)$, zatem liczba $5$ jest liczbą niekwadratową modulo $m$.

Jeżeli żadna z liczb $3,5,7,11$ nie dzieli $m$ i $8\nmid m$, ale $4\mid m$, to nie istnieją liczby pierwsze postaci $4k+1$ niekwadratowe modulo $m$, bo $4\mid [(4k+1)-1]$

Jeżeli $m=2$, to łatwo zauważamy, że nie istnieją liczby niekwadratowe modulo $2$.

Zbierając:

• jeśli liczba $m⩾18$ nie ma dzielnika pierwszego $p⩾13$, czyli jest postaci $m=2^a{3}^b{5}^c{7}^d{11}^e$, to liczba pierwsza $q=5$ lub $q=17$ jest mniejsza od $m$, jest postaci $4k+1$ i jest liczbą niekwadratową modulo $m$.
• jeśli liczba $m⩾18$ ma dzielnik pierwszy $p⩾13$, to istnieje liczba pierwsza $q<p⩽m$ taka, że $q$ jest postaci $4k+1$ i jest liczbą niekwadratową modulo $m$ (zobacz K73 i K47).

Pozostaje wypisać dla liczb $3⩽m⩽17$ najmniejsze liczby niekwadratowe, które są liczbami pierwszymi postaci $4k+1$.

for(m = 3, 20, forprimestep(q = 1, 100, 4, if( isQR(q,m) == -1, print(m, "  ", q); break() )))

$\mathit{m}$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$	$13$	$14$	$15$	$16$	$17$	$18$	$19$	$20$
$\mathit{q}$	$5$	$-$	$13$	$5$	$5$	$5$	$5$	$13$	$13$	$5$	$5$	$5$	$13$	$5$	$5$	$5$	$13$	$13$

Widzimy, że twierdzenie jest prawdziwe dla $m⩾6$, o ile $m\ne 10,11$.
□

Twierdzenie K75
Jeżeli $p⩾5$ jest liczbą pierwszą, to istnieje liczba pierwsza nieparzysta $q<p$ taka, że ${\left(\frac{p}{q}\right)}_J=-1.$

Dowód

Łatwo sprawdzamy, że

${\left(\frac{5}{3}\right)}_J={\left(\frac{7}{5}\right)}_J={\left(\frac{11}{3}\right)}_J=-1$

(zobacz J36 p.7). Zatem dowód wystarczy przeprowadzić dla $p⩾13$.

A. Liczba pierwsza $\mathit{p}$ jest postaci $\mathbf{4}\mathit{k}\mathbf{+}\mathbf{1}$

Niech liczba $q$ będzie najmniejszą nieparzystą liczbą niekwadratową modulo $p$. Z twierdzenia K31 wiemy, że dla $p⩾5$ liczba $q$ jest liczbą pierwszą i jest mniejsza od $p$. Ponieważ $p\equiv 1(\mathrm{mod}4)$, to z twierdzenia J36 p.9 otrzymujemy natychmiast

${\left(\frac{p}{q}\right)}_J={\left(\frac{q}{p}\right)}_J=-1$

B. Liczba pierwsza $\mathit{p}$ jest postaci $\mathbf{4}\mathit{k}\mathbf{+}\mathbf{3}$

Z twierdzenia K67 wynika, że dla każdej liczby pierwszej $p⩾11$ postaci $4k+3$ istnieje liczba pierwsza $q<p$ taka, że $q$ jest postaci $4k+3$ i jest liczbą kwadratową modulo $p$. Ponieważ $p\equiv q\equiv 3(\mathrm{mod}4)$, to z twierdzenia J36 p.9 otrzymujemy natychmiast

${\left(\frac{p}{q}\right)}_J=-{\left(\frac{q}{p}\right)}_J=-1$

Co kończy dowód.
□

Zadanie K76
Udowodnić twierdzenie K75 w przypadku, gdy liczba pierwsza $p⩾19$ jest postaci $4k+3$, nie korzystając z twierdzenia K67.

Rozwiązanie

Z założenia $p=4k+3$. Liczba $k$ może być postaci $k=3j$, $k=3j+1$ i $k=3j+2$. Odpowiada to liczbom pierwszym postaci $p=12j+3$, $p=12j+7$ i $p=12j+11$.

Ponieważ nie ma liczb pierwszych $p⩾19$ i będących postaci $p=12j+3$, to pozostaje rozważyć przypadki $p=12j+7$ i $p=12j+11$.

A. Liczba pierwsza $\mathit{p}$ jest postaci $\mathbf{12}\mathit{j}\mathbf{+}\mathbf{11}$

Wiemy, że w tym przypadku ${\left(\frac{3}{p}\right)}_J=+1$ (zobacz J41). Mamy

${\left(\frac{p}{3}\right)}_J=-{\left(\frac{3}{p}\right)}_J=-1$

Czyli wystarczy przyjąć $q=3$.

B. Liczba pierwsza $\mathit{p}$ jest postaci $\mathbf{12}\mathit{j}\mathbf{+}\mathbf{7}$

Wiemy, że w tym przypadku ${\left(\frac{-1}{p}\right)}_J={\left(\frac{3}{p}\right)}_J=-1$ (zobacz J36 p.6 oraz J41). Otrzymujemy

${\left(\frac{p}{p-12}\right)}_J=-{\left(\frac{p-12}{p}\right)}_J=-{\left(\frac{-12}{p}\right)}_J=[-{\left(\frac{-1}{p}\right)}_J]\cdot {\left(\frac{2^2}{p}\right)}_J\cdot {\left(\frac{3}{p}\right)}_J={\left(\frac{3}{p}\right)}_J=-1$

Ponieważ liczba $p-12⩾7$ jest nieparzysta, to musi istnieć nieparzysty dzielnik pierwszy $q<p$ liczby $p-12$ taki, że ${\left(\frac{p}{q}\right)}_J=-1$. W przeciwnym razie z twierdzenia J36 p.4 mielibyśmy ${\left(\frac{p}{p-12}\right)}_J=1$. Co kończy dowód.
□