原始根

$d=\operatorname{ord}_n(a)$ とおく。元の位数 の記事の命題「生成する部分群の位数」により、$[a]$ が生成する部分群は $\{[a]^0,[a]^1,\dots,[a]^{d-1}\}$ であり、この $d$ 個は相異なる。
1 ⇒ 2：$d=\varphi(n)$ なら $[a]^0,\dots,[a]^{\varphi(n)-1}$ は相異なる $\varphi(n)$ 個の元であり、$(\mathbb{Z}/n\mathbb{Z})^{\times}$ の元はちょうど $\varphi(n)$ 個なので、すべての元を一度ずつ表す。
2 ⇒ 3：2 の $\varphi(n)$ 個の元はすべて $[a]$ の冪なので、$[a]$ が生成する部分群が全体に一致する。
3 ⇒ 1：$[a]$ が生成する部分群の位数は $d$ であり、それが全体なら $d=\varphi(n)$ である。

1 は、群 $(\mathbb{Z}/n\mathbb{Z})^{\times}$ の元 $[a]$ に 元の位数 の記事の命題「位数と冪の整除関係」を適用したものである。2 は、Eulerの定理(整数論) の $a^{\varphi(n)}\equiv1\pmod n$ に 1 を適用すれば得られる。

$d=\operatorname{ord}_n(g)$ とおくと、prop-primitive-root-order-divides により $d\mid\varphi(n)$ である。$g$ が原始根なら $d=\varphi(n)$ であり、$\varphi(n)/q<\varphi(n)=d$ は $d$ の倍数でないので、prop-primitive-root-order-divides の 1 により $g^{\varphi(n)/q}\not\equiv1$ である。
逆に $g$ が原始根でないとすると、$d$ は $\varphi(n)$ の真の約数であり、$\varphi(n)/d>1$ はある素数 $q$ で割り切れる。このとき $\varphi(n)/q=d\cdot\bigl(\varphi(n)/(dq)\bigr)$ は $d$ の倍数なので、$g^{\varphi(n)/q}\equiv1\pmod n$ となり、条件が破れる。

$p-1=de$ と書く。多項式の恒等式
$$ x^{p-1}-1=(x^d-1)\,h(x),\qquad h(x)=x^{d(e-1)}+x^{d(e-2)}+\cdots+x^d+1 $$
が成り立つ。Fermatの小定理により、$1,2,\dots,p-1$ の $p-1$ 個の剰余類はすべて $x^{p-1}-1\equiv0\pmod p$ の解である。各解 $a$ について $p\mid(a^d-1)h(a)$ なので、$p$ が素数であることから（素数 の記事の Euclid の補題）、$a^d\equiv1$ か $h(a)\equiv0\pmod p$ の少なくとも一方が成り立つ。$h$ は最高次の係数が $1$ の次数 $d(e-1)=p-1-d$ の多項式なので、$h(x)\equiv0$ の解は高々 $p-1-d$ 個である。したがって $x^d\equiv1$ の解は少なくとも $(p-1)-(p-1-d)=d$ 個ある。一方、$x^d-1$ は次数 $d$ なので解は高々 $d$ 個である。よってちょうど $d$ 個である。

$p=2$ なら $1$ が原始根である。$p\geq3$ とし、$p-1=q_1^{e_1}q_2^{e_2}\cdots q_r^{e_r}$ を素因数分解する（$q_i$ は相異なる素数、$e_i\geq1$）。
各 $i$ について、lem-primitive-root-roots-of-unity により $x^{q_i^{e_i}}\equiv1$ の解はちょうど $q_i^{e_i}$ 個、$x^{q_i^{e_i-1}}\equiv1$ の解はちょうど $q_i^{e_i-1}$ 個ある。後者の解は前者の解でもあるので、$a^{q_i^{e_i}}\equiv1$ かつ $a^{q_i^{e_i-1}}\not\equiv1$ を満たす $a$ が存在する（$q_i^{e_i}-q_i^{e_i-1}>0$ 個ある）。このような $a_i$ を一つとると、prop-primitive-root-order-divides により $\operatorname{ord}_p(a_i)$ は $q_i^{e_i}$ を割るが $q_i^{e_i-1}$ を割らないので、$\operatorname{ord}_p(a_i)=q_i^{e_i}$ である。
$g=a_1a_2\cdots a_r$ とおく。$(\mathbb{Z}/p\mathbb{Z})^{\times}$ は可換群であり、位数 $q_1^{e_1},\dots,q_r^{e_r}$ は対ごとに互いに素なので、元の位数 の記事の命題「可換な元の積の位数」を繰り返し用いて
$$ \operatorname{ord}_p(g)=q_1^{e_1}q_2^{e_2}\cdots q_r^{e_r}=p-1 $$
を得る。よって $g$ は原始根である。

prop-primitive-root-equivalent により、$n$ と互いに素な $a$ は $0\leq k<\varphi(n)$ のただ一つの $k$ で $a\equiv g^k$ と書ける。元の位数 の記事の命題「冪の位数の公式」により
$$ \operatorname{ord}_n(g^k)=\frac{\varphi(n)}{\gcd(k,\varphi(n))} $$
であり、これが $\varphi(n)$ に等しいことは $\gcd(k,\varphi(n))=1$ と同値である。$0\leq k<\varphi(n)$ でこの条件を満たす $k$ は $\varphi(\varphi(n))$ 個ある（$\varphi(n)=1$ のときは $k=0$ の $1$ 個で、$\varphi(1)=1$ と一致する）。

まず、$m\geq3$ なら $\varphi(m)$ は偶数である。実際、$x\mapsto m-x$ は $1\leq x\leq m-1$ で $m$ と互いに素な $x$ の集合をそれ自身に移し（$\gcd(m-x,m)=\gcd(x,m)$）、2 回施すと元に戻る。固定点 $x=m-x$ があれば $m=2x$ で $\gcd(x,m)=x=1$、すなわち $m=2$ となるので、$m\geq3$ では固定点がなく、元は 2 個ずつ組になる。
よって $\varphi(a)$ と $\varphi(b)$ はともに偶数であり、$L=\operatorname{lcm}(\varphi(a),\varphi(b))$ は $\varphi(a)\varphi(b)/\gcd(\varphi(a),\varphi(b))\leq\varphi(a)\varphi(b)/2$ を満たす。$u$ を $n$ と互いに素な整数とすると、$u$ は $a$ とも $b$ とも互いに素なので、Eulerの定理(整数論) により $u^{\varphi(a)}\equiv1\pmod a$、$u^{\varphi(b)}\equiv1\pmod b$ であり、$L$ はその両方の倍数だから $a\mid u^L-1$ かつ $b\mid u^L-1$ である。$\gcd(a,b)=1$ なので $ab\mid u^L-1$、すなわち $u^L\equiv1\pmod n$ である（互いに素 の記事の命題「互いに素な因子の消去」から従う）。したがって $\operatorname{ord}_n(u)\leq L$ である。一方、互いに素 の記事の系「Euler関数の乗法性」により $\varphi(n)=\varphi(a)\varphi(b)\geq2L>L$ なので、位数 $\varphi(n)$ の元はない。

$k=3$ のとき、$u=2t+1$ と書くと $u^2=4t(t+1)+1$ であり、$t(t+1)$ は偶数なので $u^2\equiv1\pmod 8$ である。$k\geq3$ で $u^{2^{k-2}}=1+2^ks$（$s$ は整数）と書けたとすると、
$$ u^{2^{k-1}}=(1+2^ks)^2=1+2^{k+1}s+2^{2k}s^2\equiv1\pmod{2^{k+1}} $$
である（$2k\geq k+1$）。よってすべての $k\geq3$ で主張が成り立つ。$2^k$ と互いに素な数は奇数なので、どの元の位数も $2^{k-2}<2^{k-1}=\varphi(2^k)$ 以下であり、原始根はない。

二項定理により
$$ (g+p)^{p-1}=g^{p-1}+(p-1)g^{p-2}p+\sum_{i=2}^{p-1}\binom{p-1}{i}g^{p-1-i}p^i\equiv g^{p-1}+(p-1)pg^{p-2}\pmod{p^2} $$
である。$g^{p-1}\equiv1\pmod{p^2}$ なら、右辺は $1-pg^{p-2}+p^2g^{p-2}\equiv1-pg^{p-2}\pmod{p^2}$ であり、$p\nmid g$ なので $pg^{p-2}\not\equiv0\pmod{p^2}$ である。よって $(g+p)^{p-1}\not\equiv1\pmod{p^2}$ である。$g+p\equiv g\pmod p$ なので $g+p$ も $p$ を法とする原始根であり、後半が従う。

$j=0$ では $t_0=t$ でよい。$x^{p^j}=1+p^{j+1}t_j$、$p\nmid t_j$ とすると、二項定理により
$$ x^{p^{j+1}}=(1+p^{j+1}t_j)^p=1+p\cdot p^{j+1}t_j+\sum_{i=2}^{p}\binom{p}{i}p^{i(j+1)}t_j^i $$
である。$i=2$ の項は $\binom p2p^{2(j+1)}=\frac{p-1}{2}p^{2j+3}$ であり、$p$ が奇数なので $(p-1)/2$ は整数、$2j+3\geq j+3$ なので $p^{j+3}$ で割り切れる。$3\leq i\leq p$ の項は $i(j+1)\geq3(j+1)\geq j+3$ なので $p^{j+3}$ で割り切れる。よって $x^{p^{j+1}}=1+p^{j+2}(t_j+ps)$（$s$ は整数）と書け、$t_{j+1}=t_j+ps$ は $p$ で割り切れない。

存在しないこと：$n\geq2$ が $2,4,p^k,2p^k$ のいずれでもないとする。$n$ が 2 の冪なら $n=2^k$、$k\geq3$ であり、lem-primitive-root-power-of-two により原始根はない。$n$ が奇素因数 $p$ をもつとし、$n=2^ep^km$（$p\nmid m$、$m$ は奇数）と書く。$m\geq3$ なら $a=2^ep^k\geq3$、$b=m\geq3$ は互いに素であり、lem-primitive-root-no-two-factors により原始根はない。$m=1$ なら、$n$ が $p^k,2p^k$ でないことから $e\geq2$ であり、$a=2^e\geq4$、$b=p^k\geq3$ に lem-primitive-root-no-two-factors を適用すればよい。
存在すること：$n=2$ では $1$、$n=4$ では $3$（$3^1\equiv3$、$3^2\equiv1\pmod 4$、$\varphi(4)=2$）が原始根である。$p$ を奇素数、$k\geq1$ とする。thm-primitive-root-prime と lem-primitive-root-lift により、$p$ を法とする原始根 $g$ で $g^{p-1}=1+pt$、$p\nmid t$ となるものがとれる。$d=\operatorname{ord}_{p^k}(g)$ とおく。prop-primitive-root-order-divides により $d\mid\varphi(p^k)=p^{k-1}(p-1)$ である。また $g^d\equiv1\pmod{p^k}$ から $g^d\equiv1\pmod p$ であり、$g$ は $p$ を法とする原始根なので $p-1\mid d$ である。よって $d=(p-1)p^j$、$0\leq j\leq k-1$ と書ける。$j\leq k-2$ とすると、lem-primitive-root-lte により $g^{d}=(g^{p-1})^{p^j}=1+p^{j+1}t_j$、$p\nmid t_j$ で、$j+1\leq k-1$ だから $g^d\not\equiv1\pmod{p^k}$ となり矛盾する。よって $j=k-1$、$d=\varphi(p^k)$ であり、$g$ は $p^k$ を法とする原始根である。
最後に $n=2p^k$ とする。$g$ を $p^k$ を法とする原始根とし、$g$ が偶数なら $g+p^k$ に取り替えて奇数にする（$p^k$ を法とする剰余類は変わらない）。奇数 $u$ については $u^s-1$ がつねに偶数なので、$u^s\equiv1\pmod{2p^k}$ と $u^s\equiv1\pmod{p^k}$ は同値である。よって $\operatorname{ord}_{2p^k}(g)=\operatorname{ord}_{p^k}(g)=\varphi(p^k)=\varphi(2p^k)$ であり、$g$ は $2p^k$ を法とする原始根である。