ferma.tex

\documentclass{jlreq}
​
%% \documentclass{ltjsarticle}
%% \usepackage[haranoaji,deluxe]{luatexja-preset}
​
%% \usepackage[uplatex,deluxe]{otf}
\usepackage[top=2cm, bottom=2cm, left=2cm, right=2cm]{geometry}
\usepackage{ascmac}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{color}
\usepackage[table]{xcolor}
​
\newcommand{\defiff}{\overset{\text{def}}{\iff}}
​
%% \renewcommand{\theenumi}{(\arabic{enumi})}
%% \renewcommand{\thesubsubsection}{【\arabic{subsubsection}】}
​
\theoremstyle{definition}
\newtheorem{thm}{定理}[section]
\newtheorem{lem}[thm]{補題}
\newtheorem{prop}[thm]{命題}
\newtheorem{cor}[thm]{系}
\newtheorem{ass}[thm]{仮定}
\newtheorem{dfn}[thm]{定義}
​
\newtheorem{thm*}{定理}[section]
\newtheorem{lem*}[thm]{補題}
\newtheorem{prop*}[thm]{命題}
\newtheorem{cor*}[thm]{系}
\newtheorem{ass*}[thm]{仮定}
\newtheorem{dfn*}[thm]{定義}
​
​
\title{Fermatの定理・Eulerの定理}
\author{}
\date{\today}
​
\begin{document}
​
\maketitle
​
\section{Fermatの定理}
​
\begin{thm}
  素数$p$と整数$n$について，$n \perp p$のとき以下が成り立つ．
  \[
  n^{p-1} \equiv 1 \ (\bmod \ p).
  \]
  \label{thm:Fermat_little}
\end{thm}
​
\begin{dfn}
  二つの数$m, n$について以下が成り立つとき，$m$は$n$を割り切るといい，$m \mid n$と表す．ただし，$k$は整数である．
  \[
  m > 0 \ \land \ \exists k (n = k m).
  \]
\end{dfn}
​
\begin{dfn}
  二つの数$m,n$に対して，$m$を$n$で割った剰余$n \bmod m$は以下のように定義される．
  \[
  n \bmod m \defiff n - m \left\lfloor \frac{n}{m} \right\rfloor.
  \]
\end{dfn}
​
\begin{dfn}
  二つの整数$m,n$に対して，$\gcd(m, n) = 1$のとき，$m$と$n$は互いに素であるといい$m \perp n$と表す．
  \[
  m \perp n \defiff \gcd(m,n) = 1.
  \]
\end{dfn}
​
​
\begin{dfn}
  三つの数$a, b, m$について，$a$を$m$で割った剰余と$b$を$m$で割った剰余が等しいとき，$a$と$b$は$m$を法として合同であるといい，$a \equiv b \ (\bmod \ m)$もしくは$a \equiv_m b$と記す．
  \[
  a \equiv_m b \defiff a \bmod m = b \bmod m.
  \]
\end{dfn}
​
%% \begin{dfn}
%%   二つの数$m, n$に対して，整数$k$が$m, n$の両方を割り切るとき，即ち，$k \mid m$かつ$k \mid n$であるとき，$k$を$m$と$n$の公約数という．
%%   \[
%%   k \ \textrm{は} \ m \ \textrm{と} \ n \ \textrm{の公倍数である．} \defiff k \mid m \ \land k \mid n.
%%   \]
%% \end{dfn}
​
%% \begin{dfn}
%%   二つの数$m, n$に対する最大公約数$\gcd(m,n)$は以下のように定義される．ただし，$k$は整数である．
%%   \[
%%   \gcd(m,n) \defiff \max\{ k \mid (k \mid m) \ \land \ (k \mid n) \}
%%   \]
%% \end{dfn}
​
\begin{lem}
  \[
  a \equiv_m b \iff \exists k (a - b = km), \mathrm{where} \ k \in \mathbb{Z}.
  \]
  \label{lem:mod_mult}
\end{lem}
​
\begin{proof}
  ($\Rightarrow$)を示す．$a \equiv_m b$を仮定する．仮定より，$a \bmod m = b \bmod m$が成り立つ．そして，剰余の定義より，$a - m\left\lfloor \frac{a}{m} \right\rfloor = b - \left\lfloor \frac{b}{m} \right\rfloor$が成り立つ．
  
  よって，整数$\left\lfloor \frac{a}{m} \right\rfloor - \left\lfloor \frac{b}{m} \right\rfloor$について，
  \[
  a - b = m\left( \left\lfloor \frac{a}{m} \right\rfloor - \left\lfloor \frac{b}{m} \right\rfloor \right)
  \]
  が成り立つ．
​
  以上より，$a \equiv_m b \to \exists k (a - b = km)$が成り立つ．
​
  次に逆方向を示す．$\exists k (a - b = km)$が成り立つと仮定する．仮定を満たすような整数を$k^\prime$とする．
​
  $m$が$0$のときは$a=b$であり，$a \equiv_m b$である．\footnote{$a \bmod m$と$b \bmod m$が定義されない気がするが．}．
​
  $m$が$0$でないとき，
  \begin{align*}
    a \bmod m &= a - m\left\lfloor \frac{a}{m} \right\rfloor \\
    &= (mk^\prime + b) - m\left\lfloor \frac{mk^\prime + b}{m} \right\rfloor \\
    &= (mk^\prime + b) - m\left\lfloor k^\prime + \frac{b}{m} \right\rfloor \\
    &= (mk^\prime + b) - mk^\prime - m\left\lfloor \frac{b}{m} \right\rfloor \\ %& $k^\prime$ \ \mathrm{is \ an \ integer} \\
    &= b - m\left\lfloor \frac{b}{m} \right\rfloor \\
    &= b \bmod m
  \end{align*}
  である．即ち，$a \equiv_m b$が成り立つ．
​
  よって，$\exists k (a - b = km) \to a \equiv_m b$が成り立つ．
​
  以上より，補題\ref{lem:mod_mult}は成り立つ．
\end{proof}
​
​
\begin{lem}
  整数$m, n$に対して，拡張ユークリッドの互除法により式\ref{eq:exEuclid}を満たす整数$m^\prime , n^\prime$を求められる．
  \begin{equation}
    mm^\prime + nn^\prime = \gcd(m,n).
    \label{eq:exEuclid}
  \end{equation}
\end{lem}
​
\begin{proof}
TAOCP Vol. 1のpp.14--15を参照されたい．
\end{proof}
​
%% \begin{lem}
%%   \[
%%   a \equiv_m b \iff \exists k (a - b = km), \mathrm{where} \ k \in \mathbb{Z}.
%%   \]
%%   \label{lem:mod_mult}
%% \end{lem}
​
\begin{lem}
  整数$a,b,c,d,m$に対して
  \[
  a \equiv_m b \ \land \ c \equiv_m d \to ac \equiv_m bd
  \]
  が成り立つ。
  \label{lem:cong_mult}
\end{lem}
​
\begin{proof}
  $a \equiv_m b \ \land \ c \equiv_m d$を仮定する．仮定より，$a - b = mk$と$c - d = ml$を満たす整数$k, l$が存在する．そのような整数を$k^\prime$, $l^\prime$とする．
  \begin{align*}
    ac - bd &= (a-b)c + (c-d)b \\
    &= mk^\prime c + ml^\prime b \\
    &= m(k^\prime c + l^\prime b)
  \end{align*}
  これより，$ac \equiv_m bd$が成り立つ．
​
  以上より，$a \equiv_m b \ \land \ c \equiv_m d \to ac \equiv_m bd$が成り立つ．
\end{proof}
​
\begin{lem}
  整数$a,b,d,m$に対して，$d \perp m$のとき以下が成り立つ．
  \[
  ad \equiv_m bd \iff a \equiv_m b
  \]
  \label{lem:cong_div}
\end{lem}
​
\begin{proof}
  ($\Leftarrow$)は補題\ref{lem:cong_mult}より明らかである．
  
  整数$d, m$に対して以下を満たす整数$d^\prime$と$m^\prime$を拡張ユークリッドの互除法により求められる．
  \[
  d^\prime d + m^\prime m = \gcd(m, n) = 1.
  \]
  この式より，$d^\prime d - 1 = - m^\prime m$なので，$d^\prime d - 1$は$m$の倍数である．即ち，$d^\prime d \equiv_m 1$が成り立つ．
​
  ($\Rightarrow$)を示す．$ad \equiv_m bd$を仮定する．$d^\prime \equiv_m d^\prime$と補題\ref{lem:cong_mult}より$ad^\prime d \equiv bd^\prime d$が成り立つ．更に，$d^\prime d \equiv_m 1$, $a \equiv_m a$, $b \equiv_m b$と補題\ref{lem:cong_mult}より，$a d^\prime d \equiv_m a$と$b d^\prime d \equiv_m b$が成り立つ．そして，$\equiv_m$は推移律が成り立つので$a \equiv_m b$が成り立つ．
​
  よって，整数$a,b,d,m$に対して，$d \perp m$のとき$ad \equiv_m bd \to a \equiv_m b$が成り立つ．
​
  以上より，整数$a,b,d,m$に対して，$d \perp m$のとき$ad \equiv_m bd \iff a \equiv_m b$である．
\end{proof}
​
​
\begin{lem}
  素数$p$と整数$n$に対して，以下の命題が成り立つ．ただし，$n$は$p$と互いに素な数で，$i$は整数である．
  \[
  \{ in \bmod p \mid 1 \le i \le p-1 \} = \{ i \mid 1 \le i \le p-1 \}.
  \]
  \label{lem:Fermat_little}
\end{lem}
​
\begin{proof}
  $\{ in \bmod p \mid 1 \le i \le p-1 \} \neq \{ i \mid 1 \le i \le p-1 \}$を仮定する．即ち，$in \bmod p = jn \bmod p$となる$p-1$以下の異なる整数$i, j$が存在すると仮定する．仮定より，$in \equiv_p jn$であり，$n$は$p$と互いに素である．このことと補題\ref{lem:cong_div}より，$i \equiv_p j$が成り立つ．ここで，$i$と$j$は$1$以上$p$未満の数なので$i = j$となる．これは矛盾である．以上より，素数$p$と，$p$と互いに素な$n$について$\{ in \bmod p \mid 1 \le i \le p-1 \} = \{ i \mid 1 \le i \le p-1 \}$である.
\end{proof}
​
​
準備が整ったので，Fermatの定理（定理\ref{thm:Fermat_little}）の証明を以下に示す．
​
\begin{proof}
  補題\ref{lem:Fermat_little}と補題\ref{lem:cong_mult}より，集合$\{ in \bmod p \mid 1 \le i \le p-1 \}$の総積$\prod_{i=1}^{p-1} in$と集合$\{ i \mid 1 \le i \le p-1 \}$の総積$(p-1)!$について，それらを$p$で割った剰余は等しい．即ち，
  \[
  \prod_{i=1}^{p-1} in \equiv_p \prod_{i=1}^{p-1} i 
  \]
  が成り立つ．ここで，$\prod_{i=1}^{p-1} in = n^{p-1}(p-1)!$かつ$\prod_{i=1}^{p-1}i = (p-1)!$なので，
  \[
  n^{p-1}(p-1)! \equiv_p (p-1)!
  \]
  である．そして，$p$は素数なので$1$から$p-1$までの数は$p$と互いに素である．よって，補題\ref{lem:cong_div}より$n^{p-1} \equiv_p 1$が成り立つ．
\end{proof}
​
\begin{cor}
  Fermatの定理は以下の形でも表される．
  \[
  n^p \equiv_p n.
  \]
\end{cor}
​
\clearpage
​
\begin{thm}
  互いに素な数である$m$と$n$について以下の式が成り立つ．
  \[
  n^{\varphi(m)} \equiv_m 1.
  \]
  ただし，$\varphi(m)$は以下のように定義される函数である（$1$から$m$までの$m$と互いに素な数の個数である）．$x$は整数である．
  \[
  \varphi(m) \defiff |\{ x \mid 1 \leq x \leq p \ \land \ x \perp m\}|
  \]
  \label{thm:Euler}
\end{thm}
​
\begin{lem}
  互いに素である二つの整数$m,n$について以下が成り立つ．ただし，$i$は整数である．
  \[
  \{ in \bmod m \mid 1 \leq i \leq m \ \land \ i \perp m \} = \{ i \mid 1 \leq i \leq m \ \land \ i \perp m \}
  \]
  \label{lem:Euler}
\end{lem}
​
\begin{proof}
  $\{ in \bmod m \mid 1 \leq i \leq m \ \land \ i \perp m \} \neq \{ i \mid 1 \leq i \leq m \ \land \ i \perp m \}$を仮定する．即ち，$in \bmod m = jn \bmod m$となる，$i \perp m$, $j \perp m$である異なる整数$i$と$j$が存在すると仮定する．仮定より$in \equiv_m jn$であり$m \perp n$なので，補題\ref{lem:cong_div}より$i \equiv_m j$が成り立つ．ここで，$i$と$j$は$m$未満の数なので$i = j$であるが，これは矛盾である．
​
  以上より，互いに素である二つの整数$m, n$に対して，$\{ in \bmod m \mid 1 \leq i \leq m \ \land \ i \perp m \} = \{ i \mid 1 \leq i \leq m \ \land \ i \perp m \}$が成り立つ．
\end{proof}
​
定理\ref{thm:Euler}の証明を以下に示す．
​
\begin{proof}
  集合$\{ i \mid 1 \leq i \leq m \ \land \ i \perp m \}$の要素を小さい順に$i_1, i_2, \dots, i_{\varphi(m)}$とおく．このとき，補題\ref{lem:Euler}と補題\ref{lem:cong_mult}より，
  \[
  \prod_{k=1}^{\varphi(m)} i_kn \equiv_m \prod_{k=1}^{\varphi(m)} i_k
  \]
  が成り立つ．ここで，すべての$i_k$は$m$と互いに素なので補題\ref{lem:cong_div}より
  \[
  n^{\varphi(m)} \equiv_m 1
  \]
  が成り立つ．
​
  以上より，互いに素な数である$m$と$n$について$n^{\varphi(m)} \equiv_m 1$が成り立つ．
\end{proof}
​
​
\end{document}