Euler gone wild, one last time

$19845=3^4\cdot 5\cdot 7^2$ . $\$ Use Euler's theorem and cases.

$7\mid a\,\Rightarrow\, a^{9074}\equiv a^2\equiv 0\pmod{\! 7^2}$

$7\nmid a\,\Rightarrow\, a^{9074}\equiv a^{9074\pmod{\!\varphi(7^2)}}\equiv a^{2}\pmod{\! 7^2}$ .

$5\mid a\,\Rightarrow\, a^{9074}\equiv a^2\equiv 0\pmod{\! 5}$

$5\nmid a\,\Rightarrow\, a^{9074}\equiv a^{9074\pmod{\! 4}}\equiv a^2\pmod{\! 5}$

$3\nmid a\,\Rightarrow\, a^{9074}\equiv a^{9074\pmod{\! \varphi(3^4)}}\equiv a^2\pmod{\! 3^4}$

$3\mid a,\ 9\mid a\,\Rightarrow\, a^{9074}\equiv a^2\equiv 0\pmod{\! 3^4}$

$3\mid a,\ 9\nmid a\,\Rightarrow\, a^{9074}\equiv 0$ and $a^{2}\not\equiv 0\pmod{\! 3^4}$

$3\mid a,\ 9\nmid a$ is the only case when $a^{9074}\equiv a^2\pmod{\!19845}$ doesn't hold.

There are $222$ such $a$ 's with $1\le a\le 1000$ . They are:

$1\cdot 3,\, 2\cdot 3,\, 4\cdot 3,\, 5\cdot 3,\, 7\cdot 3,\, 8\cdot 3,\ldots, 331\cdot 3,\, 332\cdot 3$

So answer: $1000-222=778$ .

In the same way in the extra credit question we know $a$ doesn't satisfy it iff $\upsilon_3 (a)=1$ just like before, which is the notation for $3^1\mid a,\, 3^2\nmid a\,$ (i.e. $3^1$ is the highest power of $3$ diving $a$ . See LTE paper ).

There are $222$ such $a$ 's with $1\le a\le 1000$ , as shown above.

Answer: $1000-222=778$ .