0
$\begingroup$

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.

$\endgroup$

migrated from mathematica.stackexchange.com May 23 '13 at 20:18

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

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

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Ok. So basically I was confused with the definition of a number being relatively prime to the another :-) Also [this][1] graph from wikipedia was not clear and made me think maybe there is a range of values Euler totient function gives. Thanks for the help. [1]:en.wikipedia.org/wiki/File:EulerPhi.svg $\endgroup$ – vish213 May 23 '13 at 20:34
  • $\begingroup$ @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$. $\endgroup$ – Ross Millikan May 23 '13 at 22:13
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.