自然数 n = 2x + 1 (x ≧ 0: x ∈ Z)
自然数 2x + 1 が奇素数なのかどうかを判定します。
自然数 2x + 1 が合成数ならば、２つの奇数の積になっているので、
2s + 1, 2t + 1 (s ≧ 0, t ≧ 0: s, t ∈ Z) を考えると
2x + 1 = (2s + 1)(2t + 1) とおくと
2x + 1 が奇素数ならば、(s, t) = (x, 0), (0, x) の整数解をもつ。
2x + 1 が合成数ならば、(s, t) = (x, 0), (0, x) 以外の整数解をもつ。
そうすると、整数解が「2つの場合」と「２つ以上の場合」の格子点の問題と命題を置きかえることが出来る。
2x + 1 = 4st + 2(s + t) + 1
⇔ x = 2st + s + t
⇔ (2t + 1)s = x - t
⇔ s = (x - t)/(2t + 1)
s は整数と、s = 0, s = x 以外に整数解をもつためには、1 ≦ s ≦ x - 1 の範囲を考える
よって、 1 ≦ (x - t)/(2t + 1) であるので
分子 = x - t = a
分母 = 2t + 1 = b
1 ≦ a / b ⇔ b ≦ a
b ≦ a の条件で、t = 1, 2, 3, ..... , x - 1 までに、(x - t)/(2t + 1) に代入する
それが整数になるならば、x は合成数である。
整数がなければ、x は奇素数である。
※1 ≦ t ≦ x - 1 に対して、(x - t) と (2t + 1) が互いに素であればよいが、その条件式が見つからない。
これを、ExcelのVBA で素数判定するプログラムで動かすと、素数 (2x + 1) の判定が出来る。
＜具体例＞
合成数 15 = 3・5
2x + 1 = 15 ⇔ x = 7
t = 1 のとき、x - t = 7 - 1 = 6, 2t + 1 = 2 + 1 = 3, 2 ≦ 6 なので、a / b = 6 / 3 = 2
よって、s = 2より
(s, t) = (2, 1) なので、2s + 1 = 4 + 1 = 5, 2t + 1 = 2 + 1 = 3
奇素数 17
2x + 1 = 17 ⇔ x = 8
t = 1 のとき、x - t = 8 - 1 = 7, 2t + 1 = 2 + 1 = 3, 3 ≦ 7 なので、a / b = 7 / 3
t = 2 のとき、x - t = 8 - 2 = 6, 2t + 1 = 4 + 1 = 5, 5 ≦ 6 なので、a / b = 6 / 5
t = 3 のとき、x - t = 8 - 3 = 5, 2t + 1 = 6 + 1 = 7, 7 ≧ 5 なので、s ＜ 1 より
x = 8 のとき、奇素数である。
＜個人的な感想＞
奇素数を格子点の問題に置き換えることが出来る点が、面白いと思う。
(x - t) と (2t + 1) が互いに素の条件式が見つかると面白いと思う。
ただ、メルセンヌ数を判定するのには、向いていないと思う。
また、私のような発想は過去に誰かがしていると思うが、私の知る範囲では見たことはないです。
自然数 2x + 1 が奇素数なのかどうかを判定します。
自然数 2x + 1 が合成数ならば、２つの奇数の積になっているので、
2s + 1, 2t + 1 (s ≧ 0, t ≧ 0: s, t ∈ Z) を考えると
2x + 1 = (2s + 1)(2t + 1) とおくと
2x + 1 が奇素数ならば、(s, t) = (x, 0), (0, x) の整数解をもつ。
2x + 1 が合成数ならば、(s, t) = (x, 0), (0, x) 以外の整数解をもつ。
そうすると、整数解が「2つの場合」と「２つ以上の場合」の格子点の問題と命題を置きかえることが出来る。
2x + 1 = 4st + 2(s + t) + 1
⇔ x = 2st + s + t
⇔ (2t + 1)s = x - t
⇔ s = (x - t)/(2t + 1)
s は整数と、s = 0, s = x 以外に整数解をもつためには、1 ≦ s ≦ x - 1 の範囲を考える
よって、 1 ≦ (x - t)/(2t + 1) であるので
分子 = x - t = a
分母 = 2t + 1 = b
1 ≦ a / b ⇔ b ≦ a
b ≦ a の条件で、t = 1, 2, 3, ..... , x - 1 までに、(x - t)/(2t + 1) に代入する
それが整数になるならば、x は合成数である。
整数がなければ、x は奇素数である。
※1 ≦ t ≦ x - 1 に対して、(x - t) と (2t + 1) が互いに素であればよいが、その条件式が見つからない。
これを、ExcelのVBA で素数判定するプログラムで動かすと、素数 (2x + 1) の判定が出来る。
＜具体例＞
合成数 15 = 3・5
2x + 1 = 15 ⇔ x = 7
t = 1 のとき、x - t = 7 - 1 = 6, 2t + 1 = 2 + 1 = 3, 2 ≦ 6 なので、a / b = 6 / 3 = 2
よって、s = 2より
(s, t) = (2, 1) なので、2s + 1 = 4 + 1 = 5, 2t + 1 = 2 + 1 = 3
奇素数 17
2x + 1 = 17 ⇔ x = 8
t = 1 のとき、x - t = 8 - 1 = 7, 2t + 1 = 2 + 1 = 3, 3 ≦ 7 なので、a / b = 7 / 3
t = 2 のとき、x - t = 8 - 2 = 6, 2t + 1 = 4 + 1 = 5, 5 ≦ 6 なので、a / b = 6 / 5
t = 3 のとき、x - t = 8 - 3 = 5, 2t + 1 = 6 + 1 = 7, 7 ≧ 5 なので、s ＜ 1 より
x = 8 のとき、奇素数である。
＜個人的な感想＞
奇素数を格子点の問題に置き換えることが出来る点が、面白いと思う。
(x - t) と (2t + 1) が互いに素の条件式が見つかると面白いと思う。
ただ、メルセンヌ数を判定するのには、向いていないと思う。
また、私のような発想は過去に誰かがしていると思うが、私の知る範囲では見たことはないです。