Like a BIRDIE flies into your heart...

0%

费马小定理

内容

若 $p$ 为素数,$gcd(a,p)=1$,则 $a^{p-1}\equiv1\pmod{p}$。

证明

思路

考虑集合 $A$ 为模 $p$ 意义下的最小完整剩余系,即 $A=\{1,2,…,p-1\}$。而集合 $B$ 为 $\{1a,2a,…,(p-1)a\}$。我们将证明集合 $B$ 在模 $p$ 意义下与集合 $A$ 是一一对应关系,即集合 $B$ 也是模 $p$ 意义下的完整剩余系。

由此,我们可以应用公式:

即证明得到费马小定理。

主要证明过程

下面我们证明集合 $A,B$ 是一一对应关系。为此,我们可以证明 $\forall i\neq j,ia\not\equiv ja \pmod{p}$。

应用反证法,假设 $\exist i\neq j,ia\equiv ja \pmod{p}$,同时不妨设 $i > j$,那么我们可以得到 $(i-j)a \mid p$。而由题设我们可以得到 $gcd(a,p)=1$,且 $0<(i-j)<p$,$p$ 是质数,所以 $gcd(i-j,p)=1$。所以 $(i-j)a\nmid p$,矛盾。

于是我们证明了 $\forall i\neq j,ia\not\equiv ja \pmod{p}$,即证明了集合 $A,B$ 的一一对应关系。由此根据先前的推到,我们证明得到了费马小定理。

欧拉定理

内容

欧拉定理可以视为费马小定理的推广形式,定理内容如下:

当 $m$ 为质数时,$\phi(m)=m-1$,我们即得到了费马小定理。

证明

思路

欧拉定理具体的证明思路与费马小定理相仿,我们利用模 $m$ 意义下的简化剩余系 $r_1,r_2,…,r_{\phi(m)}$ ,我们对其每一个元素乘 $a$ ,得到 $ar_1,ar_2,…,ar_{\phi(m)}$,我们将证明这样操作得到的集合仍然是模 $m$ 意义下的简化剩余系。按照对费马小定理相同的处理方式,我们可以证明得到欧拉定理。

主要证明过程

我们将证明以下两点:

  1. $ar_i$ 与 $m$ 互质
    $\because gcd(a,m)=1,gcd(r_i,m)=1$
    $\therefore gcd(ar_i,m)=1$
  2. $\forall i\neq j,ar_i\not\equiv ar_j \pmod{m}$
    应用反证法,与费马小定理证明相仿,故在此略去。

$\therefore ar_1,ar_2,…,ar_{\phi(m)}$ 也是模 $m$ 意义下的一个简化剩余系。

$\therefore ar_1\cdot ar_2\cdot…\cdot ar_{\phi(m)} \equiv r_1 \cdot r_2 \cdot…\cdot r_{\phi(m)} \pmod{m}$

即得到 $a^{\phi(m)}\equiv 1 \pmod{m}$

拓展欧拉定理

内容

拓展欧拉定理时在比赛刷题中常用的公式,可以很方便的讲一个看似根本不可能计算的幂次方(甚至幂套幂套幂……)逐步通过取模简化至可以计算的形式。与快速幂一次食用效果更佳。

证明

不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会不会。

习题

洛谷P5091 【模板】扩展欧拉定理

  自高考完以来,在挣扎中,在体悟中,我越来越领悟到友情、亲情等除了爱情之外的美好。

阅读全文 »

  在搭建博客的过程中开始真正接触到git这一强大的工具,也就很快对其产生了好奇心。于是写一篇博客来记录自己学习git和github的过程。

阅读全文 »