Solution 1

Set \((A,M) = (N+1, N^2)\). This pair satisfies the conditions.

Proof:
\(\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\), from which the claim holds.

Sample Implementation (Python3)

Solution 2 (by Tester)

First, find a \(k\) such that \(P = kN + 1\) is prime. You can attempt random values of \(k\) and check whether \(P\) is prime using the Miller–Rabin primality test.

Since \(P\) is prime, there exists a primitive root \(a\) modulo \(P\) such that the smallest positive integer \(n\) with \(a^n \equiv 1 \pmod{P}\) is \(P-1 = kN\). You can also find such a primitive root using a randomized search.

Then, set \((A,M)=(a^k\ \text{mod}\ P, P)\), which satisfies the conditions.

Sample Implementation (Python3)