Editing Euler's totient function (section)

{{Short description|Number of integers coprime to and less than n}}
{{hatnote group|
{{Redirect|φ(n)||Phi}}
{{distinguish|Euler function}}
}}
[[Image:EulerPhi.svg|thumb|The first thousand values of {{math|''φ''(''n'')}}. The points on the top line represent {{Math|''φ''(''p'')}} when {{mvar|p}} is a prime number, which is {{Math|''p'' − 1.}}<ref>{{Cite web
| url = https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/v/euler-s-totient-function-phi-function
| title = Euler's totient function
| website = Khan Academy
| access-date = 2016-02-26
}}</ref>]]

In [[number theory]], '''Euler's totient function''' counts the positive integers up to a given integer {{mvar|n}} that are [[relatively prime]] to {{mvar|n}}. It is written using the Greek letter [[phi]] as <math>\varphi(n)</math> or <math>\phi(n)</math>, and may also be called '''Euler's phi function'''. In other words, it is the number of integers {{mvar|k}} in the range {{math|1 ≤ ''k'' ≤ ''n''}} for which the [[greatest common divisor]] {{math|gcd(''n'', ''k'')}} is equal to 1.<ref>{{harvtxt|Long|1972|p=85}}</ref><ref>{{harvtxt|Pettofrezzo|Byrkit|1970|p=72}}</ref> The integers {{mvar|k}} of this form are sometimes referred to as [[totative]]s of {{mvar|n}}.

For example, the totatives of {{math|1= ''n'' = 9}} are the six numbers 1, 2, 4, 5, 7 and 8. They are all relatively prime to 9, but the other three numbers in this range, 3, 6, and 9 are not, since {{math|1= gcd(9, 3) = gcd(9, 6) = 3}} and {{math|1= gcd(9, 9) = 9}}. Therefore, {{math|1= ''φ''(9) = 6}}. As another example, {{math|1= ''φ''(1) = 1}} since for {{math|1= ''n'' = 1}} the only integer in the range from 1 to {{mvar|n}} is 1 itself, and {{math|1= gcd(1, 1) = 1}}.

Euler's totient function is a [[multiplicative function]], meaning that if two numbers {{mvar|m}} and {{mvar|n}} are relatively prime, then {{math|1= ''φ''(''mn'') = ''φ''(''m'')''φ''(''n'')}}.<ref>{{harvtxt|Long|1972|p=162}}</ref><ref>{{harvtxt|Pettofrezzo|Byrkit|1970|p=80}}</ref>
This function gives the [[order (group theory)|order]] of the [[multiplicative group of integers modulo n|multiplicative group of integers modulo {{mvar|n}}]] (the [[Multiplicative group of integers modulo n|group]] of [[unit (ring theory)|unit]]s of the [[ring (algebra)|ring]] <math>\Z/n\Z</math>).<ref>See [[#Euler's theorem|Euler's theorem]].</ref> It is also used for defining the [[RSA (cryptosystem)|RSA encryption system]].