Editing Coprime integers (section)

== Notation and testing ==
When the integers {{mvar|a}} and {{mvar|b}} are coprime, the standard way of expressing this fact in mathematical notation is to indicate that their greatest common divisor is one, by the formula {{math|1=gcd(''a'', ''b'') = 1}} or {{math|1=(''a'', ''b'') = 1}}.  In their 1989 textbook ''[[Concrete Mathematics]]'', [[Ronald Graham]], [[Donald Knuth]], and [[Oren Patashnik]] proposed an alternative notation <math>a\perp b</math> to indicate that {{mvar|a}} and {{mvar|b}} are relatively prime and that the term "prime" be used instead of coprime (as in {{mvar|a}} is ''prime'' to {{mvar|b}}).<ref>{{citation|first1=R. L.|last1=Graham|first2=D. E.|last2=Knuth|first3=O.|last3=Patashnik|title=[[Concrete Mathematics]] / A Foundation for Computer Science|publisher=Addison-Wesley|year=1989|page=115|isbn=0-201-14236-8}}</ref>

A fast way to determine whether two numbers are coprime is given by the [[Euclidean algorithm]] and its faster variants such as [[binary GCD algorithm]] or [[Lehmer's GCD algorithm]].

The number of integers coprime with a positive integer {{mvar|n}}, between 1 and {{mvar|n}}, is given by [[Euler's totient function]], also known as Euler's phi function, {{math|''φ''(''n'')}}.

A [[Set (mathematics)|set]] of integers can also be called coprime if its elements share no common positive factor except 1. A stronger condition on a set of integers is pairwise coprime, which means that {{mvar|a}} and {{mvar|b}} are coprime for every pair {{math|(''a'', ''b'')}} of different integers in the set. The set {{math|{2, 3, 4} }} is coprime, but it is not pairwise coprime since 2 and 4 are not relatively prime.