整数のべき乗の下二桁

オイラーの定理・Grok からの続き

問題がわかったようなわからないような場合は，プログラムに落とし込んでもらうほうがありがたい。

Ｑ（koshix）：

f(n,m)=mod(n^m,100) と定義します。(n=2,3,...，m=2,3,...)

この関数は最小の出発点をm_0(n)として，最小周期T(n)を持つことがわかっているとします。つまり，f(n,m_0+T(n))=f(n,m_0) です。このとき，m_0(n)とT(n)をnの式で表わすことができますか。できる範囲で構いませんけど。

Ａ（ChatGPT o3-mini-high）：

（57秒推論，たぶん正解，以下出力省略，m=2,3,...というのはこちらの入力ミスで，m=1,2,... でなければならないのだけれど，そのあたりは勝手に斟酌して話を進めてくれている。）

出発点：m0(n) = ...

周期：T(n) = ...

Ｑ（koshix）：

n,mを入力したときに，m0(n)とT(n)を求めるプログラムを作ってください。

Ａ（ChatGPT o3-mini-high）：

（できた！）

Ｑ（koshix）：

(1) n=0を入れるまで繰り返して入力を促すようにしてください。

(2) 2^2=4, ... 2^22=...4 のように，周期に対応する部分の結果もあわせて出力するようにしてください。

Ａ（ChatGPT o3-mini-high）：

（できた！）

import math

def ord25(n):

    """

    n と 25 が互いに素な場合に、25 を法とする乗法群における n の位数を返す。

    すなわち、最小の正整数 k で n^k ≡ 1 (mod 25) となる k。

    可能性のある値は 1, 2, 4, 5, 10, 20（φ(25)=20より）です。

    """

    if n % 5 == 0:

        return None  # n が5の倍数の場合、この関数は使いません

    for k in [1, 2, 4, 5, 10, 20]:

        if pow(n, k, 25) == 1:

            return k

    return 20  # 理論上ここには来ないはず

def compute_m0_T(n):

    """

    与えられた n に対して、f(n, m) = n^m mod 100 の

    出発点 m0(n) と周期 T(n) を計算する関数です。

    

    ・モジュロ4について:

      - n ≡ 2 (mod 4) の場合は、m0,4 = 2（m>=2から定常）

      - それ以外は m0,4 = 1

    ・モジュロ25について:

      - 5で割れるが25で割れない場合は m0,25 = 2（m>=2から0になる）

      - それ以外（すなわち 5と互いに素または25で割れる場合）は m0,25 = 1

      

    最終的な出発点は m0(n)=max(m0,4, m0,25) として計算します。

    

    周期は、各合同式での周期の最小公倍数として

      T(n) = lcm(T4(n), T25(n))

    とし、モジュロ4では

      - 奇数かつ n ≡ 3 (mod 4) の場合は T4 = 2、それ以外は T4 = 1

    また、モジュロ25では

      - n と 25 が互いに素なら ord25(n) を、5で割れる場合は T25 = 1 とします。

    """

    # モジュロ4での出発点

    m0_4 = 2 if n % 4 == 2 else 1

    # モジュロ25での出発点

    m0_25 = 2 if (n % 5 == 0 and n % 25 != 0) else 1

    m0 = max(m0_4, m0_25)

    # モジュロ4での周期 T4:

    T4 = 2 if (n % 2 == 1 and n % 4 == 3) else 1

    # モジュロ25での周期 T25:

    if n % 5 == 0:

        T25 = 1

    else:

        T25 = ord25(n)

    T = (T4 * T25) // math.gcd(T4, T25)

    return m0, T

def main():

    while True:

        try:

            n = int(input("整数 n を入力してください (終了するには 0 を入力): "))

        except ValueError:

            print("整数を入力してください。")

            continue

        

        if n == 0:

            break

        

        m0, T = compute_m0_T(n)

        print(f"\nn = {n} のとき:")

        print(f"  出発点 m0({n}) = {m0}")

        print(f"  周期 T({n}) = {T}")

        print("周期に対応する部分の結果:")

        # m0 から m0+T まで（両端を含む）で f(n, m) = n^m mod 100 の値を出力

        for m in range(m0, m0 + T + 1):

            result = pow(n, m, 100)

            print(f"  {n}^{m} = {result}")

        print("-" * 40)

    

    print("終了しました。")

if __name__ == "__main__":

    main()

======================================================

（出力結果）

整数 n を入力してください (終了するには 0 を入力):  16

n = 16 のとき:

  出発点 m0(16) = 1

  周期 T(16) = 5

周期に対応する部分の結果:

  16^1 = 16

  16^2 = 56

  16^3 = 96

  16^4 = 36

  16^5 = 76

  16^6 = 16

----------------------------------------

整数 n を入力してください (終了するには 0 を入力): 

Ｑ（koshix）：

このプログラムを利用して，T(n)のn=1...100 までのリスト，m0(n)の1...100までのリストを出力してください。

Ａ（ChatGPT 03-mini-high）：

（125秒考察の後，コードとその実行結果のリストを出力してくれた。微妙に欠損していたので，もとのコードを自分で改変して修正出力した。）

図：T(n)とm0(n)のリストプロット（n=1...100）

Grok3

オイラーの定理からの続き

イーロン・マスクが支配しているX（旧Twitter）からはなるべく遠ざかりたい。日本語で自分がフォローしている空間はそこまで荒れていないし，情報量も多いので悩ましいところだ。そのマスクが2023年7月に立ち上げたAI開発企業が xAIだ。 

xAIのチャットボットであるGrokは，Xの有料ユーザ向けに提供されているものだと思って無視していたが，いつの間にか Grok3 ベータ版がXの無料ユーザにも公開されていた。テストを誘導するための一時的な措置だろう。というわけで，この推論モデルの実力を試してみる。

図：Grokのアイコン（どこかから引用）

Tsujimotter が提起していた，「2の200乗の下2桁はいくつか？」の解法7選 にちなんだ問いだ。

Ｑ（koshix）：

整数m,nに対して，mod(n^m,100) がm=0,1,…に対して，周期的に振る舞うことを証明し，その周期のはじまるmの値が n によってどのように定まるかを求めてください。

Ａ（Grok3）：

（124行ほど考えて，微妙に誤りが含まれた生ぬるい回答を返してきた。論理的な推論というよりも，具体的な計算の試行錯誤のような印象を受ける）

Ａ（DeepSeek R1）：

（371秒かけて中国語で考察した後，ある程度妥当だけれど不完全な回答を中国語で返してきた。日本語に直してとお願いしたら，「服务器繁忙，请稍后再试。」だと。）

Ａ（Gemini 2.0 Flash Thinking Experimental）：

（253行ほど考えて，あまり整理されていない回答を返してきた。頭悪いのかと思ったが，最後の結論はもしかすると良いのかもしれない。自分自身の理解が不十分なのか？）

Ａ（ChatGPT o3-mini-highl）：

（37秒かけて日本語で考察した後，もっともらしい整理された答えを返してきた。）

ということで，Grok3は巷の一部の評判ほどのものではないようだ。DeepSeek R1も相変わらずイマイチなので，とりあえず様子見ながら，o3-mini-highを中心に使うのがよろし。

［１］xAIの世界最高性能AI「Grok 3」とは？料金プランや使い方を解説（Shift AI）

［２］（自由研究）20乗数の下2桁が自己同型数になるのはなぜ？（tsujimotterのノートブック）

オイラーの定理

フェルマーの小定理・オイラーの関数からの続き

大人を過ぎてから初めて目にした概念はなかなか覚えられない。フェルマーの小定理がそれだ。鈴木貫太郎の大学入試数学チャンネルもなくなってしまったので，なおさらだ。

フェルマーの小定理は，素数を$p$とし，$p$とたがいに素な整数を $a$（gcd($a, p$)=1）として，$a^{p-1} \equiv 1 \quad ({\rm mod}\ p)$ 。あれれ，gcd($a, p$)=1 をはずせば，$a^p \equiv a \quad ({\rm mod}\ p)$）でもいいのか。

証明は次のとおり。

整数 $a, x$，素数$p$とする。二項定理で$(x+1)^p$を展開すると，

$(x+1)^p = x^p + C_1^p x^{p-1} 1^1 + C_2^p x^{p-2} 1^2 + \cdots + C_{p-1}^p x^1 1^{p-1} + 1^p$

ところで，上式の$C_k^{p-k}=\dfrac{p!}{k! (p-k)!}$であり，分母の$k<p, \ p-k < p\ $には分子の$\ p \ $を割り切る数は含まれていない。したがって，$(x+1)^p \equiv x^p+1 \quad ({\rm mod} \ p) $ である。

これから，$a^p \equiv (1+(a-1))^p \equiv 1 + (a-1)^p \quad ({\rm mod}\ p ) $

$a^p \equiv 1+ (a-1)^p \equiv 1+ 1 + (a-2)^p \equiv \cdots \equiv  a + 0^p  \quad ({\rm mod} \ p ) $

$a$と$p$は互いに素なので，両辺を$a$で割って，$a^{p-1} \equiv 1 \quad ({\rm mod} \ p) $

オイラーの定理は，フェルマーの小定理のべきの素数部分を拡張したものに相当する。

正の整数$m$に対して，集合$\ r(m) = \{a\ |\ 1 \le a \le m, \ {\rm gcd} (a, m) = 1\} $ を考え，その要素数をオイラー数 $\varphi(m)= \#r(m)$  とよんでいる。そこで，$r(m) = \{r_1, r_2, \cdots, r_{\varphi(m)} \}$。なお，$p$に対して，$\varphi(p) = p -1$。

集合 $r(m)$のすべての要素に$a$をかけて，${\rm mod}\  m$ をとれば，その集合 $ar(m) = \{ a r_1, a r_2, \cdots, a r_{\varphi(m)} \}$ は $r(m) = \{r_1, r_2, \cdots, r_{\varphi(m)} \}$と等しくなる。そこで，これらの要素の積を考えると，$ a^{\varphi(m)} \Pi_{i=1}^{\varphi(m)} r_i \equiv \Pi_{i=1}^{\varphi(m)} r_i \quad ({\rm mod }\ m )$ なので，

オイラーの定理，$a^{\varphi(m)} \equiv 1 \quad  ({\rm mod }\ m )\ $ が得られる。

（注）なお，$ar(m) = \{ a r_1, a r_2, \cdots, a r_{\varphi(m)} \} \quad ({\mod \ m }) \equiv \{ r'_1, r'_2, \cdots, r'_{\varphi(m)} \} \ $の要素$\ r'_i \ $はすべて，$a, m$と互いに素であり，同じものは含まれない。

(1) $p, q$を素数として，$m=p q\ $である場合，$\varphi(m) = \varphi(p) \varphi(q)$ となる。

$\varphi(m)\ $は，$\{1,2, \cdots, m \}$から，$p$の倍数と$q$の倍数を除いたものになるので，それぞれ，$q$個，$p$個あるが，$p q$は両方で重なっている。そこで，$p, q$の倍数でないものの個数は，$ \varphi(m) = pq -p - q +1 = (p-1) (q-1) = \varphi(p) \varphi(q) $ となる。3個以上の場合も同様。

(2) $p$ を素数，$k$を正整数として，$m = p^k\ $である場合，$\varphi(m) = p^k - p^{k-1} \ $ となる。これは，$\{ 1, 2, \cdots , p^k \} $ の中で，$ \{ 1 p, 2 p, \cdots , p^{k-1} p\}$ は$m$と互いに素でないので，その個数を引けばよいからだ。

(3) これらを組み合わせると，$m = p_1^{k_1} p_2^{k_2} \cdots p_n^{k_n}\ $ として，$\varphi(m) = m (1-1/p_1) (1-1/p_2) \cdots (1-1/p_n) $ となる。

図：オイラーのファイ関数のグラフ（Wikipediaから引用）

［１］オイラー関数の定義・性質４つとその証明（数学の景色）

［２］オイラーのファイ関数のイメージ（高校数学の物語）

終戦の詔勅

日本でラジオ放送が始まって100年，NHKでは放送100年として様々な資料映像を流している。そのなかに，名物アナウンサーの和田信堅（1912-1952）の映像があった。

和田は，双葉山69連勝でストップの放送でも有名だが，1945年8月15日正午からの玉音放送の担当であり，終戦の詔勅の朗読をしていた。あれは，裕仁天皇の玉音盤を流しただけかと思っていた。それだけではわかりにくかったからか，アナウンサーによる朗読や解説などで補っていたのだ。

1967年の夏，中学生の頃に家族でみた「日本のいちばん長い日」の映画ではじめて玉音放送を巡るエピソードを知ることになった。映画では日本放送協会の関係者も奮闘していたが，放送員（アナウンサー）として，加山雄三（1937-）が館野守男，小泉博（1926-2015）が和田信堅を演じていた。東宝のゴジラ映画でもおなじみの小泉は元NHKアナウンサーだったのか。

写真：玉音盤の副盤（Wikipediaから引用）

［１］厳禁の広告放送（和田信賢）