已知正整数 $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