首页 > 其他分享 >GCD (最大公因数)的性质

GCD (最大公因数)的性质

时间:2024-08-08 21:29:28浏览次数:12  
标签:... frac gcd cdot ...... GCD 公因数 性质

GCD 的性质总结

  1. \(gcd(a_1,a_2,......a_n)=gcd(|a_1|,|a_2|,......|a_n|)\)
  2. \(gcd(a,0)=gcd(a,a)=|a|\)
  3. \(gcd(a_1,a_2,......a_{n-1},a_n)=gcd(gcd(a_1,a_2),a_3,......a_{n-1},a_n)\)
  4. 对于不全为零的整数 \(a_1,a_2,a_3,......a_{n-1},a_n\), $ \forall 1 < k < n-1\(,\)gcd(a_1,a_2,a_3,......a_{n-1},a_n)=gcd(gcd(a_1,a_2,a_3,...a_{k}),gcd(a_{k+1},...,a_n)) $
  5. 对于不全为零的整数 \(a_1,a_2,a_3,......a_{n-1},a_n\) , \(gcd(m\cdot a_1,m\cdot a_2,...m\cdot a_n)=|m|\cdot gcd( a_1,a_2,a_3,......a_{n-1},a_n)\)
  6. 对于不全为零的整数 \(a_1,a_2,a_3,......a_{n-1},a_n\) ,若 \(gcd(a_1,a_2,a_3,...,a_n)=d\) , 则有 \(gcd(\frac{a_1}{d},\frac{a_2}{d},\frac{a_3}{d},...,\frac{a_n}{d})=1\)
  7. \(gcd(a_1,a_2,...,a_n,d) \leq d\) ,特别的 \(gcd(a_1,a_2,...,a_n,1)=1\) , 且\(gcd(a_1,a_2,...,a_n)=1\)且 \(a_i != 1\) 是\(a_1,a_2,...,a_n\) 中至少存在一对\(a_i,a_j\) 互质 的充分必要条件.

标签:...,frac,gcd,cdot,......,GCD,公因数,性质
From: https://www.cnblogs.com/cxjy0322/p/18349773

相关文章

  • Spring事务传播性质导致事务失效
    this导致事务失效的原因当我们在一个事务中调用另一个对象的方法时,如果这个方法中使用了this关键字,事务可能会失效。这是因为this关键字代表当前对象的引用,而事务是基于数据库连接的,每个数据库连接有自己的事务上下文。如果在一个事务中调用另一个对象的方法,而这个方法中使用了t......
  • 青少年编程与数学 01-008 在网页上完成计算 01课题、数学课程的性质
    青少年编程与数学01-008在网页上完成计算01课题、数学课程的性质课题要求一、课程性质二、数学的本质三、数学的社会功能四、数学教育的重要性五、数学教育的目标六、数学教育的特性七、连贯性和实践性连贯性(Coherence)实践性(Practicality)八、个性化进度与节奏九、数......
  • 可逆矩阵的概念、定理、判断条件和性质(线性代数基础)
    可逆矩阵的概念、定理、判断条件和性质可逆矩阵的概念定义:设AAA为n......
  • iOS基础---多线程:GCD、NSThread、NSOperation
    系列文章目录iOS基础—多线程:GCD、NSThread、NSOperationiOS基础—CategoryvsExtension文章目录系列文章目录一、GCD1.GCD的任务、函数、队列a.任务b.函数c.队列2.GCD的使用a.同步函数+并发队列b.异步函数+并发队列c.同步函数+串行队列d.异步函数+串行队列e.同步函......
  • P10463 Interval GCD
    P10463IntervalGCD原题传送门思路首先,有个性质:对于任意多整数,它们的最大公约数与它们的差分序列的最大公约数相同,可以通过以下证明。\(\foralla,b,c\in\mathbb{N}\text{,有}\gcd(a,b,c)=\gcd(a,b-a,c-b)\)\(\text{证明:设}d\mida,d\midb,d\midc\)......
  • 基础数论 欧拉定理与exgcd
    欧拉定理:若正整数\(a,n\)互质,则\(a^{\varphi(p)}\equiv1(\bmodp)\)推论(扩展欧拉定理):\[a^b\equiv\begin{cases}a^{b\\bmod\\varphi(p)}\\\\\\\\\\gcd(a,p)=1\\a^b\\\\\\\\\\\\\\\\\\\\\\gcd(a,p)!......
  • 快速 GCD
    预处理GCD\(O(n)\)预处理,\(O(1)\)查询两个小于\(n\)的数的快速\(\gcd\)。引理对于任意正整数\(n\),可以将\(n\)写成\(n=abc\),满足\(a,b,c\)任意一个小于\(\sqrt{n}\)或为质数。考虑归纳,首先对于\(1\),显然成立。否则,设\(n\)的最小质因子为\(p\),设\(\dfrac{n......
  • 最高法-为减少生活不便、照顾、改善全家人生活购买的房屋,显然非商业投资性质的,也符合
    1.(2021)最高法民终945号  重庆进出口融资担保有限公司、刘兴碧等申请执行人执行异议之诉民事二审民事判决书本院认为:本院认为,案件的争议焦点为:刘兴碧、田多学对案涉房屋是否享有足以排除强制执行的民事权益。根据《最高人民法院关于人民法院办理执行异议和复议案件若干问题的......
  • gcd之和(一维)
    gcd之和求∑i=1n......
  • 约数和倍数的性质
    约数(Divisors)约数是指能整除某个整数的其他整数。例如,对于整数(a),如果存在整数(b)使得(a=b*c),那么(b)就是(a)的约数。性质:1和自身是每个整数的约数:每个整数(a)都有至少两个约数:1和(a)本身。约数的范围:如果(d)是(n)的一个约数,则(d......