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

Question

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.

Answer 1

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).

Answer 2

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.)

Answer 3

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$.

Answer 4

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)$$