原始根についてのちょっとした推論を見つけました.
スポンサーリンク
原始根のおさらい
原始根についてはこのブログで何度も登場しました.
簡単に説明すれば以下になります.
[定義:原始根]
素数 と,
で割り切れない整数
について,
が指数
に対応するとき, つまり
よりも小さな正指数で
とならないとき,
を
の原始根と呼ぶ.
以前紹介した通り, 素数 における原始根は
個あり, 一つ原始根を見つければ後は芋づる式に見つけることができます.
しかしこの「与えられた素数からその原始根を任意に一つ求める簡単な方法」は(おそらく)まだ見つかっていません.
と順に検証するしかないんですね.
素数とその原始根の関係
今回はそんな「素数からその原始根を見つけること」ではなく, 素数とその複数ある原始根(3は1つなので除く)についての関係です.
たまたま昨晩思いついたレベルなのでもっと深い関係があるかもしれません.
まず5以上の素数とその原始根を小さい順に見てみましょう.
とりあえず まで書いておきます.
素数 | 原始根 |
---|---|
5 | 2,3 |
7 | 3,5 |
11 | 2,6,7,8 |
13 | 2,6,7,11 |
17 | 3,5,6,7,10,11,12,14 |
19 | 2,3,10,13,14,15 |
これを見るだけでははじめは何も思いつかないかもしれません.
では素数 における原始根を小さい順に並べたものを
とします.
上の図表から, 素数 によっては両端沿いに足し合わせると元の素数
に等しくなることがわかります.
例えば の場合
であり,
ですね.
つまり以下が考えられます.
[推論1]
任意の について
となるような素数 が存在する.
しかし例えば の場合は
で,
ということでズレています.
この のような例は他にも
とたくさんあります.
これらの素数にどのような性質があるでしょうか?
φ(p-1)から特徴を見る
素数 の原始根の個数が
であることから,
に着目すると以下になりました.
素因数分解 | OK? | ||
---|---|---|---|
◯ | |||
× | |||
× | |||
◯ | |||
◯ | |||
|
× | ||
|
× | ||
◯ | |||
× | |||
◯ | |||
◯ | |||
× | |||
× |
素因数分解 | OK? | ||
---|---|---|---|
◯ | |||
× | |||
◯ | |||
× | |||
× | |||
◯ | |||
× | |||
× | |||
◯ | |||
◯ |
ここまでくれば分かりますよね.
上の性質が成り立つ素数 は,
が
で割り切れることが条件であると推測されます.
推論から導かれること
この推論から, 対応する素数 は
を満たしていることがわかります.
つまり推論は以下に書き換えられます.
[推論2]
を満たす素数
と任意の
について
が成り立つ.
因みに であることから, 平方剰余の第一補充法則よりこのような
は
であり, また次の二次合同方程式が解を持つ必要十分条件でもあります.
なお という形の素数は
または
という形であることは合同式を用いて比較的簡単に導けるのですが, 逆は成り立ちません.
〆
というわけで証明に至ることはまだ出来ていませんが興味深かったので書いてみました.
型の素数にも似たような性質があるかもしれませんね.