# Does Euler totient function gives exactly one value(answer) or LEAST calculated value(answer is NOT below this value)?

I was studying RSA when came across Euler totient function. The definition states that- it gives the number of positive values less than $n$ which are relatively prime to $n$.

I thought I had it, until I came across this property:-

Euler Totient function is multiplicative function, that is: $\varphi(mn) = \varphi(m)\varphi(n)$

Now, if $p$ is a prime number, $\varphi(p)=p-1$.

Putting values of $p$ as 11 and 13 one by one,

$$\varphi(11)=10$$

$$\varphi(13)=12$$

Applying above stated property,

$$\varphi(11\cdot 13)=\varphi(11)\varphi(13)$$

$$\varphi(143)=12 \cdot 10$$

$$\varphi(143)=120$$

Is it correct? Does that mean we have $23$ values between $1$ and $143$ which are not relatively prime to $143$? Sorry if its something basic I'm missing. I'm not some genius at maths and came across this during study of RSA Algo. Thanks.

## migrated from mathematica.stackexchange.comMay 23 '13 at 20:18

This question came from our site for users of Wolfram Mathematica.

• Yes, $\varphi(143)=120$. Only 23 numbers between 1 and 143 share a factor with 143. – Andy Bromberg May 23 '13 at 20:20

You used it correctly, but left something out when stating multiplicativity: A number-theoretic function such as $\phi$ is called multiplicative if $\phi(nm)=\phi(n)\phi(m)$ holds if $n,m$ are relatively prime. For example $\phi(4)=2\ne\phi(2)\phi(2)$. Otherwise, your result is correct: Precisely the multiples of $11$ and the multiples of $13$ are not relatively prime to $143$, so thats $11,22,33,\ldots , 143$ and $13,26,39,\ldots,143$ (with $143$ occuring in both exception lists).
You are correct that there are $23$ numbers between $1$ and $143$ that share a factor with $143$. They are $11,22,33,\ldots 132$ ($13$ of them) and $13,26,39,\ldots 130$ ($10$ of them.)
• @vish213: The graph in Wikipedia shows that $\phi(n)$ can range essentially from $\frac {4n}{15}$ to $n$, depending on $n$, but it has only one value for a given $n$. – Ross Millikan May 23 '13 at 22:13
For some intuition about why $n$ and $m$ must be relatively prime, consider that, for $N=p_1^{a_1}p_2^{a_2}...p_n^{a_n}$, $$\varphi(N)=N \left (1-\frac{1}{p_1}\right) \left (1-\frac{1}{p_2}\right)...\left (1-\frac{1}{p_n}\right)$$ And for $M=p_m^b$, $$\varphi(M)=M \left (1-\frac{1}{p_m}\right)$$
If $p_m$ is not one of $p_1,p_2,...,p_n$ then $NM$ has $1$ more unique prime factor than $N$, and $$\varphi(NM)=NM \left (1-\frac{1}{p_1}\right) \left (1-\frac{1}{p_2}\right)...\left (1-\frac{1}{p_n}\right) \left(1-\frac{1}{p_m}\right)=\varphi(N)\varphi(M)$$ But if $p_m$ is one of $p_1,p_2,...,p_n$, then $NM$ the same number of unique prime factors as $N$, and $$\varphi(NM)=NM \left (1-\frac{1}{p_1}\right) \left (1-\frac{1}{p_2}\right)...\left (1-\frac{1}{p_n}\right) \ne\varphi(N)\varphi(M)$$
Yes there are $23$ values that are not relatively prime. The classic way to count these is to look at multiples of $11$, $\{1\cdot 11,...,12\cdot11, 13 \cdot 11 \}$, and multiples of $13$, $\{1 \cdot 13,...,10 \cdot 13, 11 \cdot 13\}$. You then look at the size of the union which is $12+10+1=23$.