数学&数论

ZJle · 2024-09-15 07:48:40 · 学习·文化课

数学&数论

同余

• 这是个非常重要的概念

• 定义

  • 设整数 m\ne0。若 m\mid(a-b)，称 m 为 模数（模），a 同余于 b 模 m，b 是 a 对模 m 的 剩余。记作 a\equiv b\pmod m。

  • 否则，a 不同余于 b 模 m，b 不是 a 对模 m 的剩余。记作 a\not\equiv b\pmod m。

  • 这样的等式，称为模 m 的同余式，简称 同余式。

  • 根据整除的性质，上述同余式也等价于 a\equiv b\pmod{(-m)}。

• 性质

  • 如果 a \equiv b \pmod m,c \equiv d \pmod m,那么 a+c \equiv b+d \pmod m
  • 如果 a \equiv b \pmod m,c \equiv d \pmod m,那么 a-c \equiv b-d \pmod m
  • 如果 a \equiv b \pmod m,c \equiv d \pmod m,那么 ac \equiv bd \pmod m
  • 上述的同余式证明都比较简单,将
    • \begin{cases}a=x1*m+op\\b=x2*m+op\\c=x3*m+ui\\d=x4*m+ui\end{cases}

      进行暴力展开即可证明

• 幽默拓展

  • 如果 ab \equiv 1\pmod m,定义 a^{-1} \equiv b \pmod m
  • (这是乘法逆元)

    费马小定理

• 定义

  • 若 p为素数,\gcd(a,p)=1,则a^{p-1}\equiv1\pmod p
  • 另一个形式:对于任意整数 a ,有a^p\equiv a\pmod p

• 证明

  • 设一个质数 p,我们取一个不为 p 倍数的数 a
  • 构造一个序列: A=\{1,2,3,...,p-1\},这个数列有这样一个性质
  • \prod_{i=1}^{p-1}\space A_i\equiv\prod_{i=1}^{p-1} (A_i\times a) \pmod p
  • 证明:
  • (A_i,p)=1,(A_i*a,p)=1
  • 又因为每个 A_i*a\pmod p都是独一无二的,且 A_i*a \pmod p < p
  • 得证 (每一个 A_i*a 都对应了一个 A_i)
  • 设f=(p-1)!,则 f\equiv A_1*a*A_2*a*A_3*a*...*A_{p-1}*a\pmod p
    • 这里可以根据上面的 ac \equiv bd \pmod m推断得出
  • a^{p-1}*f\equiv f\pmod p
  • 同时也可以用归纳法证明
    • 显然 1^p\equiv1 \pmod p ,假设 a^{p}\equiv a \pmod p成立,那么通过二项式定理可知
    • (a+1)^p=a^p+\binom{p}{1}a^{p-1}+\binom{p}{2}a^{p-2}+\cdots +\binom{p}{p-1}a+1
    • 因为\binom{p}{k}=\frac{p(p-1)\cdots(p-k+1)}{k!}对于1\leq k\leq(p-1),在模 p 意义下 \binom{p}{1}\equiv\binom{p}{2}\equiv\binom{p}{3}\equiv\cdots\equiv \binom{p}{p-1}\equiv 0\pmod p,那么 (a+1)^p\equiv a^p+1\pmod p,将a^p\equiv a\pmod p带入即可得(a+1)^p\equiv a+1 \pmod p
    • 得证

      欧几里得算法

• 如果我们已知两个数 a 和 b，如何求出二者的最大公约数呢？

  • 不妨设 a > b。
  • 我们发现如果 b 是 a 的约数，那么 b 就是二者的最大公约数。下面讨论不能整除的情况，即 a = b \times q + r，其中 r < b。
  • 我们通过证明可以得到 \gcd(a,b)=\gcd(b,a \bmod b)，过程如下:
  • 设 a=bk+c，显然有 c=a \bmod b。设 d \mid a,~d \mid b，则 c=a-bk, \frac{c}{d}=\frac{a}{d}-\frac{b}{d}k。
  • 由右边的式子可知 \frac{c}{d} 为整数，即 d \mid c，所以对于 a,b 的公约数，它也会是 b,a \bmod b 的公约数。
  • 反过来也需要证明:
  • 设 d \mid b,~d\mid (a \bmod b)，我们还是可以像之前一样得到以下式子 \frac{a\bmod b}{d}=\frac{a}{d}-\frac{b}{d}k,~\frac{a\bmod b}{d}+\frac{b}{d}k=\frac{a}{d}。
  • 因为左边式子显然为整数，所以 \frac{a}{d} 也为整数，即 d \mid a，所以 b,a\bmod b 的公约数也是 a,b 的公约数。
  • 既然两式公约数都是相同的，那么最大公约数也会相同。所以得到式子 \gcd(a,b)=\gcd(b,a\bmod b)
  • 既然得到了 \gcd(a, b) = \gcd(b, r)，这里两个数的大小是不会增大的，那么我们也就得到了关于两个数的最大公约数的一个递归求法。

    扩展欧几里得算法

• 裴蜀定理

  • 对于任何整数 a,b ,关于未知数 x 和 y 的线性不定方程(称为裴蜀等式)

• • 方程有整数解(当且仅当 \gcd(a,b)|c 时),裴蜀等式有解时必然有无穷多个解
  • ax+by=c$有解的充要条件是 $\gcd(a,b)|c
  • 一定存在x和y使得ax+by=\gcd(a,b)
  • 推论,当a,b互素的时候 ax+by=1 有解
  • 证明
    • 对于第一点,由于
    • \gcd(a,b)\mid a$且$\gcd(a,b)\mid b
    • 所以\gcd(a,b)\mid ax且\gcd(a,b)\mid by
    • 因此\gcd(a,b)\mid ax+by
    • 对于第二点,由于
    • 1.若a,b任何一个等于0,\gcd(a,b)=a这时定理显然成立
    • 2.若a,b不等于0
      • 由于 gcd(a,b)=gcd(a,-b)
      • 不妨设a,b都大于0,a≥b,\gcd(a,b)=d
      • 对ax+by=d,两边同时除以d,可得a_1x+b_1y=1,其中(a_1,b_1)=1
      • 转证a_1x+b_1y=1
      • 来回忆一下辗转相除法是怎么做的,由\gcd(a,b)\rightarrow\gcd(b,a\mod b)我们把模出来的数据叫做 r,于是有\gcd(a_1,b_1)=\gcd(b_1,r_1)=\gcd(r_1,r_2)=\cdots=\gcd(r_{n-1},r_n)
      • 把辗转相除法中的运算展开,做成带余的除法,得

• • • • 不妨令辗转相除法在除到互质的时候退出则 r_n=1 所以有（q 被换成了 x，为了符合最终形式）

• • • • 即

由倒数第三个式子 r_{n-1}=r_{n-3}-x_{n-1}r_{n-2} 代入上式，得

• • • • • 然后用同样的办法用它上面的等式逐个地消去r_{n-2},\cdots,r_1,
    • 可证得 1=a_1x+b_1y
    • 这样等于是一般式中 d=1 的情况。
• 接下来就该进入正题关于拓展欧几里得定理了
  • 目的:求出一组关于ax+by=\gcd(a,b)的特解
  • 根据欧几里得算法 可得

• • 其中将a\mod b代替为 a-\lfloor \frac{a}{b}\rfloor *b代入上式中可得

• • 可以得出x和y与x^{'}和y^{'}的关系
  • \begin{cases}x=y^{'}\\y=x^{'}-\lfloor \frac{a}{b}\rfloor*y^{'}\end{cases}
  • 边界情况分析 ax^{'}+by^{'}=d(d=\gcd(a,b)),当b=0时,a为\gcd(a,b),当且仅当x^{'}=-1时成立;y^{'}可以为任意值,为方便起见,设y^{'}=0
  • 根据 ?=?’,?=?’−⌊\frac{a}{b}⌋∗?’，可以倒推出 ? 和 ? 的多组解。

逆元

• 如果一个线性同余方程 ax \equiv 1 \pmod b，则 x 称为 a \bmod b 的逆元，记作 a^{-1}。

• 首先,根据拓展欧几里得定理的原理,我们可以求出线性同余方程组的解,以下是证明

  • 形如ax\equiv b\pmod n的方程称为 线性同余方程。其中，a、b 和 n 为给定整数，x 为未知数。需要从区间 [0, n-1] 中求解 x，当解不唯一时需要求出全体解。
  • 根据以下两个定理，可以求出线性同余方程 ax\equiv b \pmod n 的解。

  • 定理 1：

    • 线性同余方程 ax\equiv b \pmod n 可以改写为如下线性不定方程：ax + nk = b
    • 其中 x 和 k 是未知数。这两个方程是等价的，有整数解的充要条件为 \gcd(a,n) \mid b。
    • 应用扩展欧几里德算法可以求解该线性不定方程。根据定理 1，对于线性不定方程 ax+nk=b，可以先用扩展欧几里得算法求出一组 x_0,k_0，也就是 ax_0+nk_0=\gcd(a,n)，然后两边同时除以 \gcd(a,n)，再乘 b。就得到了方程

• • • • 于是找到方程的一个解。

    • 定理 2：

    • 若 \gcd(a,n)=1，且 x_0、k_0 为方程 ax+nk=b 的一组解，则该方程的任意解可表示为：

    • \begin{cases} x=x_0+nt\\k=k_0-at\end{cases}

    • 并且对任意整数 t 都成立。

    • 根据定理 2，可以从已求出的一个解，求出方程的所有解。实际问题中，往往要求出一个最小整数解，也就是一个特解x=(x \bmod t+t) \bmod t

    • 其中有t=\dfrac{n}{\gcd(a,n)}

  • 不难发现,这可以用来求逆元

中国剩余定理

以下证明来自于Bilibili以及Oi-wiki

• 中国剩余定理可求解如下形式的一元线性同余方程组（其中 n_1, n_2, \cdots, n_k 两两互质）：

• 下面是一个例子
  • 用线性代数的话来说 可以将 10 和 6作为一组基向量
  • \begin{cases} 10=\left( ^1_0\right)\\6=\left( ^0_1\right)\end{cases}
  • 任何一个解都可以用这个方法求出
  • (^a_b)=a*( ^1_0)+b*(^0_1)=a*10+b*6

• • \overrightarrow{e_i} \equiv δ_{i,j} \pmod {m_j}
  • x=\sum_{i=1}^n a_i \overrightarrow {e_i}\pmod {\prod ^n_{i=1}m_i}
  • 但是这些好用的基向量是怎么算出来的呢
  • 我们可以回到上面的表格
  • 想要成为 5 的基向量,就一定得是 3的倍数
  • (_1^0)\equiv \pmod 3
    • \begin{cases}3\equiv 0 \pmod 3 \\ 3\equiv 3 \pmod 5\end{cases}
    • 但是我们之前学过数论倒数 2 \equiv 3^{-1} \pmod 5
    • 那么我们只要给 3 乘上 2
    • 2*\begin{cases}3\equiv 0 \pmod 3 \\ 3\equiv 3 \pmod 5\end{cases} \Rightarrow\begin{cases}6\equiv 0 \pmod 3 \\ 6\equiv 1 \pmod 5\end{cases}
    • 这样就得到了 5 的基向量
    • 同理的我们只要给 5 乘上 2 就得到了3的基向量
    • 2*\begin{cases}5\equiv2 \pmod 3 \\ 5\equiv 0 \pmod 5\end{cases} \Rightarrow\begin{cases}10\equiv 1 \pmod 3 \\ 10\equiv 0 \pmod 5\end{cases}
  • 对于多个数而言
    • m_1=3\qquad m_2=5 \qquad m_3=7
    • M_1=5\times 7=35
    • M_1^{-1}\equiv 2\pmod 3
    • 2*\begin{cases}M_1\equiv 2 \pmod 3 \\ M_1\equiv 0 \pmod 5\\ M_1\equiv 0 \pmod 7\end{cases}
    • \overrightarrow {e_1}=M_1\times [M_1]^{-1}_{\mod3}=35\times 2=70
    • M_2=3\times 7=21
    • M_2^{-1}\equiv 1\pmod 5
    • 1*\begin{cases}M_2\equiv 0 \pmod 3 \\ M_2\equiv 1 \pmod 5\\ M_2\equiv 0 \pmod 7\end{cases}
    • \overrightarrow {e_2}=M_2\times [M_2]^{-1}_{\mod5}=21\times 1=21
    • M_3=3\times 5=15
    • M_3^{-1}\equiv 1\pmod 3
    • 1\times\begin{cases}M_3\equiv 0 \pmod 3 \\ M_3\equiv 0 \pmod 5\\ M_3\equiv 1 \pmod 7\end{cases}
    • \overrightarrow {e_3}=M_3\times [M_3]^{-1}_{\mod3}=15\times 1=15
• 总结性的来说
  • 对于一组同余方程$\begin{cases} x &\equiv a_1 \pmod {m_1} \ x &\equiv a_2 \pmod {m_2} \ &\vdots \ x &\equiv a_n \pmod {m_n} \ \end{cases}
  • 其解为 x\equiv \sum_{i=1}^na_i\overrightarrow{e_i}\pmod M,其中M=\prod_{i=1}^nm_i
  • 其中,\overrightarrow{e_i}=M_i[M_i]^{-1}_{\mod m_i},M_i=\frac{M}{m_i},i=1,2,3,\cdots,n。
  • 以上即为中国剩余定理的基本形式

    一次式同余

整式的中国剩余定理

• 对于一组同余方程$\begin{cases} f(x) &\equiv a_1(x) \pmod {m_1(x)} \ f(x) &\equiv a_2(x) \pmod {m_2(x)} \ &\vdots \ f(x) &\equiv a_n(x) \pmod {m_n(x)} \ \end{cases}

  - 其解为 $f(x)\equiv \sum_{i=1}^na_i(x)\overrightarrow{e_i}(x)\pmod M(x)$,其中$M(x)=\prod_{i=1}^nm_i(x)
  • 其中,\overrightarrow{e_i}(x)=M_i(x)[M_i(x)]^{-1}_{\mod m_i(x)},M_i=\frac{M(x)}{m_i(x)},i=1,2,3,\cdots,n。
    • 以上即为整式中国剩余定理的基本形式

• 拓展衍生

  • 如果在解整式的同余方程组时,这些整式都是一次式$\begin{cases} f(x) &\equiv a_1(x) \pmod {x_1-a} \ f(x) &\equiv a_2(x) \pmod {x_2-a} \ &\vdots \ f(x) &\equiv a_n(x) \pmod {x_n-a} \ \end{cases}
  • 那么中国剩余定理的样子会不会好看一点呢?
  • 由于 f(x)\equiv f(a)\pmod{x-a}
  • 所以 $\begin{cases} f(x) &\equiv f(x_1) \pmod {x_1-a} \ f(x) &\equiv f(x_2) \pmod {x_2-a} \ &\vdots \ f(x) &\equiv f(x_n) \pmod {x_n-a} \ \end{cases}
  • 于是我们可以将解里面的所有a_i(x)替换为f(x_i)
  • 其解为 f(x)\equiv \sum_{i=1}^nf(x_i)\overrightarrow{e_i}(x)\pmod{ M(x)},其中M(x)=\prod_{i=1}^nm_i(x)
    • 其中,\overrightarrow{e_i}(x)=M_i(x)[M_i(x)]^{-1}_{\mod m_i(x)},M_i=\frac{M(x)}{m_i(x)},i=1,2,3,\cdots,n。
  • 可以发现 式中还有两个乘积,我们可以对他下手
  • 虽然乘积本身不涉及取模,但是他的逆元涉及了取模
  • M_1(x)=\frac{(x-x_1)(x-x_2)(x-x_3)\cdots(x-x_n)}{x-x_1}
  • \qquad\quad=(x-x_2)(x-x_3)\cdots(x-x_n)
  • [M_1(x)]^{-1}_{\mod x-x_1}\equiv M_1^{-1}\pmod{x-x1}
  • [M_1(x)]^{-1}_{\mod x-x_1}\equiv \frac{1}{M_1(x_1)}\pmod{x-x1}
  • 进一步来说,这个式子的基向量
  • \overrightarrow{e_1}(x)=M_1(x)[M_1(x)]^{-1}_{\mod m_1(x)}
  • \qquad\,\,\,=\frac{M_1(x)}{M_1(x_1)}=\frac{(x-x_2)(x-x_3)\cdots(x-x_n)}{(x_1-x_2)(x_1-x_3)\cdots(x_1-x_n)}
  • \qquad\,\,\,=\prod_{j≠1}\frac{x-x_j}{x_1-x_j}
  • 其他的基向量也可以用这样表示
  • \overrightarrow{e_i}(x)=\prod_{j≠i}\frac{x-x_j}{x_i-x_j},i=1,2,3,\cdots,n
  • 把基向量的解再带回到解里面去
  • 其解为 f(x)\equiv \sum_{i=1}^nf(x_i)\prod_{j≠i}\frac{x-x_j}{x_i-x_j}\pmod {M(x)},其中M(x)=\prod_{i=1}^nm_i(x)

    拉格朗日差值法

• 由于要求构造一个函数 f(x) 过点 P_1(x_1, y_1), P_2(x_2,y_2),\cdots,P_n(x_n,y_n). 首先设第 i 个点在 x 轴上的投影为 P_i^{\prime}(x_i,0).

• 考虑构造 n 个函数 f_1(x), f_2(x), \cdots, f_n(x)，使得对于第 i 个函数 f_i(x)，其图像过 \begin{cases}P_j^{\prime}(x_j,0),(j\neq i)\\P_i(x_i,y_i)\end{cases}，则可知题目所求的函数 f(x)=\sum\limits_{i=1}^nf_i(x).

• 那么可以设 f_i(x)=a\cdot\prod_{j\neq i}(x-x_j)，将点 P_i(x_i,y_i) 代入可以知道 a=\dfrac{y_i}{\prod_{j\neq i} (x_i-x_j)}，所以

• 那么我们就可以得出 Lagrange 插值的形式为：

• 和上面产生联系的时候

  • f(x)=\sum_{i=1}^ny_i\cdot\prod_{j\neq i}\dfrac{x-x_j}{x_i-x_j}=\sum_{i=1}^n a_iM_i[M_i]^{-1}_{\mod m_i}

• 是不是很神奇?我也不知道为什么

  映射

• 这个比较唐

  • 比较正式的来说,就是有两个集合 A 和 B ,设 x 是 A 中的元素,设 y 是 B 中的元素,满足一定的法则 f ,使得 x 在 B 有唯一映射,可以使得 f: x \rightarrow y, y 称为元素 x 在映射下的像,称作 f(x) , x 称为元素 y 在映射 f 下的原像(感觉其实就是一个函数 f(x) ,加了定义域)
  • 同时,如果 R_f=B, B中的任何一个元素都能在A中找到原像,那么称 f 为 A 到 B 上的映射或是满射; 若 A 中任意两个不同元素 x1 和 x2 满足 f(x1)!=f(x2) 则称这个 f 为A到B的单射,若映射f是单射,那么称作这个f为一一映射或是叫双射
  • 映射又称为算子.根据集合 A 、B 的不同情形,在不同的数学分支中,映射又有不同的惯用名称.例如,从非空集 A 到数集 B 的映射又称为 A 上的泛函,从非空集 A 到它自身的映射又称为 A 上的变换,从实数集(或其子集) A 到实数集的映射通常称为定义在 A 上的 函数
  • 设f是X到Y的单射,则由定义,对每个y∈R,有唯一的x∈X,适合f(x)=y.于是,我们可定义一个从R到X的新映射g,即 g_R→X 对每个 y∈R_f ,规定g(y)=x,这x满足f(x)=y.这个映射g称为f的逆映射,记作f^{-1}其定义域 D_{f^{-1}}=R,值域 R_{f^{-1}} =X.
  • 按上述定义,只有单射才存在逆映射.