3
$\begingroup$

I've been recently learning about Phi function(Euler's totient function). I am attempting to efficiently find the $\phi(n)$ of higher numbers.

What I wanted to asked about was, if I have say:

$\frac{30}{\phi(30)} = 3.75,$

would I be able to now know that for every multiple of $30$?

$\frac{180}{\phi(180)} = 3.75,$

$\frac{999990}{\phi(999990)} = 3.75.$

I have done some research but, with me being quite the novice I am still unsure?

  • 0
    @AndréNicolas: Thanks for the help :D I will definitely be re-reading all of these responses. This has cleared up a few things already though.2012-07-14

3 Answers 3

6

We will prove that $\frac{a}{\varphi(a)}=\frac{b}{\varphi(b)}$ iff the prime factorizations of $a$ and $b$ involve the same primes.

If $p$ is a prime, then $\varphi(p^k)=(p-1)p^{k-1}$ for any positive integer $k$. So $\frac{p^m}{\varphi(p^m)}=\frac{p^n}{\varphi(p^n)}$ for all positive integers $m$ and $n$. Since $\varphi$ is multiplicative, it follows that if the prime factorizations of $a$ and $b$ involve the same primes, then $\frac{a}{\varphi(a)}=\frac{b}{\varphi(b)}$.

Conversely, suppose that $\frac{a}{\varphi(a)}=\frac{b}{\varphi(b)}$. Then the same primes divide $a$ and $b$. This is trickier to prove. Let $p_1, p_2,\dots,p_k$ be the (distinct) primes that divide $a$, listed in decreasing order, and $q_1,q_2, \dots,q_l$ be the primes that divide $b$, again listed in decreasing order.

From the fact that $\frac{a}{\varphi(a)}=\frac{b}{\varphi(b)}$, we can fairly easily conclude that $(q_1-1)\cdots(q_l-1)p_1\cdots p_k=(p_1-1)\cdots(p_k-1)q_1\cdots q_l.\tag{$1$}$

Suppose that $q_1 \ge p_1$. Since $q_1$ divides the right-hand side of $(1)$, it must divide the left-hand side. It cannot divide any $q_i-1$, and the only $p_i$ it can possibly divide is $p_1$, since $q_1 \ge p_1$. It follows that $q_1=p_1$.

Now in Equation $(1)$, cancel the terms $q_1$ and $p_1$, also $q_1-1$ and $p_1-1$. (If $p_1 \ge q_1$, use the same argument.) We obtain an equation of the same type as $(1)$. Continue in his way, from the largest primes down. We conclude hat $k=l$, and $p_i=q_i$ for all $i$.

Remark: Your post says you are interested in efficiently finding $\varphi(n)$ for large $n$. Let $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$, where the $p_i$ are distinct pimes, and the $a_i$ are $\ge 1$. Then $\varphi(n)=(p_1-1)p_1^{a_1-1} (p_2-1)p_2^{a_2-1}\cdots (p_k-1)p_k^{a_k-1}.$ For very large $n$, the above formula is not efficient, since it involves factoring $n$, which seems to be a computationally difficult problem.

It is known that if $n$ is the product of two primes, and we only know $n$ and $\varphi(n)$, we can efficiently find the two primes. So if there is an efficient way to find $\varphi(n)$ for large $n$, then the RSA encryption scheme, which is thought to be secure, is in fact not at all secure.

There has been a huge amount of effort expended in trying to "break" RSA. One can probably safely say that there is known efficient way to compute $\varphi(n)$ for very large $n$.

  • 0
    @AndréNicolas: In terms of RSA, the numbers I'm looking to compute wouldn't be that large. I was speaking more for$a$range of about 100k to 900k/1mil. I believe what you've been posting, especially the remark **is** what the problem was getting at.2012-07-14
4

No. The phi function is multiplicative, so that if $(a,b) = 1$, then $\varphi(ab) = \varphi(a)\varphi(b)$.

So let's look at $210 = 7 \cdot 30$, and $\dfrac{210}{\varphi(210)} = \dfrac{7}{\varphi(7)}\dfrac{30}{\varphi(30)}$. But is $\dfrac{\varphi(7)}{7} = 1$? No - it's not.

  • 0
    @tijko: It is a good question. The full answer turns out to be simple to state, but not all that easy to prove.2012-07-14
2

$If\ n=2^a3^b5^c\ where\ a,b,c≥1$

$\phi(n)=2^{a-1}3^{b-1}(3-1)5^{c-1}(5-1)$

=>$\frac{n}{\phi(n)} =\frac{15}{4}=3.75$

$If\ n=2^a3^b5^cp^d\ where\ a,b,c,d ≥1$

=>$\frac{n}{\phi(n)} =\frac{15p}{4(p-1)}≠3.75$