数论知识

• 扩展欧几里得算法

• 二元线性丢番图方程(二元一次不定方程)

• 一元线性同余方程

• 欧拉定理

  • 证明：
  • 费马小定理：

• 逆元

扩展欧几里得算法

• 根据裴蜀定理，$ax+by=gcd(a,b)ax+by=gcd(a,b)$有整数解$x,yx,y$

  

• 用扩展欧几里得算法，可以在求$gcd(a,b)gcd(a,b)$的过程中求出一组$x_0,y_{0}x\_0,y\_0$

  则方程的全部解为

  $\{\begin{array}{c}x=x_0+\frac{b}{gcd(a,b)}\ast k\\ y=y_0-\frac{a}{gcd(a,b)}\ast k\\ k\in \mathbb{Z}\end{array}\backslash left\backslash \{\; \backslash begin\{array\}\{c\}\; x=x\_0+\backslash frac\{b\}\{gcd(a,b)\}*k\backslash \backslash \; y=y\_0-\backslash frac\{a\}\{gcd(a,b)\}*k\backslash \backslash \; k\backslash in\; \backslash mathbb\{Z\}\backslash \backslash \; \backslash end\{array\}\; \backslash right.$

二元线性丢番图方程(二元一次不定方程)

• $ax+by=cax+by=c$有解的充要条件：

  $c\mathrm{\%}gcd(a,b)=0c\; \backslash \%\; gcd(a,b)\; =\; 0$

• 设$ax+by=gcd(a,b)ax+by=gcd(a,b)$的一组解为$(x^{\ast },y^{\ast })(x^*,y^*)$

  则$ax+by=cax+by=c$的一组解为$(\frac{c}{gcd(a,b)}{x}^{\ast },\frac{c}{gcd(a,b)}{y}^{\ast })(\backslash frac\{c\}\{gcd(a,b)\}x^*,\; \backslash frac\{c\}\{gcd(a,b)\}y^*)$

  全部解为

  $\{\begin{array}{c}x=\frac{c}{gcd(a,b)}{x}^{\ast }+\frac{b}{gcd(a,b)}\ast k\\ y=\frac{c}{gcd(a,b)}{y}^{\ast }-\frac{a}{gcd(a,b)}\ast k\\ k\in \mathbb{Z}\end{array}\backslash left\backslash \{\; \backslash begin\{array\}\{c\}\; x=\backslash frac\{c\}\{gcd(a,b)\}x^*+\backslash frac\{b\}\{gcd(a,b)\}*k\backslash \backslash \; y=\backslash frac\{c\}\{gcd(a,b)\}y^*-\backslash frac\{a\}\{gcd(a,b)\}*k\backslash \backslash \; k\backslash in\; \backslash mathbb\{Z\}\backslash \backslash \backslash end\{array\}\; \backslash right.$

一元线性同余方程

• 形如

  $ax\equiv b\left(modm\right)ax\backslash equiv\; b\backslash left(\; mod\backslash ,\backslash ,m\; \backslash right)$

  称为一元线性同余方程，与二元线性丢番图方程类似

• 一元线性同余方程组可以转化为

  $ax+my=bax+my=b$

  则线性同余方程有解的充要条件为

  $b\mathrm{\%}gcd(a,m)=0b\backslash \%gcd(a,m)=0$

• 根据二元线性丢番图方程的解的公式，解线性同余方程得

  $x=\frac{b}{gcd(a,m)}{x}^{\ast }+\frac{m}{gcd(a,m)}\ast k\mathrm{其}\mathrm{中}{x}^{\ast }\mathrm{是}ax+my=gcd(a,m)\mathrm{的}\mathrm{一}\mathrm{个}\mathrm{解}k=0,1,\mathrm{.}\mathrm{.}\mathrm{.},gcd(a,m)-1x=\backslash frac\{b\}\{gcd(a,m)\}x^*+\backslash frac\{m\}\{gcd(a,m)\}*k\; \backslash \backslash \; 其中x^*是ax+my=gcd(a,m)的一个解\; \backslash \backslash \; k=0,1,...,gcd(a,m)-1$

欧拉定理

• 当$gcd(a,n)=1gcd(a,n)=1$时，$a^{\phi (n)}\equiv 1(modn)a^\{\backslash varphi(n)\}\; \backslash equiv\; 1\; (mod\backslash \; n)$
• 当n是质数时，$\phi (n)=n-1\backslash varphi(n)=n-1$，所以$a^{n-1}\equiv 1(modn)a^\{n-1\}\; \backslash equiv\; 1\; (mod\backslash \; n)$

证明：

记号：$a_1,a_2,\mathrm{.}\mathrm{.}\mathrm{.},a_{\phi (n)}\mathrm{是}1-n\mathrm{中}\mathrm{与}n\mathrm{互}\mathrm{质}\mathrm{的}\mathrm{数}a\_1,a\_2,...,a\_\{\backslash varphi(n)\}是1-n中与n互质的数$

• step1：由于$a_{i}a\_i$和n互质，$aa$和n互质，所以$a{a}_1\mathrm{、}a{a}_2\mathrm{、}\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{、}a{a}_{\phi (n)}\mathrm{与}n\mathrm{互}\mathrm{质}aa\_1、aa\_2、...、aa\_\{\backslash varphi(n)\}与n互质$

• step2：假设$a{a}_i\equiv a{a}_j(modn)aa\_i\; \backslash equiv\; aa\_j\; (mod\backslash \; n)$，则$a(a_i-a_j)\equiv 0(modn)\mathrm{.}a(a\_i-a\_j)\backslash equiv\; 0(mod\backslash \; n).$

  因为$gcd(a,n)=1gcd(a,n)=1$，所以$a_i-a_j\equiv 0(modn)\mathrm{，}\mathrm{即}{a}_i\equiv a_j(modn)a\_i-a\_j\; \backslash equiv\; 0\; (mod\backslash \; n)，即a\_i\; \backslash equiv\; a\_j(mod\; \backslash \; n)$

  因为$a_i\equiv ̸a_j(modn),a\_i\; \backslash not\; \backslash equiv\; a\_j\; (mod\backslash \; n),$所以$a{a}_i\mathrm{和}a{a}_{j}aa\_i和aa\_j$互不相同

  所以$\{a{a}_i\}\mathrm{和}\{a_i\}\backslash \{aa\_i\backslash \}和\backslash \{a\_i\backslash \}$都能表示$nn$的简化剩余系

  所以$a^{\phi (n)}{a}_1{a}_2\mathrm{.}\mathrm{.}\mathrm{.}{a}_{\phi (n)}\equiv a_1{a}_2\mathrm{.}\mathrm{.}\mathrm{.}{a}_{\phi (n)}(modn)a^\{\backslash varphi(n)\}a\_1a\_2...a\_\{\backslash varphi(n)\}\; \backslash equiv\; a\_1a\_2...a\_\{\backslash varphi(n)\}\; (mod\backslash \; n)$

  即$a^{\phi (n)}\equiv 1(modn)a^\{\backslash varphi(n)\}\; \backslash equiv\; 1\; (mod\backslash \; n)$

费马小定理：

当n是质数时的欧拉定理即为费马小定理

逆元

• 定义：$ax\equiv 1(modm)ax\; \backslash equiv\; 1(mod\backslash \; m)$，$xx$是$aa$的模$mm$逆元。

  通常情况下，逆元指的是x的最小正整数解，则问题转化为求x的最小正整数解

• 方程有解的充要条件：$gcd(a,m)=1gcd(a,m)=1$

• 求解方法：

  • 扩展欧几里得算法

    原方程转化为$ax+my=1=gcd(a,m)ax+my=1=gcd(a,m)$

    利用扩展欧几里得算法求出$x=x_0+\frac{m}{gcd(a,m)}\ast k=x_0+m\ast kx=x\_0+\backslash frac\{m\}\{gcd(a,m)\}*k=x\_0+m*k$

    则x的最小正整数解为$(x_0\mathrm{\%}m+m)\mathrm{\%}m(x\_0\backslash \%m+m)\backslash \%m$

  • 费马小定理

    当$mm$是质数时，$a\ast a^{m-2}\equiv 1(modm)a*a^\{m-2\}\; \backslash equiv1(mod\backslash \; m)$

    所以$a^{m-2}\mathrm{\%}ma^\{m-2\}\backslash \%m$就是$aa$的逆元

• 应用

  $b\mathrm{\%}a=0b\backslash \%a=0$的条件下，计算$(b\mathrm{/}a)\mathrm{\%}m\mathrm{.}(b/a)\backslash \%m.$若b很大，则可以通过$aa$的逆元来计算

  即$(b\mathrm{/}a)\mathrm{\%}m(b/a)\backslash \%m$化为$(bx)\mathrm{\%}m=((b\mathrm{\%}m)\ast (x\mathrm{\%}m))\mathrm{\%}m(bx)\backslash \%m=((b\backslash \%m)*(x\backslash \%m))\backslash \%m$来计算