链接
引 理 2 的 证 明 引理2的证明 引理2的证明
就 是 p = a x , 假 定 g c d ( p , m ) > 1 ， 那 么 p 模 m = r , g c d ( r , m ) > 1 移 项 可 得 a x − m k = r 根 据 裴 蜀 定 理 a x − b y = c 的 充 要 条 件 是 g c d ( a , b ) ∣ c ， 并 且 所 有 的 解 都 能 表 示 成 a x − b y = g c d ( a , b ) 的 解 x ′ , y ′ 的 c / g c d ( a , b ) 倍 这 样 g c d ( a , m ) = 1 ， 所 以 x 一 定 是 r 的 倍 数 ， 这 就 矛 盾 了 就是p=ax,假定gcd(p,m)>1，那么p模m=r,gcd(r,m)>1 移项可得ax-mk=r 根据裴蜀定理ax-by=c的充要条件是gcd(a,b)|c，并且所有的解都能表示成ax-by=gcd(a,b)的解x',y'的c/gcd(a,b)倍 这样gcd(a,m)=1，所以x一定是r的倍数，这就矛盾了 就是p=ax,假定gcd(p,m)>1，那么p模m=r,gcd(r,m)>1移项可得ax−mk=r根据裴蜀定理ax−by=c的充要条件是gcd(a,b)∣c，并且所有的解都能表示成ax−by=gcd(a,b)的解x′,y′的c/gcd(a,b)倍这样gcd(a,m)=1，所以x一定是r的倍数，这就矛盾了
总 而 言 之 ， 欧 拉 定 理 的 证 明 是 需 要 构 造 p i = a ∗ x i 总而言之，欧拉定理的证明是需要构造p_i=a*x_i 总而言之，欧拉定理的证明是需要构造pi​=a∗xi​
并 且 证 明 p i 两 两 模 m 不 同 （ x i 同 理 ） 并且证明p_i两两模m不同（x_i同理） 并且证明pi​两两模m不同（xi​同理）
p i 模 m 与 m 互 质 pi模m与m互质 pi模m与m互质
这 样 我 们 就 可 以 推 出 p i 模 m 共 f ( m ) 个 ， 而 x i 共 m 个 且 互 相 不 同 ， 所 以 就 可 以 推 出 乘 积 模 m 相 等 这样我们就可以推出pi模m共f(m)个，而x_i共m个且互相不同，所以就可以推出乘积模m相等 这样我们就可以推出pi模m共f(m)个，而xi​共m个且互相不同，所以就可以推出乘积模m相等

扩展欧拉定理证明转载


该 定 理 证 明 比 较 简 单 该定理证明比较简单 该定理证明比较简单
证 明 过 程 中 要 用 到 积 性 函 数 的 性 质 也 就 是 证 明 任 意 组 合 质 数 证明过程中要用到积性函数的性质也就是证明任意组合质数 证明过程中要用到积性函数的性质也就是证明任意组合质数
箭 头 所 指 的 东 西 证 明 我 也 不 太 会 ， 如 果 有 人 知 道 的 话 希 望 可 以 告 诉 我 o w o 箭头所指的东西证明我也不太会，如果有人知道的话希望可以告诉我owo 箭头所指的东西证明我也不太会，如果有人知道的话希望可以告诉我owo