Loading web-font TeX/Math/Italic
横画面推奨!
モバイル機器の場合、数式が見切れる場合があります。

2024年12月17日

ある素数未満の自然数の倍数をある素数で割ったときの余りの性質

 素数pp未満の任意の自然数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のとき

 p>2のときは、「倍数を互いに素な自然数で割ったときの余りの性質」を利用します。
素数pp未満の自然数kは互いに素です。
したがって、次のことがいえます。
kの倍数k,2k,\cdots,(p-1)k,pkをそれぞれpで割ったときの余りを一列に並べたものは0,1,\cdots,p-2,p-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の中に必ず1つだけpで割ったときの余りが1となるものが含まれているということなので、(1)を満たすp未満の自然数xが必ず1つだけ存在することがわかります。

以上より、冒頭の性質
性質2:
素数pp未満の任意の自然数kについて
\large kx\equiv1\pmod p
を満たすp未満の自然数xが必ず存在する
という性質があることがわかります。

 次は、(1)を満たす2つの因数の組み合わせについて調べてみます。
相異なるp未満の自然数a,bの積abaの倍数かつbの倍数であるといえます。
(1)kx=abを代入して
ab\equiv1\pmod p
が成り立つとき、kxに代入して(1)を満たすaの倍数はab以外になく、同様に(1)を満たすbの倍数もまたabしかないということが性質1よりいえます。
したがって、以下のことがいえます。
性質3:
(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において
\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*}
となり、自身しか含まない組み合わせは(1,1),(p-1,p-1)の2つしかないことがわかります。

他の組み合わせ

 性質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:
share
◎Amazonのアソシエイトとして、当サイト「数学について考えてみる」は適格販売により収入を得ています。
Powered by Blogger.

PR

blogmura_pvcount
ブログランキング・にほんブログ村へ