查看“︁互質”︁的源代码

{{pp-vandalism|small=yes}}
{{NoteTA|G1=Math}}

在[[數論]]中，'''互質'''（{{lang-en|coprime}}，[[符號]]：⊥，又稱'''-{zh-cn:互质;zh-tw:互素}-'''）是指如果兩個或兩個以上的[[整數]]的[[最大公因數]]是1<ref>{{Cite web |url=http://books.google.com.tw/books?id=2KV2rfP0yWEC&pg=PA28#v=onepage&q&f=false |title=Number Theory in Science and Communication, p.28 |accessdate=2014-10-19 |archive-date=2014-10-19 |archive-url=https://web.archive.org/web/20141019165345/http://books.google.com.tw/books?id=2KV2rfP0yWEC&pg=PA28#v=onepage&q&f=false |dead-url=no }}</ref>。依此定義：
* 如果[[數域]]是[[正整數]]<math>\mathbb{N^+}</math>，那麼1與所有正整數互質。
* 如果[[數域]]是[[整數]] <math>\mathbb{Z}</math>，那麼1和-1與所有整數互質<ref>{{Cite web |url=https://proofwiki.org/wiki/Definition:Coprime/Integers |title=ProofWiki > Definition:Coprime/Integers |accessdate=2014-10-19 |archive-date=2020-03-27 |archive-url=https://web.archive.org/web/20200327025204/https://proofwiki.org/wiki/Definition:Coprime/Integers |dead-url=no }}</ref>，而且它們是僅有與<var>0</var>互質的整數<ref>{{Cite web |url=https://proofwiki.org/wiki/Integers_Coprime_to_Zero |title=ProofWiki > Integers Coprime to Zero |accessdate=2014-10-19 |archive-date=2020-03-27 |archive-url=https://web.archive.org/web/20200327025204/https://proofwiki.org/wiki/Integers_Coprime_to_Zero |dead-url=no }}</ref>。

兩個整數{{mvar|a}}與{{mvar|b}}互質，記為<math>a \perp b</math>，也可以依其定义写成<math>\gcd(a, b) = 1</math>或<math>(a,b) = 1</math>。

{{TOC limit}}

==互質的例子==
例如8與10的最大公因數是2，不互質。

又如7、10、13的最大公因數是1，因此互質。

最大公因数可以通过[[辗转相除法]]得到。

==整集互質與兩兩互質==
三个或三个以上的整數互質有两种不同的情况：
* 這些整數的最大公因數是1，我們直接稱這些整數互質<ref>{{Cite web |url=http://math.stackexchange.com/questions/137206/a-problem-with-coprime-numbers |title=StackExchange > a problem with coprime numbers |accessdate=2014-10-19 |archive-date=2020-09-21 |archive-url=https://web.archive.org/web/20200921145827/https://math.stackexchange.com/questions/137206/a-problem-with-coprime-numbers |dead-url=no }}</ref>，也稱為'''整集互質'''（{{lang-en|setwise coprime}}）<ref>[http://books.google.com.tw/books?id=bDLecF34d8UC&pg=RA1-PA14&lpg=RA1-PA14&dq=%22setwise+coprime%22 ''Algebra II: Chapters 4-7'', p.14]</ref>。以 <math>\{6,8,9\}</math>為例：<math display=block>\gcd(6, 8, 9) = \gcd(\gcd(6, 8), 9) = \gcd(2, 9) = 1</math>
* 这些整數是两两互質的（{{lang-en|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>，任兩者皆不互質。

==性質==
性质之一：整数{{mvar|a}}和{{mvar|b}}互質，当且仅当存在整数{{mvar|x}},{{mvar|y}}，使得<math>xa+yb=1</math>。

一般地，存在整数{{mvar|x}},{{mvar|y}}使得<math>xa+yb=d</math>，其中{{mvar|d}}是{{mvar|a}}和{{mvar|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。故这两数互質。

==參考來源==
{{reflist|2}}

==外部參考==
* [http://www.numericana.com/answer/numbers.htm Final Answers > Number Theory]{{Wayback|url=http://www.numericana.com/answer/numbers.htm |date=20170517121844 }}
* [http://web.stanford.edu/class/cs103x/cs103x-notes.pdf 史丹福大學離散結構講義]{{Wayback|url=http://web.stanford.edu/class/cs103x/cs103x-notes.pdf |date=20200930065524 }}
* [http://books.google.com.tw/books?id=qToTAgAAQBAJ&pg=PA45#v=onepage&q&f=false Abstract Algebra: An Inquiry Based Approach, p.45]{{Wayback|url=http://books.google.com.tw/books?id=qToTAgAAQBAJ&pg=PA45#v=onepage&q&f=false |date=20141020021309 }}

[[Category:数论]]