ささきしき

チラシの表

【学習ノート】「原始元」

ご無沙汰しております。奏汰です。 今回は普段と趣の異なる、まじめなお勉強回です。

友人に何通もメールで説明するのも面倒だし、私の(こっそり)尊敬している先輩も、以前ブログで解説とか出題とかやってたなぁと思ったら、わりとこういうのもありじゃないかな、と。
そんなわけで、学友向けかつ自身の復習用のざっくり講座。今回は「原始元」です。
なお予め断っておきますが、当コンテンツはあくまで「課題の補助となる知識の提供」であり、定義を正しく理解したい方などには向きません。
本職の方の訂正もどしどし募集しております。優しくマサカリを投げていただければと思います。

さて、原始元とは何ぞやという事ですが。
細かい話はセキュリティアカデメイア様の「原始元」(別ウィンドウで開きます)を見ていただく事として。 つまりは「素数Nの原始元は何か?」と問われたときは、 「1からN-1までの整数xについて、{xN-1÷N}の余りがはじめて1になる数(たち)です」というのが答え。

例として、素数13の原始元を求めたのが以下の画像。
ord13(g)=12
縦軸(青)が整数x、横軸(灰)が指数にあたる。 表の中で赤くなっているのが、13で割った余りが1になった箇所。 そして、指数が12になったときに初めて1が出ているのは、{2,6,7,11}の4つ。 つまりこの4数が「素数13の原始元」という事になる。

で、導出方法。
絶対あるはずなんだけど、やる気のない小生にはよく分かりませんでしたので、総当りしました。
ところで、さっきの画像を見直してほしい。こいつをどう思う?
すごく…大きいです対称的です…。
ということで、深緑の太枠、つまり1/4くらいの計算だけやってしまえば、あとは推測で埋まるのではないか、という屁理屈。
一応それでも間違った数字は出せないので、今回に限っては使えそうです。
そういうわけで、6*6=36回の乗算と除算。
電卓使用可ですし、たぶん問題ないんじゃないですかね。

【追記:2014/06/20】
そんなものはなさそうだった。
1乗は自明なので、2乗からスタートして、「答えが1になる」or「N-2乗まで一度も答えが1にならない」のどちらかを達成するまで繰り返す、という事になりそう。ちなみに先の例では、 [2(原始元)],[3(3乗で1)],[4(6乗で)],[5(4乗)],[6(原始元)],[7(原始元)],[8(4乗)],[9(3乗)],[10(6乗)],[11(原始元)],[12(2乗)] ということなので、全部で…61回かな?
もっと減りそうな気がするなぁ。