高中数学题的一些背景思考 1 —— 裴蜀定理

标签：right gcd 高中 定理 集合 数学题 裴蜀 left

1 裴蜀定理 「\(\in\) 数论」

题目

设集合 \(M=\left\{7m+5n\left| m,n\in\Z\right. \right\},N=\left\{3m-2n\left|m,n\in\Z\right.\right\}\)。试判断集合 \(M,N\) 的关系。

从 gcd 和 Euclid 说起

比方说我要求 \(\gcd(a,b)\)，不妨 \(a>b\)。

令 \(r_0=b\)，

\[\begin{aligned}a&=q_1\cdot{b}+r_1&0\le{r_1}<b&\quad\gcd(a,b)=\gcd(b,r_1)\\b&=q_2\cdot{r_1}+r_2&0\le{r_2}<r_1&\quad\gcd(a,b)=\gcd(r_1,r_2)\\&&\vdots\\r_{n-1}&=q_{n+1}\cdot{r_n}+r_{n+1}&0\le{r_{n+1}}<r_n&\quad\gcd(a,b)=\gcd(r_n,r_{n+1}) \end{aligned} \]

因为 \(b=r_0>r_1>r_2>\cdots>r_n>r_{n+1}>\cdots\ge0\)，所以有限次后，必然存在 \(r_i=0\)。
不妨认为 \(r_{n+1}=0\)，也就是说 \(\gcd(a,b)=\gcd(r_n,r_{n+1})=r_n\)。

这就是欧几里得算法求最大公约数。

裴蜀定理

\(\forall a,b\in\Z_+,\exists u,v\in\Z \text{ s.t. }ua+vb=\gcd(a,b)\)。

证明

根据上面的欧几里得算法，逆着走，这是显然的。

但是我们还有别的证法。

令 \(S=ua+vb\) 的最小正值，这个值显然存在。
设 \(a=qS+r(0\le r<S)\)，那么 \(r=a-qS\) 也是一个 \(\left(a,b\right)\) 的线性组合，因为 \(S\) 的最小性，所以 \(r=0\)，所以 \(S|a\)，同理 \(S|b\)，所以 \(S|\gcd(a,b)\)。
又因为 \(\gcd(a,b)|a,b\)，所以 \(\gcd(a,b)|(a,b)\) 的所有线性组合，包括 \(S\)，所以 \(S=\gcd(a,b)\)。

回归题目

因为 \(\gcd(7,5)=\gcd(3,2)=1\)，所以显然这两个集合是相等的。

怎么写呢，只要构造出一个 1 就可以了。

对于 \(M\)，\(-2\times7+3\times5=1\)；对于 \(N\)，\(3-2=1\)。

课后

0（重难点）：

设集合 \(M=\left\{12m+8n\left| m,n\in\Z\right. \right\},N=\left\{20m+16n\left|m,n\in\Z\right.\right\}\)。试判断集合 \(M,N\) 的关系。

1（初等数论——命题人讲座）：

设 \(n\ge m>0\)。求证 \(\dfrac{\gcd(n,m)}{n}C_{n}^m\) 是整数。

2（IMO）：

对于正整数 \(n,p,q\)，其中 \(n>p+q\)，以及数列 \(x_0,x_1,x_2,\ldots,x_n\) 满足

• \(x_0=x_n\)；
• \(\forall i\in[1,n]:x_{i}-x_{i-1}=p\text{ or }-q\)。
  试证明 \(\exists i<j,(i,j)\neq(0,n)\text{ s.t. } x_i=x_j\)。

标签：right,gcd,高中,定理,集合,数学题,裴蜀,left
From： https://www.cnblogs.com/LJC001151/p/18399303