合同式:合成数を法とする合同式
$\newcommand{\N}{\mathbb{N}}$ $\newcommand{\Z}{\mathbb{Z}}$ $\newcommand{\Q}{\mathbb{Q}}$ $\newcommand{\R}{\mathbb{R}}$ $\newcommand{\C}{\mathbb{C}}$ $\newcommand{\LCM}{\mathrm{LCM}}$ $\newcommand{\abs}[1]{\left\lvert#1\right\rvert}$ $\newcommand{\wenvert}[1]{\left\lvert\left\lvert#1\right\rvert\right\rvert}$ $\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}$ $\newcommand{\mathmod}[1]{\ \left(\mathrm{mod}\ #1\right)}$
合同式の記事では主に素数を法とする場合について扱ったが、この記事では合成数を法とする場合について扱う。
それで、主に多項式 $f(x)$ について
$$f(x)\equiv 0\mathmod{N} \quad\quad (*)$$
の形の方程式を中心に解説する。
合成数を法とする1次方程式
$\gcd(a, n)=1$ ならば合同式:定理1.7より $$ax\equiv b\mathmod{n}\Longleftrightarrow x\equiv ba^{-1}\mathmod{n}$$ となる。つまり $$ax\equiv b\mathmod{n} \quad\quad (1.1)$$ となる $x\mathmod{n}$ が一意に定まる。
一方、$d=\gcd(a, n)>1$ のときは状況が変化する。 $ax\equiv b\mathmod{n}$ の解となる $x$ をとり、$b=ax-qn$ とおくと $$d\mid (ax-qn)=b$$ となって、$d$ は $b$ を割り切らなければならない。つまり $d$ が $b$ を割り切らないときは $(1.1)$ は解をもたないのである。
一方 $d\mid b$ のとき合同式:定理1.2(7)より $$ax\equiv b\mathmod{n}\Longleftrightarrow (a/d)x\equiv (b/d)\mathmod{n/d}$$ となる。倍数と約数:定理2.5より $\gcd(a/d, n/d)=1$ だから 合同式:定理1.7より、$n/d$ を法とする $a/d$ の逆元 $s$ がとれ、 $$ax\equiv b\mathmod{n}\Longleftrightarrow x\equiv sb/d\mathmod{n/d}$$ となる。よって $ax\equiv b\mathmod{n}$ となる $x\mathmod{n}$ は $$x\equiv kn/d+sb/d\mathmod{n} (k=0, 1, \ldots, d-1) \quad\quad (1.2) $$ で与えられる。つまり $(1.1)$ は $\Z/n\Z$ に $d$ 個の解をもつ。 よって、次のことがわかる。
定理1.1
$$ax\equiv b\mathmod{n}$$ が解をもつための必要十分条件は $d=\gcd(a, n)$ が $b$ を割り切ることであり、 そのとき、$n/d$ を法とする $a/d$ の逆元を $s$ とおくと、 この合同式は $\Z/n\Z$ に $(1.2)$ で与えられる $d$ 個の解をもつ。
合成数を法とする一般の方程式
中国式剰余定理から、合成数を法とする方程式 $$f(x)\equiv 0\mathmod{n}$$ は、素数べきを法とする合同式 $$f(x)\equiv 0\mathmod{p^e}$$ に還元されるので、素数べきを法とする合同式について考察する。
まず $f^\prime(x)$ を多項式環の記事で定義した多項式 $f(x)$ の微分とする。 この微分が素数べきを法とする合同式を考察する上で重要な役目を果たす。
定理2.1
$p$ が素数で $$f(x_1)\equiv 0\mathmod{p}, f^\prime(x_1)\not\equiv 0\mathmod{p}$$ となる $x_1\mathmod{p}$ をとる。 $$f(x)\equiv 0\mathmod{p^e}$$ となる $x\mathmod{p^e}$ が存在し、なおかつそのような $x$ で $x\equiv x_1\mathmod{p}$ となるものが一意に定まる。
より正確に、正の整数 $t$ について $$f(x_t)\equiv 0\mathmod{p^t}, x_t\equiv x_1\mathmod{p}, f^\prime(x_1)\not\equiv 0\mathmod{p}$$ のとき、ちょうど1つの剰余類 $y_t\mathmod{p}$ に対して $$f(x_t+y_t p^t)\equiv 0\mathmod{p^{t+1}}$$ となり、$y\not\equiv y_t\mathmod{p}$ のとき $$f(x_t+y p^t)\not\equiv 0\mathmod{p^{t+1}}$$ となる。
Proof.
$$f(x)=a_d x^d+a_{d-1} x^{d-1}+\cdots+a_0$$ とおく。 $$f(x_1)\equiv 0\mathmod{p}, f^\prime(x_1)\not\equiv 0\mathmod{p}$$ となる $x_1\mathmod{p}$ をとり、正の整数 $t$ について $$f(x_t)\equiv 0\mathmod{p^t}, x_t\equiv x_1\mathmod{p}$$ となる $x_t\mathmod{p}$ が存在するとする。
$$f(x_t+p^t)=\sum_{k=0}^d a_k (x_t+p^t)^k=\sum_{k=0}^d a_k\left(x_t^k+kx_t^{k-1}p^t+\binom{k}{2}x_t^{k-2}p^{2t}+\cdots\right)$$ と展開することができ、$t\geq 1$ なので $f(x_t)=u_t p^t$ とおくと $$f(x_t+p^t)\equiv a_0+\sum_{k=1}^d a_k(x_t^k+kx_t^{k-1}p^t)=f(x_t)+p^t f^\prime(x_t)=p^t(u_t+f^\prime(x_t)) \mathmod{p^{t+1}}$$ となる。 $f^\prime(x_1)\not\equiv 0\mathmod{p}$ であるから $$u_t+y_t f^\prime(x_t)\equiv 0\mathmod{p}$$ となる $y_t \mathmod{p}$ が一意に定まる。つまり $$f(x_t+y_t p^t)\equiv p^t(u_t+yf^\prime(x_t))\equiv 0\mathmod{p^{t+1}}$$ となる $y_t \mathmod{p}$ が一意に定まる。
□定理2.2
$p$ が素数、$e\geq 1$ で、$n$ が $p$ で割り切れないとき $$x^n\equiv 1\mathmod{p^e}$$ は $\Z/(p^e)\Z$ にちょうど $\gcd(n, p-1)$ 個の解をもつ。また $f(x)$ が $$x^n-1\equiv f(x)g(x)\mathmod{p}$$ となる多項式 $g(x)$ が存在し、$p$ を法とする次数が $d$ 以下の多項式ならば $$f(x)\equiv 0\mathmod{p^e}$$ は $\Z/(p^e)\Z$ に多くとも $d$ 個の解しかもたない。
Proof.
合同式:定理4.4より $$x^n\equiv 1\mathmod{p}\Longleftrightarrow x^{\gcd(n, p-1)}\equiv 1\mathmod{p}$$ となる。 $a$ を $p$ を法とする原始根とし、$x\equiv a^g\mathmod{p}$ とおくと $$a^{g\gcd(n, p-1)}\equiv 1\mathmod{p}\Longleftrightarrow (p-1)\mid g\gcd(n, p-1)\Longleftrightarrow (p-1)/\gcd(n, p-1)\mid g$$ となるから $$x^{\gcd(n, p-1)}\equiv 1\mathmod{p}\Longleftrightarrow x\equiv a^{k(p-1)/\gcd(n, p-1)}\mathmod{p} (k=0, 1, \ldots, \gcd(n, p-1)-1)$$ となる。よって $$x^n\equiv 1\mathmod{p}$$ は $\Z/p\Z$ にちょうど $\gcd(n, p-1)$ 個の解をもつ。 一方 $n$ は $p$ で割り切れないから $x^n\equiv 1\mathmod{p}$ のとき $$(x^n-1)^\prime=nx^{n-1}\not\equiv 0\mathmod{p}$$ となる。よって定理2.1より $$x^n\equiv 1\mathmod{p^e}$$ も $\Z/(p^e)\Z$ にちょうど $\gcd(n, p-1)$ 個の解をもつ。
つぎに $f(x)$ が $$x^n-1\equiv f(x)g(x)\mathmod{p}$$ となる多項式 $g(x)$ が存在し、$p$ を法とする次数が $d$ 以下の多項式とする。合同式:定理5.3より $$f(x)\equiv 0\mathmod{p}$$ は $\Z/p\Z$ に多くとも $d$ 個の解しかもたない。
$$f(a)\equiv f^\prime(a)\equiv 0\mathmod{p}$$ となる $a\mathmod{p}$ が存在するとすると、 多項式環:定理15より $$f(x)\equiv g(x)(x-a)^2\mathmod{p}$$ となる $g(x)$ が存在するので $$x^n-1\equiv h(x)(x-a)^2\mathmod{p}$$ となる $h(x)$ が存在する。よって多項式環:定理14より $$x^n-1\equiv (x^n-1)^\prime\equiv 0\mathmod{p}$$ は $x\equiv a\mathmod{p}$ を解にもつ。これは矛盾である。
よって $$f(a)\equiv 0\mathmod{p}$$ ならば $f^\prime(a)\not\equiv 0\mathmod{p}$ となるので 定理2.1より $$f(x)\equiv 0\mathmod{p^e}$$ の解の個数は $f(x)\equiv 0\mathmod{p}$ の解の個数と一致する。
□定理2.3
$$N=p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$$ と素因数分解する。 $$f(x)\equiv 0\mathmod{p_i^{e_i}}$$ の解 $x\mathmod{p_i^{e_i}}$ の個数を $m_i$ とおくと、 $$f(x)\equiv 0\mathmod{N} \quad\quad (*)$$ の解の個数は $\prod_{i=1}^k m_i$ に等しい。 とくに $f(x)$ が各 $p_i$ を法とする次数が $d_i$ 以下の多項式で、いずれの $i$ についても $$f(a)\equiv f^\prime(a)\equiv 0\mathmod{p_i}$$ となる $a\mathmod{p_i}$ が存在しないとき、$(*)$ の解の個数は $\prod_{i=1}^k d_i$ 以下である。
Proof.
中国式剰余定理から $(x_1\mathmod{p_1^{e_1}}, \ldots, x_k\mathmod{p_k^{e_k}})$ の組と $$x\equiv x_i\mathmod{p_i^{e_i}} (i=1, \ldots, k)$$ となる $x\mathmod{N}$ は$1$対$1$に対応する。 $$f(x)\equiv 0\mathmod{N}\Longleftrightarrow f(x)\equiv 0\mathmod{p_i^{e_i}} (i=1, \ldots, k)\Longleftrightarrow f(x_i)\equiv 0\mathmod{p_i^{e_i}} (i=1, \ldots, k)$$ となるから、 $(*)$ の解 $x\mathmod{N}$ は $$f(x_i)\equiv 0\mathmod{p_i^{e_i}} (i=1, \ldots, k)$$ となる $(x_1\mathmod{p_1^{e_1}}, \ldots, x_k\mathmod{p_k^{e_k}})$ の組と対応するので $(*)$ の解の個数は $\prod_{i=1}^k m_i$ に等しい。
$f(x)$ が各 $p_i$ を法とする次数が $d_i$ 以下の多項式ならば $$f(x)\equiv 0\mathmod{p_i}$$ の解の個数は $d_i$ 以下である。 $$f(a)\equiv f^\prime(a)\equiv 0\mathmod{p_i}$$ となる $a\mathmod{p_i}$ が存在しないので、定理2.1より $$f(x)\equiv 0\mathmod{p_i^{e_i}}$$ の解の個数も $d_i$ 以下である。つまり $m_i\leq d_i$ であるから $(*)$ の解の個数は $\prod_{i=1}^k d_i$ 以下である。
□素数べきを法とする原始根
$p$ を法とする原始根 $a\mathmod{p}$ とは $$1, a, \ldots, a^{p-2}\mathmod{p}$$ が $p$ を法とする既約剰余類をすべてあらわすものであった。
$p^e$ を法とする既約剰余類は $p^e-p^{e-1}=p^{e-1}(p-1)$ 個あるから $$1, a, \ldots, a^{p^{e-1}(p-1)}\mathmod{p}$$ が $p^e$ を法とする既約剰余類をすべてあらわすとき、 $a\mathmod{p^e}$ を、$p^e$ を法とする原始根という。
$\mathrm{LTE}$ (Lifting The Exponent)と呼ばれる、次の補題から証明する。
補題3.1(LTE)
$p>2$ が奇素数、$\gcd(a, b)=1$ かつ $a, b$ がいずれも $p$ で割り切れない整数で $g$ が $$p\mid (a^g-b^g),$$ となる最小の正の整数、$f$ を $$p^f\mid\mid (a^g-b^g)$$ となる整数とする。 このとき $$p\mid(a^n-b^n)\Longleftrightarrow g\mid n$$ で、$e, k$ が $$p^e\mid\mid k$$ となる正の整数ならば $$p^{e+f}\mid\mid (a^{gk}-b^{gk}).$$
Proof.
$bc\equiv a\mathmod{p}$ となる $c$ をとると $(bc)^n\equiv a^n\mathmod{p}$ だから $$a^n\equiv b^n\mathmod{p}\Longleftrightarrow c^n\equiv 1\mathmod{p}$$ となる。よって $g$ は $c^n\equiv 1\mathmod{p}$ となる最小の正の整数でもあるから $$a^n\equiv b^n\mathmod{p}\Longleftrightarrow g\mid n\mathmod{p}$$ となる。 $$p^f\mid\mid (a^g-b^g)$$
次に $e, k$ が $$p^e\mid\mid k$$ となる正の整数とする。
$$bc\equiv a\mathmod{p^{e+f+1}}$$ となる $c$ をとる。 $$(bc)^g\equiv a^g\equiv b^g\mathmod{p}$$ から $c^g\equiv 1\mathmod{p}$ となる。$\ell=0, 1, \ldots, e-1$ に対し、 $$c^{p^\ell g}\equiv 1\mathmod{p}$$ が明らかに成り立つ。そこで $$c^{p^\ell g}=Ap+1$$ とおくと、$p$ は奇数なので $$\begin{split} \frac{c^{p^{\ell +1}g}-1}{c^{p^\ell g}-1}= & \sum_{i=0}^{p-1} c^{i p^\ell g}=\sum_{i=0}^{p-1} (Ap+1)^i \\ = & p+\frac{p(p+1)}{2}Ap+(Ap^2)\sum_{i=2}^{p-1}\binom{i}{2}+\cdots \\ = & p+\frac{p+1}{2}Ap^2+(Ap^2)\sum_{i=2}^{p-1}\binom{i}{2}+\cdots \\ \end{split}$$ より、 $$\frac{c^{p^{\ell +1}g}-1}{c^{p^\ell g}-1}\equiv p\mathmod{p^2}$$ となるから $$p\mid\mid \frac{c^{p^{\ell +1}g}-1}{c^{p^\ell g}-1}$$ が成り立つ。よって $$p^e\mid\mid \frac{c^{p^e g}-1}{c^g-1}$$ となるから $$p^{f+e}\mid\mid (c^{p^e g}-1)$$ となる。 $k=p^e s$ とおくと $p\not\mid s$ だから $$c^{p^e g(s-1)}+\cdots+c^{p^e g}+1\equiv s\not\equiv 0\mathmod{p}$$ なので $$p^{f+e}\mid\mid (c^{gk}-1)=(c^{p^e g}-1)(c^{p^e g(s-1)}+\cdots+c^{p^e g}+1)$$ となる。よって $$p^{f+e}\mid\mid ((bc)^{gk}-b^{gk})$$ となるが、$bc\equiv a\mathmod{p^{e+f+1}}$ より $$a^{gk}\equiv (bc)^{gk}\mathmod{p^{e+f+1}}$$ だから $$p^{f+e}\mid\mid (a^{gk}-b^{gk})$$ である。
□とくに $$a^g\equiv 1\mathmod{p^f}, a^g\not\equiv 1\mathmod{p^{f+1}}$$ ならば $$a^{gk}\equiv 1\mathmod{p^{e+f}}, a^{gk}\not\equiv 1\mathmod{p^{e+f+1}}$$ となる。 Fermatの小定理より、$a$ が $p$ で割り切れないとき $$a^{p-1}\equiv 1\mathmod{p}$$ なので $$a^{p^{e-1}(p-1)}\equiv 1\mathmod{p^e}$$ となることがわかる。これにより、素数べきを法とする場合のEulerの定理の別証明が得られる。
定理3.2
$p>2$ が奇素数で $a$ を $p$ を法とする原始根とする。このとき $$a^{p-1}\not\equiv 1\mathmod{p^2}$$ ならば $$a^n\equiv 1\mathmod{p^e}\Longleftrightarrow p^{e-1}(p-1)\mid n$$ となる。すなわち $a\mathmod{p^2}$ は $p^2$ を法とする原始根となる。
Proof.
$a$ は原始根だから $a^n\equiv 1\mathmod{p^e}$ ならば $(p-1)\mid n$. そこで $n=m(p-1)$ とおく。仮定より $$p\mid\mid(a^{p-1}-1)$$ となるから、補題3.1より、$p^k\mid\mid m$ ならば $$p^{k+1}\mid\mid(a^n-1)$$ となる。よって $$p^e\mid (a^n-1)\Longleftrightarrow k\geq e-1\Longleftrightarrow p^{e-1}\mid m$$ となる。
□与えられた原始根 $a_1\mathmod{p}$ に対して $$a_2^{p-1}\equiv 1\mathmod{p^2}$$ となる $a_2\mathmod{p^2}$ は一意に定まるから $$a\equiv a_1\mathmod{p}, a\not\equiv a_2\mathmod{p}$$ ならば $$a^n\equiv 1\mathmod{p^e}\Longleftrightarrow p^{e-1}(p-1)\mid n$$ が成り立つ。このことから、$0\leq m, n<p^{e-1}(p-1)$ で $$a^m\equiv a^n\mathmod{p^e}$$ ならば $p^{e-1}(p-1)\mid (m-n)$ なので $m=n$ となる。よって $a^n (n=0, 1, \ldots, p^{e-1}(p-1)-1)$ は $p^e$ を法とする既約剰余類をすべてあらわすので $a$ は $p^e$ を法とする原始根である。このようにして $p^e$ を法とする原始根が存在することがいえる。
$p$ が奇素数のとき $p^e$ を法とする原始根 $a$ が存在することから、$p^e$ を法とする既約剰余類は $g\mathmod{p^{e-1}(p-1)}$ を用いて $a^g (0\leq g\leq p^{e-1}(p-1)-1)$ の形に一意的にあらわされる。 よって $p^e$ を法とする既約剰余類全体 $(\Z/(p^e)\Z)^*$ は乗法に関して群をなし、位数 $p^{e-1}(p-1)$ の巡回群に同型である。
もちろん、$a^n\equiv 1\mathmod{p^e}, 1\leq n\leq p^{e-1}(p-1)-1$ となる $n$ が存在するならば $a$ は $p^e$ を法とする原始根ではない。
このことから、次のことがわかる。
定理3.3
$p$ が奇素数で $e\geq 2$ とする。$a$ が $p$ を法とする原始根であるとき、次の条件は互いに同値。
- $a$ が $p^e$ を法とする原始根。
- $a^{p-1}\not\equiv 1\mathmod{p^2}$.
- $a^n\equiv 1\mathmod{p^e}\Longleftrightarrow p^{e-1}(p-1)\mid n$.
最後に、$p=2$ のときについて考える。
定理3.4
$d=u\times 2^v, 2\not\mid u$ とする。 $a\equiv 3, 5\mathmod{8}$ のとき $v=0$ ならば $2\mid\mid (a^d-1)$, $v\geq 1$ ならば $$2^{v+2}\mid\mid (a^d-1)$$ となる。
$a\equiv 1, 7\mathmod{8}$ のとき $a=k\times 2^m\pm 1, m\geq 3, 2\not\mid k$ とおくと $v\geq 1$ ならば $$2^{v+m}\mid\mid (a^d-1)$$ となる。$v=0$ ならば $a\equiv 1\mathmod{8}$ のとき $2^m\mid\mid (a^d-1)$, $a\equiv 7\mathmod{8}$ のとき $2\mid\mid (a^d-1)$ となる。
Proof.
まず $a\equiv 3, 5\mathmod{8}$ とする。 $$2\mid\mid (a-1), 2^3\mid\mid (a-1)(a+1)=(a^2-1)$$ である。また $t\geq 0$ に対して $$a^{2^t}+1\equiv 2\mathmod{4}$$ であるから $v\geq 2$ のとき $$a^{2^v}-1=(a-1)(a+1)\prod_{i=1}^{v-1}(a^{2^i}+1)$$ より $$2^{v+2}\mid\mid (a^{2^v}-1)$$ である。
次に $a\equiv 1, 7\mathmod{8}$ とする。 $a\equiv 1\mathmod{8}$ のとき $2^m\mid\mid (a-1)$, $a\equiv 7\mathmod{8}$ のとき $2\mid\mid (a-1)$ となる。また、いずれの場合も $$2^{m+1}\mid (a-1)(a+1)=a^2-1$$ となる。上と同様に $v\geq 2$ のとき $$a^{2^v}-1=(a-1)(a+1)\prod_{i=1}^{v-1}(a^{2^i}+1)$$ より $$2^{v+m}\mid\mid (a^{2^v}-1)$$ である。
最後に $$\frac{a^d-1}{a^{2^v}-1}=1+a^{2^v}+\cdots+a^{(u-1)2^v}\equiv u\equiv 1\mathmod{2}$$ より $2$ が $a^d-1$ を割り切る回数と $a^{2^v}-1$ を割り切る回数は一致するので、定理がいえる。
□このことから、次のことがわかる。
系3.5
$a$ が奇数ならば $e\leq 2$ のとき $$a^{2^{e-1}}\equiv 1\mathmod{2^e}$$ となり、$e\geq 3$ のとき $$a^{2^{e-2}}\equiv 1\mathmod{2^e}$$ となる。また、$e\leq 2$ のとき $$a^d\equiv 1\mathmod{2^e}\Longleftrightarrow 2^{e-1}\mid d$$ となる $a$ が存在し、 $e\geq 3$ のとき $$a^d\equiv 1\mathmod{2^e}\Longleftrightarrow 2^{e-2}\mid d$$ となる $a$ が存在する。
合成数を法とする既約剰余類
$$N=p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$$ と素因数分解すると、中国式剰余定理から $$x\equiv 1\mathmod{N}\Longleftrightarrow x\equiv 1\mathmod{p_i^{e_i}} (i=1, \ldots, k)$$ となる。
Carmichaelの$\lambda$関数を素数べきに対して $$\lambda(p^e)=\left\{\begin{array}{cl}2^{e-2} & (p=2\land e\geq 3),\\ p^{e-1}(p-1) & (p>2\lor e\leq 2)\end{array}\right.$$ と定め、一般の自然数 $N$ に対して $$\lambda(N)=\LCM [\lambda(p_1^{e_1}), \lambda(p_2^{e_2}), \ldots, \lambda(p_k^{e_k})]$$ により定める。明らかに $$\lambda(N)\mid \prod_{i=1}^k p_i^{e_i-1}(p_i-1)=\varphi(N)$$ が成り立つ。
定理4.1
$\gcd(a, N)=1$ ならば $$a^{\lambda(N)}\equiv 1\mathmod{N}$$ が成り立つ。
Proof.
$$N=p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$$ と素因数分解する。Eulerの定理および系3.5より $i=1, 2, \ldots, k$ に対して $$a^{\lambda(p_i^{e_i})}\equiv 1\mathmod{p_i^{e_i}}$$ となり、$\lambda(N)$ の定義より各 $\lambda(p_i^{e_i})$ は $\lambda(N)$ を割り切るので $$a^{\lambda(N)}\equiv 1\mathmod{p_i^{e_i}}$$ となるから、中国式剰余定理より $$a^{\lambda(N)}\equiv 1\mathmod{N}$$ となる。
□定理4.2
$$a^d\equiv 1\mathmod{N}\Longleftrightarrow \lambda(N)\mid d$$ となる $a\mathmod{N}$ が存在する。
Proof.
$$N=p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$$ と素因数分解し、$p_i$ が奇数のとき $a_i$ を $p_i^{e_i}$ を法とする原始根のし、 $p_i=2$ のとき $a_i$ を系3.5の後半のように $e_i\leq 2$ のとき $$a_i^d\equiv 1\mathmod{2^{e_i}}\Longleftrightarrow 2^{e_i-1}\mid d,$$ $e_i\geq 3$ のとき $$a_i^d\equiv 1\mathmod{2^{e_i}}\Longleftrightarrow 2^{e_i-2}\mid d$$ となるようにとる。 よって各 $i$ に対し、 $$a_i^d\equiv 1\mathmod{p_i^{e_i}}\Longleftrightarrow \lambda(p_i^{e_i})\mid d$$ となる。中国式剰余定理より $$a\equiv a_i\mathmod{p_i^{e_i}} (i=1, 2, \ldots, k)$$ となる $a\mathmod{N}$ がとれる。このとき $$a^d\equiv 1\mathmod{N}\Longleftrightarrow a_i^d\equiv 1\mathmod{p_i^{e_i}} (i=1, \ldots, r)\Longleftrightarrow \lambda(p_i^{e_i})\mid d (i=1, \ldots, r)$$ より、$\lambda(N)$ の定義から $$a^d\equiv 1\mathmod{N}\Longleftrightarrow \lambda(N)\mid d$$ となる。
□参考文献
- Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th Ed. revised by D. R. Heath-Brown and J. H. Silverman, Oxford University Press, 2008, Section 8.1-8.4.
- Trygve Nagell, Introduction to Number Theory, John Wiley & Sons, Inc. New York, 1951, Chapter III, Section 31-32.
- Harold N. Shapiro, Introduction to the Theory of Numbers, John Wiley & Sons, Inc. New York, 1983, Section 5.5.
