Jacobi記号

1：各因子は $0,\pm1$ のどれかで、因子 $\left(\frac a{p_i}\right)$ が $0$ になるのは $p_i\mid a$ のときに限る。よって積が $0$ になることと、$n$ のある素因数が $a$ を割り切ること、すなわち $\gcd(a,n)>1$ は同値である。2：前半は Legendre 記号の乗法性（Legendre記号 の記事の式「Legendre 記号の計算規則」）を各因子に使えばよく、後半は $mn$ の素因数分解が $m$ と $n$ の素因数分解を並べたものであることによる。3：$a\equiv b\pmod n$ なら各 $p_i$ について $a\equiv b\pmod{p_i}$ で、Legendre 記号は法 $p_i$ の剰余類だけで決まる。4：平方剰余の相互法則 の記事の定理「Jacobi記号の相互法則」である。5：$a\equiv c^2\pmod n$ なら 2・3 により $\left(\frac an\right)=\left(\frac cn\right)^2$ で、1 により $\left(\frac cn\right)=\pm1$ なので値は $1$ である。$\square$

はじめの入力を $(a_0,n_0)$ とする。
正しさ．「いまの $(a,n)$ と $s$ について $s\left(\frac an\right)=\left(\frac{a_0}{n_0}\right)$ で、$n$ は正の奇数」が、手順を進めても保たれることを示す。最初は $s=1$ で成り立つ。手順 2 の置き換えでは prop-jac-basic の 3 により $\left(\frac an\right)$ は変わらない。手順 2 で $a=0$ なら、$n>1$ なので $\gcd(0,n)=n>1$ で、同じ命題の 1 により $\left(\frac0n\right)=0$、すなわち元の値は $0$ であり、出力は正しい。手順 1 で $n=1$ なら $\left(\frac a1\right)=1$ なので元の値は $s$ であり、出力は正しい。
手順 3〜5 では、prop-jac-basic の 2・4 により $\left(\frac an\right)=\left(\frac2n\right)^e\left(\frac{a'}n\right)$ で、$\left(\frac2n\right)=-1$ となるのは $n\equiv\pm3\pmod8$ のときである。$a'$ と $n$ が互いに素なら、同じ命題の 4 により $\left(\frac{a'}n\right)=\epsilon\left(\frac n{a'}\right)$ であり、$\epsilon=(-1)^{\frac{a'-1}2\cdot\frac{n-1}2}$ が $-1$ になるのは $a'\equiv n\equiv3\pmod4$ のときである。$a'$ と $n$ が互いに素でなければ、同じ命題の 1 により $\left(\frac{a'}n\right)=0=\left(\frac n{a'}\right)$ なので、この等式はどちらの符号でも成り立つ。したがって手順 3・4 で符号を直した $s$ について $s\left(\frac n{a'}\right)$ は直す前の $s\left(\frac an\right)$ に等しく、手順 5 の後も性質が保たれる。$a'$ は $1\le a'\le a< n$ を満たす奇数である。
終わること．手順 5 のたびに $n$ は $a'< n$ に置き換わるので、正の奇数 $n$ は真に減り続け、有限回で $n=1$ になるか、手順 2 で $a=0$ になって終わる。
回数．$i$ 回目の繰り返しの後の $n$ を $n_i$ とすると $n_0> n_1> n_2>\cdots$ である。$i\ge1$ について、$i+1$ 回目の繰り返しでは、$a=n_{i-1}$ を $n_i$ で割った余り $r$ に置き換え、$n_{i+1}$ は $r$ の奇数の部分なので $n_{i+1}\le r$ である。$n_i< n_{i-1}$ なので商は $1$ 以上で、$n_{i-1}\ge n_i+r\ge n_i+n_{i+1}> 2n_{i+1}$ である。よって $n_{2j}\le n_0/2^j$ である（$j=0$ では等号）。繰り返しが $k$ 回行われたとき $n_k\ge1$ なので、$k=2j$ なら $1\le n_0/2^j$ から $k=2j\le2\log_2n_0$、$k=2j+1$ なら $1\le n_{2j+1}< n_{2j}\le n_0/2^j$ から $j< \log_2n_0$ で $k< 2\log_2n_0+1$ である。どちらの場合も $k\le2\log_2n_0+1$ である。$\square$

prop-jac-basic の 1・2・3 により、$a\bmod n\mapsto\left(\frac an\right)$ は $(\mathbb{Z}/n\mathbb{Z})^\times$ 上でうまく定まり、値は $\pm1$ で、積を積に移す準同型 $J_n$ である。
1：$n=m^2$ なら、同じ命題の 2 により $\left(\frac an\right)=\left(\frac am\right)^2=1$ である。
2：$n$ が平方数でないので、ある素数 $p$ が $n$ を奇数乗 $p^e$（$e$ は奇数）でちょうど割り切る。$n=p^em$（$p\nmid m$）とおく。法 $p$ の平方非剰余 $b$ がある（平方剰余 の記事の命題「平方剰余はちょうど半分」）。中国剰余定理 により、$a\equiv b\pmod{p^e}$ かつ $a\equiv1\pmod m$ となる整数 $a$ がある。$a$ は $n$ と互いに素で、
$$ \left(\frac an\right)=\left(\frac ap\right)^e\left(\frac am\right)=\left(\frac bp\right)^e\left(\frac 1m\right)=(-1)^e=-1 $$
である（$a\equiv b\pmod p$、$a\equiv1\pmod m$ と同じ命題の 2・3 による）。よって $J_n$ は全射で、その核は指数 $2$ の部分群である（$J_n$ の像 $\{\pm1\}$ と $(\mathbb{Z}/n\mathbb{Z})^\times/\ker J_n$ が同型）。核の元の個数は $\varphi(n)/2$ である。$\square$

部分群であること．$1\in E(n)$ である。$a,b\in E(n)$ なら、prop-jac-basic の 2 により $(ab)^{(n-1)/2}=a^{(n-1)/2}b^{(n-1)/2}\equiv\left(\frac an\right)\left(\frac bn\right)=\left(\frac{ab}n\right)$ なので $ab\in E(n)$ である。有限群の空でない部分集合で積について閉じたものは部分群である（各元の冪が有限個しかないので、逆元もその冪として含まれる）。
素数の場合．上に述べた Euler の規準による。
合成数の場合．$E(n)=(\mathbb{Z}/n\mathbb{Z})^\times$ と仮定して矛盾を導く。2 つの場合に分ける。
(i) ある素数 $p$ について $p^2\mid n$ のとき。$g:=1+n/p$ とおく。$p\mid n/p$ なので $(n/p)^2=n\cdot(n/p^2)$ は $n$ の倍数であり、二項定理で
$$ g^p=1+p\cdot\frac np+\sum_{j\ge2}\binom pj\Bigl(\frac np\Bigr)^j\equiv1\pmod n $$
である。よって $g$ は $n$ と互いに素で、$g\not\equiv1\pmod n$ だから、$(\mathbb{Z}/n\mathbb{Z})^\times$ での位数はちょうど素数 $p$ である。仮定から $g\in E(n)$ なので、prop-jac-basic の 1 より $\left(\frac gn\right)=\pm1$ で、$g^{n-1}=\bigl(g^{(n-1)/2}\bigr)^2\equiv\left(\frac gn\right)^2=1$ である。位数 $p$ の元の冪が $1$ になる指数は $p$ の倍数なので $p\mid n-1$ となるが、$p\mid n$ なので $p\mid1$ となり矛盾する。
(ii) $n$ が平方因子をもたないとき。$n$ は合成数なので、素数 $p$ と $1$ より大きい奇数 $m$ で $n=pm$、$p\nmid m$ と書ける。法 $p$ の平方非剰余 $b$ をとり、中国剰余定理 で $a\equiv b\pmod p$、$a\equiv1\pmod m$ となる $a$ をとる。prop-jac-half の証明と同じ計算で $\left(\frac an\right)=\left(\frac bp\right)\left(\frac1m\right)=-1$ である。仮定から $a^{(n-1)/2}\equiv-1\pmod n$ であり、法 $m$ で見ると $a\equiv1$ なので $1\equiv-1\pmod m$、すなわち $m\mid2$ となるが、$m$ は $1$ より大きい奇数なので矛盾する。
どちらの場合も矛盾なので $E(n)$ は真の部分群である。Lagrangeの定理 により $\lvert E(n)\rvert$ は $\varphi(n)$ の約数で、$\varphi(n)$ より小さいので $\varphi(n)/2$ 以下である。$\square$