解法① (Writer解)

\((A,M)=(N+1,N^2)\) が条件を満たします。

証明： \(\displaystyle (N+1)^n-1\equiv \sum_{k=1}^n \binom nkN^k\equiv nN\equiv 0\ \text{mod}\ N^2\iff n\equiv 0\ \text{mod}\ N\) から従います。

実装例(Python3)

解法② (Tester解)

まず、 \(P=kN+1\) が素数となる \(k\) を探します。これは、 \(k\) をランダムに取り、ミラー–ラビン素数判定法で \(P\) が素数か判定する乱択を繰り返すことで見つけることができます。

\(P\) は素数なので、 \(a^n\equiv 1\ \text{mod}\ P\) を満たす最小の正整数 \(n\) が \(P-1=kN\) であるような原始根 \(a\) が存在します。この原始根も乱択で探すことができます。

このとき、 \((A,M)=(a^k\ \text{mod}\ P, P)\) とすると条件を満たすことができます。

実装例(Python3)