素数pとp未満の任意の自然数kについて
という性質があります。
\begin{equation}\large kx\equiv1\pmod p\end{equation}
を満たすp未満の自然数xが必ず存在する
これが成り立つことを確かめてみます。
これは、p未満の自然数同士の積の中にpで割ったときの余りが1になるものが必ず存在することを主張しています。
p=2のとき
p=2のとき、p未満の自然数は1だけなのでk=1。
x\equiv1\pmod2
を満たすx=1が存在することがわかります。
p>2のとき
したがって、次のことがいえます。
kの倍数k,2k,\cdots,(p-1)k,pkをそれぞれpで割ったときの余りを一列に並べたものは0,1,\cdots,p-2,p-1の並び替えである。
ここで、必ず
これはすなわち、kの倍数k,2k,\cdots,(p-2)k,(p-1)kの中に必ず1つだけpで割ったときの余りが1となるものが含まれているということなので、(1)を満たすp未満の自然数xが必ず1つだけ存在することがわかります。
pk\equiv0\pmod p
であることに着目すれば
性質1:
kの倍数k,2k,\cdots,(p-2)k,(p-1)kをそれぞれpで割ったときの余りを一列に並べたものは1,2,\cdots,p-2,p-1の並び替えである。
ということがいえます。kの倍数k,2k,\cdots,(p-2)k,(p-1)kをそれぞれpで割ったときの余りを一列に並べたものは1,2,\cdots,p-2,p-1の並び替えである。
これはすなわち、kの倍数k,2k,\cdots,(p-2)k,(p-1)kの中に必ず1つだけpで割ったときの余りが1となるものが含まれているということなので、(1)を満たすp未満の自然数xが必ず1つだけ存在することがわかります。
以上より、冒頭の性質
性質2:
素数pとp未満の任意の自然数kについて
という性質があることがわかります。
素数pとp未満の任意の自然数kについて
\large kx\equiv1\pmod p
を満たすp未満の自然数xが必ず存在する
次は、(1)を満たす2つの因数の組み合わせについて調べてみます。
相異なるp未満の自然数a,bの積abはaの倍数かつbの倍数であるといえます。
(1)にkx=abを代入して
(1)にkx=abを代入して
ab\equiv1\pmod p
が成り立つとき、kxに代入して(1)を満たすaの倍数はab以外になく、同様に(1)を満たすbの倍数もまたabしかないということが性質1よりいえます。
したがって、以下のことがいえます。
性質3:
(1)を満たす因数の組み合わせの中に(a,b)以外にa,bを含む組み合わせが存在しない。
(1)を満たす因数の組み合わせの中に(a,b)以外にa,bを含む組み合わせが存在しない。
ところで、(1)を満たす因数の組み合わせの中でpによらず変わらないものが存在します。
それは、1またはp-1を含む組み合わせです。
1を含む組み合わせ
もう一方の因数をxとします。
1\equiv1\pmod p
なので、
x\equiv1\pmod p
を満たすものとして自明なのはx=1であり、性質3より唯一のxの値となります。
したがって、1を含む組み合わせは必ず(1,1)となります。
p-1を含む組み合わせ
もう一方の因数をyとします。
p-1\equiv-1\pmod p
より、
(p-1)y\equiv1\pmod p
を満たすものにはy=p-1があり、性質3より唯一のyの値となります。
したがって、p-1を含む組み合わせは必ず(p-1,p-1)となります。
他に自身しか含まない組み合わせが存在するかを調べてみると、
(1)にx=kを代入すると、\mod pにおいて
となり、自身しか含まない組み合わせは(1,1),(p-1,p-1)の2つしかないことがわかります。
\begin{align*}k^2\equiv1\\[0.5em]k^2-1\equiv0\\[0.5em](k+1)(k-1)\equiv0\\[0.5em]k\equiv\pm1\equiv1,p-1\end{align*}
他の組み合わせ
性質2よりそれぞれの自然数に対になる自然数が必ず存在し、性質3より一度組み合わせに現れた自然数は再び現れないことがわかります。
すると、(1,1),(p-1,p-1)より1,p-1は他の組み合わせには現れず、残る2,3,\cdots,p-3,p-2の中から2個ずつ取り出して組み合わせをつくることになります。
p>2ならば素数pは奇数なので、p未満の自然数1,2,\cdots,p-2,p-1の数は偶数、1,p-1を除いた2,3,\cdots,p-3,p-2の数も偶数なので、過不足なくすべての自然数を使って組み合わせをつくることができます。
できる組み合わせの数は、2,3,\cdots,p-3,p-2の個数p-3個の半分の\dfrac{p-3}{2}個です。
したがって、kxに代入して(1)を満たすことができるp未満の自然数による因数の組み合わせの数は全部で\dfrac{p+1}{2}個となります。
例えば、p=31のとき(1)を満たす組み合わせは1から30までの自然数をすべて使って以下の16個ができます。
\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*}
Share: