首页 > 其他分享 >裴蜀定理证明

裴蜀定理证明

时间:2024-06-09 11:11:16浏览次数:26  
标签:mathbb 0q 定理 证明 aX 互质 裴蜀

简单裴蜀定理


有 \(a\) 和 \(b\) 两数互质,则 \(\exists X,Y\in \mathbb{Z}\),使得 \(aX + bY = 1\).

证明:
规定集合 \(S = \left \{ aX + bY | X,Y \in \mathbb{Z} \right \}\)
设 \(aX_0 + bY_0\) 为集合 \(S\) 中的最小正值
则对于 \(\forall aX + bY \in S\)
都可表示为 \(aX + bY = (aX_0 + bY_0)q + R\),其中 \(q,R \in Z\)
经移项可得 \(a(X - X_0q) + b(Y - Y_0q) = R \in S\)
又因 \(aX_0 + bY_0\) 为最小正值且 \(R \ge 0\)
所以 \(R = 0\)
由假设可知 $\forall u \in S $
\(u \bmod (aX_0 + bY_0) = 0\)
所以 \(aX_0 + bY_0\) 为 \(S\) 中所有元素的最大公约数
又因 \(a\),\(b\) 互质
则 \(aX_0 + bY_0\) 即为 \(gcd(a,b) = 1\)
得证。

标签:mathbb,0q,定理,证明,aX,互质,裴蜀
From: https://www.cnblogs.com/wyl123ly/p/18239356

相关文章

  • 瞎记一些匹配相关定理的证明
    由于公式打不熟练,以下表达上可能会有很多不严谨的地方以及一些笔误。Hall'sTheorem\(S_1,S_2,\cdots,S_m\)存在一组相异代表系(SDR)\(\Leftrightarrow\)\(\forallI\subseteq\{1,2,\dots,m\},|\bigcup_{i\inI}S_i|\geq|I|\)。以二分图为背景就是二分图存在一个完美匹配......
  • Matrix-Tree 定理
    引入此算法可以解决图上生成树计数问题。值得注意的是,矩阵树定理不能用于存在自环的图。定义设\(G\)是一个图。记邻接矩阵\(A(G)_{i,j}=\#e(i,j),\#e(i,j)\)若\(G\)是无向图记\(D(G)\)表示其度数矩阵,\(D(G)\)满足\(D(G)_{i,i}\)表示第\(i\)点的度数,\(D(G)_{......
  • 线段树合并复杂度证明
    以CF600E为例,没看过题目的先去看题。本题的线段树做法,即对题目所给树中每个结点所在子树建树维护数字出现情况。此做法中,当前节点和其兄弟节点对应的线段树需要合并到父节点上,最后父节点上权值update到新树。也就是说对于每个非叶子节点,其有x个子节点,就要合并x次(其实也可以看成x-......
  • 罗德里格斯旋转公式证明
    罗德里格斯旋转公式证明。设旋转向量为\((n,\theta)\),设其对应的旋转矩阵为\(R\),如何证明?\[R=cos\thetaI+n^{\wedge}sin\theta+(1-cos\theta)nn^{T}\]证明过程如下:如图所示,设旋转向量为\(\hat{A}\),记为\(n\),设三维中的点\(r\)绕\(n\)旋转\(\theta\)后得到\(r^{'}\),其中\(......
  • 证明欧几里得定理(这是一位刚学数论的初三生发明的方法)
    欧几里得定理:gcd(a,b)=......
  • Chapter 4 证明技巧
    证明技巧:思路图使用公理系统时,证明的「构思过程」与证明的「书写过程」大相径庭。思考过程往往从最后一步开始,逐步规约。来看两个例子传递律的证明\[A\rightarrowB,B\rightarrowC\vdashA\rightarrowC\]Thinking&Writing...换位律的证明\[\vdash(A\rightarrow(B\ri......
  • 矩阵树定理学习笔记
    矩阵树定理学习笔记真的,我这辈子都没有想过行列式还能用到这种地方。定义图的关联矩阵对于一张有\(n\)个点、\(m\)条边的图(对于无向图,可以随便定义边的方向,因为相反的边只需要将对应列乘以\(-1\)即可),我们定义其关联矩阵\(M\)满足:\[M_{i,j}=\left\{\begin{matrix}1&e_j......
  • 2024_5_29 狄尔沃斯定理(偏序集)
    偏序集中的反链是其元素两两不可比的子集,而链是其元素两两可比的子集。链分解是将偏序集中的元素划分为若干无交的链。狄尔沃斯定理指出,有限偏序集合中,包含元素最多反链的元素数等于包含链数最少的链分解的链数,这个量被定义为该偏序集的宽度。对于任意有限偏序集,其最大反链中元素......
  • 高斯公式对高斯定理的推导
    目录前置定理基础证明过程参考资料这里主要讨论多元微分学中学到的高斯公式对于物理上的高斯定理的推导(目前是对于静电荷的高斯定理)。本身想连着Stokes公式一大堆一块写,但是考虑到工程量太大了,所以尝试分篇来写吧。前置定理基础标准的高斯公式的形式如下(推导略)\[\iiint_{\Omeg......
  • 非凸优化收敛性证明框架
    \chapter{非凸优化}\section{非凸优化中的重要概念}\subsection{次微分}\begin{definition}{Frechet次微分}适当函数\(f\),如果\(\forallx\in\)dom$f\(,则\)f\(在\)x\(处的Frechet次微分记为\)\overset{-}{\partial}f(x)$,它的定义是:$$\overset{-}{\partial}f(x)=\left\l......