互素
跳转到导航
跳转到搜索
在数论中，互素（英语：coprime，符号：⊥，又称互质）是指如果两个或两个以上的整数的最大公因数是1[1]。依此定义：
- 如果数域是正整数<math>\mathbb{N^+}</math>，那么1与所有正整数互素。
- 如果数域是整数 <math>\mathbb{Z}</math>，那么1和-1与所有整数互素[2]，而且它们是仅有与0互素的整数[3]。
两个整数a与b互素，记为<math>a \perp b</math>，也可以依其定义写成<math>\gcd(a, b) = 1</math>或<math>(a,b) = 1</math>。
互素的例子[编辑]
例如8与10的最大公因数是2，不互素。
又如7、10、13的最大公因数是1，因此互素。
最大公因数可以通过辗转相除法得到。
整集互素与两两互素[编辑]
三个或三个以上的整数互素有两种不同的情况：
- 这些整数的最大公因数是1，我们直接称这些整数互素[4]，也称为整集互素（英语：setwise coprime）[5]。以 <math>\{6,8,9\}</math>为例：<math display=block>\gcd(6, 8, 9) = \gcd(\gcd(6, 8), 9) = \gcd(2, 9) = 1</math>
- 这些整数是两两互素的（英语：pairwise coprime）。以<math>\{7,8,9\}</math>为例：<math display=block>\gcd(7, 8) = \gcd(7, 9) = \gcd(8, 9) = 1 \Rightarrow \gcd(7, 8, 9) = \gcd(\gcd(7, 8), 9) = \gcd(7, \gcd(8, 9)) = \gcd(\gcd(7, 9), 8) = 1</math>
两两互素是较为严格的互素，如果一个整数集合是两两互素的，它也必定是整集互素，但是整集互素不必然是两两互素，甚至可能两两皆不互素，例如<math>\gcd(6,15,10)=1</math>，是整集互素，但<math>\gcd(6,15)=3</math>、<math>\gcd(15,10)=5</math>、<math>\gcd(10,6)=2</math>，任两者皆不互素。
性质[编辑]
性质之一：整数a和b互素，当且仅当存在整数x,y，使得<math>xa+yb=1</math>。
一般地，存在整数x,y使得<math>xa+yb=d</math>，其中d是a和b的最大公因数（贝祖等式）。
判别方法[编辑]
- 两个不同的素数一定互素。例如，2与7、13与19。
- 一个素数，另一个不为它的倍数，这两个数互素。例如，3与10、5与 26。
- 1和任何一个自然数都互素。如1和9908。
- 相邻两个自然数互素。如15与16。
- 相邻两个奇数互素。如49与51。
- 较大数是素数，则两个数互素。如97与88。
- 两数都是合数（二数差较大），较小数所有的素因数，都不是较大数的因数，这两个数互素。如357与715，357=3×7×17，而3、7和17都不是715的因数，故这两数互素。
- 两数都是合数（二数差较小），这两数之差的所有素因数都不是较小数的因数，这两个数互素。如85和78。85－78=7，7不是78的因数，故这两数互素。
- 两数都是合数，较大数除以较小数的余数（大于“1”）的所有素因数，都不是较小数的因数，则两数互素。如 462与 221，462÷221=2...20，20=2×2×5。2、5都不是221的因数，故这两数互素。
- 辗转相除法。如255与182。255－182=73，182－（73×2）=36，73－（36×2）=1，则（255，182）=1。故这两数互素。
参考来源[编辑]
- ^ Number Theory in Science and Communication, p.28. [2014-10-19]. （原始内容存档于2014-10-19）.
- ^ ProofWiki > Definition:Coprime/Integers. [2014-10-19]. （原始内容存档于2020-03-27）.
- ^ ProofWiki > Integers Coprime to Zero. [2014-10-19]. （原始内容存档于2020-03-27）.
- ^ StackExchange > a problem with coprime numbers. [2014-10-19]. （原始内容存档于2020-09-21）.
- ^ Algebra II: Chapters 4-7, p.14