已知正整数 $n\ge2$，所有与 $n$ 互质的正整数 $a$ 都有 $a^n\equiv a\pmod{n}$．证明：
【难度】
【出处】
2019年中科大自主招生(回忆)
【标注】
-
$n$ 没有平方因子．标注答案略解析由题意可知 $a^{n-1}\equiv1\pmod{n}$，取 $a=n-1$，则 $(-1)^{n-1}\equiv1\pmod{n}$，若 $n$ 是偶数，则只能 $n|2$，只能 $n=2$．
只考虑 $n$ 是奇数的情况， -
若 $n$ 的素因子个数不超过 $2$，则 $n$ 为素数．标注答案略解析若 $n$ 只有一个素因子，则只能 $n$ 为素数，由费马小定理，命题显然成立．
若 $n=pq$，其中 $p,q$ 为不同的奇素因子，则 $a^{pq-1}\equiv1\pmod{pq}$，
又 $\varphi(pq)=(p-1)(q-1)$，结合欧拉定理可得 $a^{(p-1)(q-1)}\equiv1\pmod{pq}$，
题目
问题1
答案1
解析1
备注1
问题2
答案2
解析2
备注2
