Bueno no se si a alguien le interese pero es con la definicion de binomio.
\( (a+b)^n = \displaystyle\sum_{k=0}^n{a^{n-k}*b^k} \)
si nosotros distribuimos el modulo y usamos definicion queda
\( \displaystyle\sum_{k=0}^n{a^{n-k}*1} \mbox{ mod } a^2 + \displaystyle\sum_{k=0}^n{a^{n-k}*(-1)^k} \mbox{ mod } a^2 \)
si desplegamos esas sumas y distribuimos nos daremos cuenta que cualquier k>=2 exponente de a...sera divisible por a^2...luego solo quedan los que no se dejan dividir..
\( 1+\displaystyle\binom{n}{n-1}*a + (-1)^{n-1}*\displaystyle\binom{n}{n-1}*a + (-1)^n \)
luego si n es par
\( 1+na-na + 1=2 \)
si n es impar
\( 1+na + na - 1 = 2an \)
ahora bien...el patron que encontre es que si a era par se recorria hasta a..osea 0<n<a+1 y si a era impar 0<n<2a+1
Luego eso demora nada en cualquier computador.

pd: te me adelantaste un tris.
pd2: gracias
