Find all the natural numbers between $1 \leq a \leq 1000$ which fulfill $a^{11764} \equiv a^4\pmod{25725}$ [duplicate]

I am trying to prove this statement which is equivalent to show $n^{91} = n^7 \pmod{ 364}$. By splitting modulus theorem $n^{91} = n^7 \bmod 91$ and $\bmod 4$. Then I don’t know what to do next... Can anyone help me?

Solution 1:

It's a special case of below Euler-Fermat generalization with $\,e = 7,\, f = 84,\ \prod p_i^{e_i} = 2^2\cdot 7\cdot 13 $

Theorem $\ $ Suppose that $\ m\in \mathbb N\ $ has the prime factorization $\:m = p_1^{e_{1}}\cdots\:p_k^{e_k}\ $ and suppose that for all $\,i,\,$ $\ e_i\le e\ $ and $\ \phi(p_i^{e_{i}})\mid f.\ $ Then $\ m\mid a^e(a^f-1)\ $ for all $\: a\in \mathbb Z.$

Proof $\ $ If $\ p_i\mid a\ $ then $\:p_i^{e_{i}}\mid a^e\ $ by $\ e_i \le e.\: $ Else $\:a\:$ is coprime to $\: p_i\:$ so by Euler's phi theorem, $\!\bmod q = p_i^{e_{i}}\!: \ a^{\phi(q)}\equiv 1\,$ thus $\,a^f\equiv 1\, $ by $\: \phi(q)\mid f.\ $ Since all $\ p_i^{e_{i}}\,$ divide $\, a^e (a^f - 1)\ $ so too does their product $\,m\,$ by lcm = product for coprimes, or by unique prime factorization.

Examples $\ $ You can find many illuminating examples in prior questions, e.g. below

$\qquad\qquad\quad$ $24\mid a^3(a^2-1)$

$\qquad\qquad\quad$ $40\mid a^3(a^4-1)$

$\qquad\qquad\quad$ $88\mid a^5(a^{20}\!-1)$

$\qquad\qquad\quad$ $6p\mid a\,b^p - b\,a^p$