ある素数未満の自然数の倍数をある素数で割ったときの余りの性質 ~ 数学について考えてみる

　素数

p

$p$ と

p

$p$ 未満の任意の自然数

k

$k$ について

\begin{matrix} (1) & k x \equiv 1 (\mod p) \end{matrix}

$\begin{equation}\large kx\equiv1\pmod p\end{equation}$

を満たす

p

$p$ 未満の自然数

x

$x$ が必ず存在する

という性質があります。

これが成り立つことを確かめてみます。

　これは、

p

$p$ 未満の自然数同士の積の中に

p

$p$ で割ったときの余りが

1

$1$ になるものが必ず存在することを主張しています。

$p=2$ のとき

p = 2

$p=2$ のとき、

p

$p$ 未満の自然数は

1

$1$ だけなので

k = 1

$k=1$ 。

x \equiv 1 (\mod 2)

$x\equiv1\pmod2$

を満たす

x = 1

$x=1$ が存在することがわかります。

$p>2$ のとき

p > 2

$p>2$ のときは、「倍数を互いに素な自然数で割ったときの余りの性質」を利用します。
素数

p

$p$ と

p

$p$ 未満の自然数

k

$k$ は互いに素です。

したがって、次のことがいえます。

k

$k$ の倍数

k, 2 k, \dots, (p - 1) k, p k

$k,2k,\cdots,(p-1)k,pk$ をそれぞれ

p

$p$ で割ったときの余りを一列に並べたものは

0, 1, \dots, p - 2, p - 1

$0,1,\cdots,p-2,p-1$ の並び替えである。

ここで、必ず

p k \equiv 0 (\mod p)

$pk\equiv0\pmod p$

であることに着目すれば

性質1：

k

$k$ の倍数

k, 2 k, \dots, (p - 2) k, (p - 1) k

$k,2k,\cdots,(p-2)k,(p-1)k$ をそれぞれ

p

$p$ で割ったときの余りを一列に並べたものは

1, 2, \dots, p - 2, p - 1

$1,2,\cdots,p-2,p-1$ の並び替えである。

ということがいえます。
これはすなわち、

k

$k$ の倍数

k, 2 k, \dots, (p - 2) k, (p - 1) k

$k,2k,\cdots,(p-2)k,(p-1)k$ の中に必ず1つだけ

p

$p$ で割ったときの余りが

1

$1$ となるものが含まれているということなので、

(1)

$(1)$ を満たす

p

$p$ 未満の自然数

x

$x$ が必ず1つだけ存在することがわかります。

以上より、冒頭の性質

性質2：
素数

p

$p$ と

p

$p$ 未満の任意の自然数

k

$k$ について

k x \equiv 1 (\mod p)

$\large kx\equiv1\pmod p$

を満たす

p

$p$ 未満の自然数

x

$x$ が必ず存在する

という性質があることがわかります。

　次は、

(1)

$(1)$ を満たす2つの因数の組み合わせについて調べてみます。

相異なる

p

$p$ 未満の自然数

a, b

$a,b$ の積

a b

$ab$ は

a

$a$ の倍数かつ

b

$b$ の倍数であるといえます。

(1)

$(1)$ に

k x = a b

$kx=ab$ を代入して

a b \equiv 1 (\mod p)

$ab\equiv1\pmod p$

が成り立つとき、

k x

$kx$ に代入して

(1)

$(1)$ を満たす

a

$a$ の倍数は

a b

$ab$ 以外になく、同様に

(1)

$(1)$ を満たす

b

$b$ の倍数もまた

a b

$ab$ しかないということが性質1よりいえます。

したがって、以下のことがいえます。

性質3：

(1)

$(1)$ を満たす因数の組み合わせの中に

(a, b)

$(a,b)$ 以外に

a, b

$a,b$ を含む組み合わせが存在しない。

ところで、

(1)

$(1)$ を満たす因数の組み合わせの中で

p

$p$ によらず変わらないものが存在します。

それは、

1

$1$ または

p - 1

$p-1$ を含む組み合わせです。

$1$ を含む組み合わせ

　もう一方の因数を

x

$x$ とします。

1 \equiv 1 (\mod p)

$1\equiv1\pmod p$

なので、

x \equiv 1 (\mod p)

$x\equiv1\pmod p$

を満たすものとして自明なのは

x = 1

$x=1$ であり、性質3より唯一の

x

$x$ の値となります。

したがって、 $1$ を含む組み合わせは必ず $(1,1)$ となります。

$p-1$ を含む組み合わせ

　もう一方の因数を

y

$y$ とします。

p - 1 \equiv - 1 (\mod p)

$p-1\equiv-1\pmod p$

より、

(p - 1) y \equiv 1 (\mod p)

$(p-1)y\equiv1\pmod p$

を満たすものには

y = p - 1

$y=p-1$ があり、性質3より唯一の

y

$y$ の値となります。

したがって、 $p-1$ を含む組み合わせは必ず $(p-1,p-1)$ となります。

他に自身しか含まない組み合わせが存在するかを調べてみると、

(1)

$(1)$ に

x = k

$x=k$ を代入すると、

\mod p

$\mod p$ において

\begin{aligned} k^{2} \equiv 1 \\ k^{2} - 1 \equiv 0 \\ (k + 1) (k - 1) \equiv 0 \\ k \equiv \pm 1 \equiv 1, p - 1 \end{aligned}

$\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)

$(1,1),(p-1,p-1)$ の2つしかないことがわかります。

他の組み合わせ

　性質2よりそれぞれの自然数に対になる自然数が必ず存在し、性質3より一度組み合わせに現れた自然数は再び現れないことがわかります。

すると、

(1, 1), (p - 1, p - 1)

$(1,1),(p-1,p-1)$ より

1, p - 1

$1,p-1$ は他の組み合わせには現れず、残る

2, 3, \dots, p - 3, p - 2

$2,3,\cdots,p-3,p-2$ の中から2個ずつ取り出して組み合わせをつくることになります。

p > 2

$p>2$ ならば素数

p

$p$ は奇数なので、

p

$p$ 未満の自然数

1, 2, \dots, p - 2, p - 1

$1,2,\cdots,p-2,p-1$ の数は偶数、

1, p - 1

$1,p-1$ を除いた

2, 3, \dots, p - 3, p - 2

$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

$p=31$ のとき

(1)

$(1)$ を満たす組み合わせは

1

$1$ から

30

$30$ までの自然数をすべて使って以下の16個ができます。

\begin{aligned} (\mod 31) \\ (1, 1) & 1 \cdot 1 & = 1 \\ (2, 16) & 2 \cdot 16 & = 32 = 31 + 1 \\ (3, 21) & 3 \cdot 21 & = 63 = 31 \cdot 2 + 1 \\ (4, 8) & 4 \cdot 8 & = 32 = 31 + 1 \\ (5, 25) & 5 \cdot 25 & = 125 = 31 \cdot 4 + 1 \\ (6, 26) & 6 \cdot 26 & = 156 = 31 \cdot 5 + 1 \\ (7, 9) & 7 \cdot 9 & = 63 = 31 \cdot 2 + 1 \\ (10, 28) & 10 \cdot 28 & = 280 = 31 \cdot 9 + 1 \\ (11, 17) & 11 \cdot 17 & = 187 = 31 \cdot 6 + 1 \\ (12, 13) & 12 \cdot 13 & = 156 = 31 \cdot 5 + 1 \\ (14, 20) & 14 \cdot 20 & = 280 = 31 \cdot 9 + 1 \\ (15, 29) & 15 \cdot 29 & = 435 = 31 \cdot 14 + 1 \\ (18, 19) & 18 \cdot 19 & = 342 = 31 \cdot 11 + 1 \\ (22, 24) & 22 \cdot 24 & = 528 = 31 \cdot 17 + 1 \\ (23, 27) & 23 \cdot 27 & = 621 = 31 \cdot 20 + 1 \\ (30, 30) & 30 \cdot 30 & = 900 = 31 \cdot 29 + 1 \end{aligned}

$\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*}$