[数论] $n^9-n^3\equiv0 \mod{504}$

求证:$n^9-n^3\equiv0  \mod{504}$.
来自<初等数论100例>.pdf第22题

1# realnumber
$504=2^3\cdot3^2\cdot7$
然后Euler函数即可以解决问题

2# yes94
过程,这样怎么行,不会.

3# realnumber
试了一试，输入很麻烦，编辑检查也麻烦，做起来还也麻烦。
因为$\phi(7)=\phi(9)=6$，$\phi(8)=4$，
（1）$n^6\equiv1$ $(\mod 7)$，故$n^9\equiv n^3$ $(\mod {7})$，
（2）当$n\not\equiv 0，3，6$  $(\mod {9})$时，$n^6\equiv 1$ $(\mod {9})$，故$n^9\equiv n^3$ $(\mod {9})$；
     当$n\equiv 0，3，6$ $(\mod {9})$时，$n^4\equiv 1 (\mod {9})$不成立！
（3）还有$n^4\equiv1$ $(\mod {8})$还不一定成立，需要条件$n\not\equiv 0，2，4，6$  $(\mod {8})$
即便成立，如何证这个$n^9\equiv n^3$ $(\mod {7})$？还麻烦呢
笨办法就是穷举$n\equiv 0，1，2，3，4，5，6，7$ $(\mod {8})$
有没有好一点的办法？

4# yes94
欧拉函数不会用,我本来是打算分解因式类的做法,万一不行,就用你也想到的笨办法,$\mod 7,8,9$都穷举,貌似计算量也不大,烦琐倒是的.

$n^9-n^3=n^3(n^6-1)\equiv0 \mod7$, 费马小定理
$n^3(n-1)(n+1)(n^2-n+1)(n^2+n+1)\equiv0 \mod8$,$n$分奇数偶数讨论.
$n^3(n-1)(n+1)((n+1)^2-3n)((n-1)^2+3n)\equiv0 \mod9$,$n$按$\mod3$分类.
而$7,8,9$显然两两互素.所以原题成立.