互いに素な整数$k$と素数$p$について
という性質があります。（以降、性質①といいます。）
\begin{equation}\large kx\equiv1\pmod p\end{equation}
を満たす$p$未満の自然数$x$が必ず存在する。
これが成り立つことを確かめてみます。
これは、$p$未満の自然数を掛けた連続する整数$k$の倍数
\[k, 2k, 3k, \cdots, (p-3)k, (p-2)k, (p-1)k\]
をそれぞれ$p$で割ったとき、この中に余りが$1$になるものが必ず含まれていることを主張しています。
この性質は、「連続する整数の倍数を自然数で割ったときの余りの性質」より示すことができます。
「連続する整数の倍数を自然数で割ったときの余りの性質」とは、
互いに素な整数$A$と$2$以上の自然数$B$について、
連続する$B$個の$A$の倍数をそれぞれ$B$で割ったときの余りを一列に並べたものは、$0, 1, 2, \cdots,$ $B-3, B-2, B-1$の並び替えである。
というものです。
連続する$B$個の$A$の倍数をそれぞれ$B$で割ったときの余りを一列に並べたものは、$0, 1, 2, \cdots,$ $B-3, B-2, B-1$の並び替えである。
ここで、連続する$B$個の$A$の倍数を
すると、$A=k, B=p$としたとき、
\[A, 2A, 3A, \cdots, (B-2)A, (B-1)A, BA\]
とします。すると、$A=k, B=p$としたとき、
互いに素な整数$k$と素数$p$について、連続する$p$個の$k$の倍数
となります。
\[k, 2k, 3k, \cdots, (p-2)k, (p-1)k, pk\]
をそれぞれ$p$で割ったときの余りを一列に並べたものは、$0, 1, 2, \cdots,$
$p-3, p-2, p-1$の並び替えである。
ところで、$pk$は$p$の倍数でもあるので、$p$で割ったときの余りは$0$です。
したがって、連続する$(p-1)$個の$k$の倍数
\[k, 2k, 3k, \cdots, (p-3)k, (p-2)k, (p-1)k\]
をそれぞれ$p$で割ったときの余りを一列に並べたものは、$1, 2, 3, \cdots,$
$p-3, p-2, p-1$の並び替えとなります。（以降、性質②といいます。）
すなわち、上記の$k$の倍数の中に$p$で割ったときの余りが$1$となるものが必ず含まれているということであり、性質①、すなわち
互いに素な整数$k$と素数$p$について
という性質があることがわかります。
\[\large kx\equiv1\pmod p\]
を満たす$p$未満の自然数$x$が必ず存在する。
性質①を満たす$p$未満の自然数の組
上では、$k$を$p$と互いに素な任意の整数として一般の性質を述べました。
ここからは、$k$も$x$と同様に$p$未満の自然数としたときの、$(1)$を満たす$k, x$の組について調べてみます。
ここからは、$k$も$x$と同様に$p$未満の自然数としたときの、$(1)$を満たす$k, x$の組について調べてみます。
$p$未満の自然数は$p$と互いに素なので、性質①より、どの$k$についても$(1)$を満たす$x$が必ず存在します。
また、性質②より、どの$k$についても$(1)$を満たす$x$はただ1つ存在することがわかります。
また、性質②より、どの$k$についても$(1)$を満たす$x$はただ1つ存在することがわかります。
$x$もまた$p$未満の自然数で$p$と互いに素なので、$k$と$x$の対称性より、どの$x$についても性質①を満たす$k$はただ1つ存在するといえます。
ゆえに、以下のことがいえます。
すなわち、異なる2つの組は、$k$の値も$x$の値も等しくなることはないということです。
$(1)$を満たす$k, x$の組に$(a, b), (a', b')$が存在するとき
（以降、性質③といいます。）
\[a=a'\ \Leftrightarrow\ b=b'\]
すなわち、異なる2つの組は、$k$の値も$x$の値も等しくなることはないということです。
$(1)$を満たす$p$未満の自然数$k,
x$の組には、$k=x$であるものが存在します。
それは、$k=1$と$k=p-1$の場合です。このことは、合同式であれば簡単に示せます。
それは、$k=1$と$k=p-1$の場合です。このことは、合同式であれば簡単に示せます。
$k=x$のとき、$(1)$は
\[k^2\equiv1\pmod p\]
となり、変形すると
\begin{align*}k^2-1&\equiv0\\[0.5em](k+1)(k-1)&\equiv0\end{align*}
$p$は素数なので
\begin{align*}k+1\equiv0&またはk-1\equiv0\\[0.5em]k\equiv-1&またはk\equiv1\end{align*}
ここで、$p-1\equiv-1\pmod p$より
\[k\equiv1またはk\equiv p-1\]
$1≦k≦p-1$より
\[k=1, p-1\]
$k=1$のとき
$(1)$に$k=1$を代入すると
\[x\equiv1\pmod p\]
となり、$x=1$であることがわかります。
そして、性質③より、$(k, x)=(1,1)$以外に$k=1$である組は存在しません。
$k=p-1$のとき
$(1)$に$k=p-1$を代入すると
\[(p-1)x\equiv1\pmod p\]
となり、$\pmod
p$において$p-1\equiv-1$で$(p-1)^2\equiv1$であることより、$x=p-1$であることがわかります。
そして、性質③より、$(k, x)=(p-1, p-1)$以外に$k=p-1$である組は存在しません。
$p=2$においては、$(1)$を満たす$k, x$の組は$(k, x)=(1, 1)$のみ、
$p=3$においては、$(k, x)=(1, 1)$と$(k, x)=(p-1, p-1)$、すなわち$(k, x)=(2, 2)$しかありません。
$p=3$においては、$(k, x)=(1, 1)$と$(k, x)=(p-1, p-1)$、すなわち$(k, x)=(2, 2)$しかありません。
$2≦k≦p-2$のときの$(1)$を満たす$p$未満の自然数$k,
x$の組についても考えます。
$2≦k≦p-2$のとき
$2≦k≦p-2$を満たす自然数が存在するのは$p≧5$のときなので、以降$p≧5$とします。
$2≦k≦p-2$を満たす自然数$k=a$をとると、性質①より、$(1)$を満たす$x$が必ず存在し、これを$x=b$とします。なお、$k=x$のときは$k=1,
p-1$のときだけなので、$a≠b$です。
すると、性質③より、$(k, x)=(a, b)$以外に$k=a$である組は存在しません。
すると、性質③より、$(k, x)=(a, b)$以外に$k=a$である組は存在しません。
次に、$k=b$をとると、上記より
そして、性質③より、$(k, x)=(b, a)$以外に$k=b$である組は存在しません。
\[ab\equiv1\pmod p\]
が成り立つことがわかっているので、$(1)$を満たす$x$として$x=a$があることがわかります。
そして、性質③より、$(k, x)=(b, a)$以外に$k=b$である組は存在しません。
以上のことより、$k, x$の区別をなくしたとき、$(1)$を満たす$2$以上$p-2$以下の自然数同士は必ず1対1対応になることがわかります。
すなわち、$2$以上$p-2$以下の自然数を、$(1)$を満たす2つの自然数の組に分けられるということです。
（$5$以上の素数は奇数なので、$p$未満の自然数の個数は偶数、$1$と$p-1$を除いても偶数です。
このことから、実際に$2$以上$p-2$以下の自然数をすべて使い、過不足なく2つの自然数の組に分けられることがわかります。）
また、$2$以上$p-2$以下の自然数は$p-3$個あり、これらは$(1)$を満たすように2つずつ組み合わせられます。したがって、$2$以上$p-2$以下の自然数の組の数は$\dfrac{p-3}{2}$個となります。
例えば、$p=31$のときの$(1)$を満たす$31$未満の自然数の組は、$(1, 1), (30,
30)$を含めて以下の16個となります。（$2$以上$29$以下の自然数からなる組み合わせは$\dfrac{31-3}{2}=14$個）
\begin{align*}\pmod{31}\\
(1,1)&&1\cdot1&=1\\[0.5em](2,16)&&2\cdot16&=32=31+1\\[0.5em](3,21)&&3\cdot21&=63=31\cdot2+1\\[0.5em](4,8)&&4\cdot8&=32=31+1\\[0.5em](5,25)&&5\cdot25&=125=31\cdot4+1\\[0.5em](6,26)&&6\cdot26&=156=31\cdot5+1\\[0.5em](7,9)&&7\cdot9&=63=31\cdot2+1\\[0.5em](10,28)&&10\cdot28&=280=31\cdot9+1\\[0.5em](11,17)&&11\cdot17&=187=31\cdot6+1\\[0.5em](12,13)&&12\cdot13&=156=31\cdot5+1\\[0.5em](14,20)&&14\cdot20&=280=31\cdot9+1\\[0.5em](15,29)&&15\cdot29&=435=31\cdot14+1\\[0.5em](18,19)&&18\cdot19&=342=31\cdot11+1\\[0.5em](22,24)&&22\cdot24&=528=31\cdot17+1\\[0.5em](23,27)&&23\cdot27&=621=31\cdot20+1\\[0.5em](30,30)&&30\cdot30&=900=31\cdot29+1\end{align*}
(2026/9)内容を修正しました。
Share:
