Euler gone wild, again

We will show that this congruency holds for all positive integers $a$ , so that the answer to our puzzle here is $\boxed{1000}.$

We have the prime factorization $n=25725=3\times{5^2}\times7^3=3\times{25}\times{343}$ . The given congruency holds modulo 25725 if (and only if) it holds modulo 3, 25, and 343. We will examine the case 343; the other two cases are analogous.

If 7 does not divide $a$ , then Euler's theorem gives $a^{\phi(343)}=a^{294}\equiv1 \pmod{343}$ so $a^{11760}=a^{294\times40}\equiv1$ and $a^{11763}\equiv{a^3}\pmod{343}$ as claimed. If 7 divides $a$ , then $7^3=343$ will divide $a^3$ , so that $a^{11763}\equiv{0}$ $\equiv{a^3}\pmod{343}.$

Or we can use this Corollary to Euler's Theorem. As it often happens in Math, it is easier to prove the Corollary and apply it to this special case than to deal with the special case with all its messy numbers.

This is true for any $a$ relatively prime to $25725 = 3 \cdot 5^2 \cdot 7^3$ by Euler's Theorem (since $\varphi(25725) = 11760$ ).

It's also true for $a = 7$ because the two sides are congruent to $0$ mod $7^3$ and congruent to each other mod $3 \cdot 5^2$ by Euler again, so they're congruent modulo the product by the Chinese Remainder Theorem. A similar argument works for $a = 5$ and $a = 3$ .

Now if the statement is true for $b$ and true for $c$ , it's true for $bc$ . So the above two paragraphs imply that it's true for all $a$ ; the answer is $\fbox{1000}$ .