平方数

第 1 の等式は展開すればよい。$x=n^2$（$n\ge1$）とすると $\sqrt{x}=n$ であり、$x$ の直前の平方数は $(n-1)^2=x-2n+1< x-2n+2$、直後の平方数は $(n+1)^2=x+2n+1>x+2n$ である。よって区間 $[x-2n+2,\ x+2n]$ に含まれる平方数は $x$ だけである。$\square$

指数がすべて偶数なら $m:=p_1^{e_1/2}\cdots p_r^{e_r/2}$ は整数で $n=m^2$ である。逆に $n=m^2$（$m\ge1$）とし、$m=p_1^{f_1}\cdots p_r^{f_r}$（$f_i\ge0$）と書くと $n=p_1^{2f_1}\cdots p_r^{2f_r}$ である。素因数分解の一意性により $e_i=2f_i$ であり、すべて偶数である。$\square$

$n$ が平方数なら $\sqrt{n}$ は非負整数であり有理数である。逆に $\sqrt{n}=a/b$（$a\ge0$、$b\ge1$ は整数）とすると $nb^2=a^2$ である。$n=0$ なら平方数である。$n\ge1$ のとき $a\ge1$ であり、素数 $p$ に対して正の整数 $k$ の素因数分解における $p$ の指数を $v_p(k)$（p進付値）と書くと、素因数分解の一意性により $v_p(n)+2v_p(b)=2v_p(a)$ となる。よって $v_p(n)=2(v_p(a)-v_p(b))$ はすべての $p$ について偶数であり、prop-square-number-exponents により $n$ は平方数である。$\square$

$n=2k$ なら $n^2=4k^2\equiv0\pmod 4$ であり、$n=2k+1$ なら $n^2=4k(k+1)+1$ である。$k(k+1)$ は連続する 2 整数の積なので偶数であり、$n^2\equiv1\pmod 8$、特に $n^2\equiv1\pmod 4$ である。偶数 $n=2k$ については $n^2=4k^2$ であり、$k$ が偶数なら $8\mid n^2$、奇数なら $k^2\equiv1\pmod 8$ より $n^2\equiv4\pmod 8$ である。$\square$

prop-square-number-mod-4-8 により平方数の法 $4$ での剰余は $0,1$ に限るので、二つの和の剰余は $0,1,2$ に限る。平方数の法 $8$ での剰余は $0,1,4$ に限るので、三つの和の剰余は $\{a+b+c\mid a,b,c\in\{0,1,4\}\}$ を $8$ で割った余り、すなわち $0,1,2,3,4,5,6$ に限り、$7$ は現れない。$\square$

$n^2$ の $p$ での余りは $n$ の $p$ での余りだけで決まるので、$n=0,1,\dots,p-1$ について $n^2\bmod p$ を調べればよい。$n=0$ は余り $0$ を与え、$1\le n\le p-1$ のとき $p\nmid n^2$ なので余りは $0$ でない。$1\le x,y\le p-1$ について $x^2\equiv y^2\pmod p$ は $p\mid(x-y)(x+y)$ と同値であり、$p$ が素数なので $x\equiv y$ または $x\equiv-y\pmod p$ と同値である。$p$ が奇数なので $y\not\equiv-y\pmod p$ であり、$y$ と $p-y$ は $\{1,\dots,p-1\}$ の相異なる元である。よって $x\mapsto x^2\bmod p$ は $\{1,\dots,p-1\}$ から $\{1,\dots,p-1\}$ への 2 対 1 の写像であり、その像はちょうど $(p-1)/2$ 個からなる。$0$ を合わせて $(p+1)/2$ 個である。$\square$