In number theory, Euler's totient function counts the positive integers up to a given integer [math]n[/math] that are relatively prime to [math]n[/math]. It is written using the Greek letter phi as [math]φ(n)[/math] or [math]ϕ(n)[/math], and may also be called Euler's phi function. It can be defined more formally as the number of integers [math]k[/math] in the range [math]1\le k\le n[/math] for which the greatest common divisor [math]gcd[/math][math](n,k)[/math] is equal to [math]1[/math]. The integers [math]k[/math] of this form are sometimes referred to as totatives of [math]n[/math].[br]For example, the totatives of [math]n=9[/math] are the six numbers [math]1,2,4,5,7[/math] and [math]8[/math]. They are all relatively prime to [math]9[/math], but the other three numbers in this range, [math]3,6[/math], and [math]9[/math] are not, because[math]gcd(9,3)=gcd(9,6)=3[/math] and [math]gcd(9,9)=9[/math]. Therefore, [math]φ(9)=6.[/math] As another example, [math]φ(1)=1[/math] since for [math]n=1[/math] the only integer in the range from [math]1[/math] to [math]n[/math] is [math]1[/math] itself, and [math]gcd(1,1)=1.[/math][br]Euler's totient function is a multiplicative function, meaning that if two numbers [math]m[/math] and [math]n[/math] are relatively prime, then [math]φ(mn)=φ(m)φ(n)[/math].This function gives the order of the multyplicative group of integeres modulo [math]n[/math] (the group of units of the ring [math]ℤ/nℤ[/math]). It also plays a key role in the definition of the RSA encryptoin system.