\[\large a^{9074}\equiv{a^2}\pmod{19845}\]

How many integers \(a\) with \(1\leq{a}\leq1000\) satisfy the congruency above?

Extra Credit Question: How many integers \(a\) with \(1\leq{a}\leq1000\) satisfy the congruency \[\large a^{758}\equiv{a^2}\pmod{19845}\]

Inspiration here, here, and here.