所有整数a和质数p，a^p-1等于什么除以p余数？

欧拉定理以及费马小定理的证明 前言 好久没有刷过数论的题了，感觉之前证明过的一些东西都有些忘记了，正好最近在重新学数论，就顺便记下一些定理及证明。 欧拉定理的证明 先写欧拉定理是因为费马小定理本身就是欧拉定理的一个特例，其证明过程本质上是一致的。 Description : \[若正整数\:a,n\:互质，则\:a^{\varphi(n)}\equiv 1\:(mod\:n) \] 准备知识： 前置小芝士🧀： 同余的性质：自反性、对称性、传递性、同加性、同乘性、同幂性等。 自反性：\(a\equiv a\:(mod\:m)\) 对称性：若 \(a\equiv b\:(mod\:m)\) ，则 \(b\equiv a\:(mod\:m)\) 传递性：若 \(a\equiv b\:(mod\:m),b\equiv c\:(mod\:m)\) ，则 \(a\equiv c\:(mod\:m)\) 同加性：若 \(a\equiv b\:(mod\:m)\) ，则 \(a+c\equiv b+c\:(mod\:m)\) 同乘性： 若 \(a\equiv b\:(mod\:m)\) ，则 \(a\times c\equiv b\times c\:(mod\:m)\) 若 \(a\equiv b\:(mod\:m),c\equiv d\:(mod\:m)\) ，则 \(a\times c\equiv b\times d\:(mod\:m)\) 同幂性：若 \(a\equiv b\:(mod\:m)\) ，则 \(a^n\equiv b^n\:(mod\:m)\) 完全剩余系以及简化剩余系的概念 引理 \(1\) ： 若 \(a,b,c\) 为任意 \(3\) 个整数，\(m\) 为正整数，且 \(m\) 与 \(c\) 互质，则当 \(a\cdot c\equiv b\cdot c\:(mod\:m)\) 时，有 \(a\equiv b\:(mod\:m)\) 证明：\(a\cdot c\equiv b\cdot c\:(mod\:m)\) 可得 \(ac-bc\equiv 0\:(mod\:m)\) ，即 \((a-b)\cdot c\equiv 0\:(mod\:m)\) 。因为 \(m\) 与 \(c\) 互质，所以 \(c\) 不可能为 \(m\) 的倍数，即 \(a-b\equiv 0\:(mod\:m)\) ，所以 \(a\equiv b\:(mod\:m)\) 。 证毕。 引理 \(2\) ： 若 \(a,b\) 属于 \(m\) 的简化剩余系，那么 \(a\times b\) 仍属于 \(m\) 的简化剩余系（即 \(m\) 的简化剩余系关于模 \(m\) 乘法封闭）。 证明：若 \(a,b\) 与 \(m\) 互质，即 \(a,b\) 不含有与 \(m\) 相同的质因子，那么 \(a\times b\) 也不可能与 \(m\) 含有相同的质因子，即 \(a\times b\) 也与 \(m\) 互质，所以 \(a\times b\) 仍属于 \(m\) 的简化剩余系。 证毕。 引理 \(3\) ： 若 \(n\) 与 \(m\) 互质，且 \(\left\{\overline{a_1},\overline{a_2},\overline{a_3},\cdots,\overline{a_m}\right\}\) 为 \(m\) 的完全剩余系，则 \(\left\{\overline{na_1},\overline{na_2},\overline{na_3},\cdots,\overline{na_m}\right\}\) 也构成 \(m\) 的完全剩余系。 证明：若存在 \(na_i\) 与 \(na_j\) 同余即 \(na_i\equiv na_j\:(mod\:m)\) ，由引理 \(1\) 可得 \(a_i\equiv a_j\:(mod\:m)\) ，与条件不符，故假设不成立。 证毕。 引理 \(4\) ： 若 \(n\) 与 \(m\) 互质，且 \(\left\{\overline{a_1},\overline{a_2},\overline{a_3},\cdots,\overline{a_{\varphi(n)}}\right\}\) 为 \(m\) 的简化剩余系，则 \(\left\{\overline{na_1},\overline{na_2},\overline{na_3},\cdots,\overline{na_{\varphi(n)}}\right\}\) 也构成 \(m\) 的简化剩余系。