ご無沙汰しております。奏汰です。 今回は普段と趣の異なる、まじめなお勉強回です。
友人に何通もメールで説明するのも面倒だし、私の（こっそり）尊敬している先輩も、以前ブログで解説とか出題とかやってたなぁと思ったら、わりとこういうのもありじゃないかな、と。
そんなわけで、学友向けかつ自身の復習用のざっくり講座。今回は「原始元」です。
なお予め断っておきますが、当コンテンツはあくまで「課題の補助となる知識の提供」であり、定義を正しく理解したい方などには向きません。
本職の方の訂正もどしどし募集しております。優しくマサカリを投げていただければと思います。
さて、原始元とは何ぞやという事ですが。
細かい話はセキュリティアカデメイア様の「原始元」(別ウィンドウで開きます)を見ていただく事として。
つまりは「素数Nの原始元は何か？」と問われたときは、
「1からN-1までの整数xについて、{xN-1÷N}の余りがはじめて1になる数（たち）です」というのが答え。
例として、素数13の原始元を求めたのが以下の画像。
縦軸（青）が整数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回かな？
もっと減りそうな気がするなぁ。
