整数のべき乗の下二桁

オイラーの定理・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）