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

裴蜀定理_原理证明

时间:2023-01-04 21:00:11浏览次数:41  
标签:mathbb le gcd cdot 定理 原理 textcolor 裴蜀

裴蜀定理

算法使用

对于\(\forall a,b \in \mathbb{Z}\),\(\exists x,y \in \mathbb{Z}\),使

\[a \cdot x + b \cdot y = \gcd(a,b) \]

且\(a\)与\(b\)组成的最小正整数为\(\gcd(a,b)\).

\(\gcd(x,y)\)表示\(x\)和\(y\)的最大公约数.

数学原理

Tips : \(a | b\)表示\(b\)能整除\(a\),即\(b \ \% \ a = 0\)或\(b \ ÷ \ a 为整数\).

\[\begin{aligned} 定义 &a与b为定值 \\ &A = \{c \ | \ a \cdot x + b \cdot y = c;x,y \in \mathbb{Z} \} \\ 设&A中最小正元素为s \\ &a \cdot x_0 + b \cdot y_0 = s \\ 要证 & \textcolor{blue}{\gcd(a,b) = s} \\ \because \ & \gcd(a,b) | a \cdot x_0 \\ & \gcd(a,b) | b \cdot y_0 \\ & \gcd(a,b) | (a \cdot x_0 + b \cdot y_0) \\ \therefore \ & \gcd(a,b) | s \\ & \textcolor{red}{s >= \gcd(a,b)} \\ 设 &a = m \cdot s + n , m \in \mathbb{Z} ,(0 \le n < s) \\ &b = i \ \ \cdot s + j \ , i \ \ \in \mathbb{Z} ,(0 \le j \ < s) \\ \because \ &n = a - m \cdot s \\ & \: \: \: \: = a - m (a \cdot x_0 + b \cdot y_0) \\ & \: \: \: \: = a(1 - m \cdot x_0) + b (-m \cdot y_0) \\ & n \in A , 0 \le n < s,s是A中最小正整数 \\ &j \ = b - i \ \ \cdot s \\ & \: \: \: \: = b - i \ \ (a \cdot x_0 + b \cdot y_0) \\ & \: \: \: \: = a(- i \ \ \cdot x_0) + b (1 - i\ \ \cdot y_0) \\ & j \ \in A , 0 \le j \ < s,s是A中最小正整数 \\ \therefore \ & n = 0 ,j \ = 0 \\ & s | a \ , \ s | b \\ \therefore \ & s为a \ b的一个公约数 , \gcd(a,b) 为a \ b的最大公约数 \\ & \textcolor{red}{s <= \gcd(a,b)} \\ \therefore \ & \textcolor{blue}{\gcd(a,b) = s} \end{aligned} \]

拓展

  • \(a \cdot x + b \cdot y = c\),\(\gcd(a,b) | c\).

标签:mathbb,le,gcd,cdot,定理,原理,textcolor,裴蜀
From: https://www.cnblogs.com/why-123/p/17025997.html

相关文章

  • 【深入浅出Sentinel原理及实战】「基础实战专题」零基础探索分析Sentinel控制台开发指
    Sentinel控制台Sentinel提供了一个轻量级的开源控制台SentinelDashboard,它提供了机器发现与健康情况管理、监控(单机和集群)、规则管理与推送等多种功能。Sentinel控制台提......
  • 贝祖定理
    引入:1.背景:在数论中,裴蜀定理是一个关于最大公约数(或最大公约数)的定理,是法国数学家Bézout'sLemma,又称贝祖定理。2.(1) Z={...-3,-2,-1,0,1,2,3...}  (2) 2Z={...-6,-4,-......
  • 关于asan内存检测工具的原理和使用
    Hello,各位看官好,小弟的公司最近开始使用asan这个工具了,最近在晚上查了一下,不查不知道,一查吓一跳,这个工具真的是神一般的工具,所以我就花了一点时间整理了一下asan工具的......
  • vue面试之Composition-API响应式包装对象原理
    本文主要分以下两个部分对CompositionAPI的原理进行解读:reactiveAPI原理refAPI原理reactiveAPI原理打开源码可以找到reactive的入口,在composition-api/src/......
  • 采集存储计算处理卡设计原理图:619-基于6U VPX的双FMC ZU19EG 采集存储计算处理卡
    619-基于6UVPX的双FMCZU19EG采集存储计算处理卡 基于6UVPX的双FMCZU19EG采集存储计算处理卡 一、板卡概述   该板卡是采集、存储、计......
  • 通俗易懂的MySQL事务及MVCC原理,我先收藏了!
    一、事务简介与四大特性事务指的是一组命令操作,在执行的过程中,要么全部成功,要么全部失败。由引擎层支持事务,MyISAM就不支持事务,而InnoDB是支持事务的。事务具有以下四......
  • Go Map底层实现原理
    GoMap底层实现原理Gomapmap是一种key-value的键值对存储结构,其中key不能重复,底层用hash表存储。平日里我们一般是这样使用map的://创建//map[KeyType]ValueType......
  • scarpy架构组成和工作原理
     汽车之间案例:importscrapyclassCarSpider(scrapy.Spider):name='car'allowed_domains=['https://car.autohome.com.cn/price/brand-15.html']......
  • 一致性哈希算法原理及实际应用
    最近有一位读者跟我交流,说除了算法题之外,系统设计题是一大痛点。算法题起码有很多刷题平台可以动手实践,但系统设计类的题目一般很难实践,所以看一些教程总结也只是一知半解,......
  • 浅谈存储系统:LSM 树设计原理
    我在上篇文章ApachePulsar的架构设计中介绍了Pulsar存算分离的架构,其中broker只负责计算,由BookKeeper负责底层的存储,我还画了这样一张图说明BookKeeper读写分......