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?

  • 1
    Well, you can use the fact that $$\phi(n)=n\prod\limits_{p\in\mathbb P,p|n}\left(1-\frac1p\right)$$2012-07-14
  • 2
    The assertion $\frac{a}{\varphi(a)}=3.75$ is not correct when $a=999990$. This is because $999990$ is divisible by the primes $41$ and $271$, but $\varphi(999990)$ is not.2012-07-14
  • 3
    @tijko: One needs to use *all* the primes that divide $n$.2012-07-14
  • 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
    I like how we addressed the two opposite aspects of this problem. Together, it's a full answer. +12012-07-14
  • 0
    @mixedmath: I decided to write a completely full answer. The ratios for $a$ and $b$ are equal **iff* $a$ and $b$ are divisible by the same primes.2012-07-14
  • 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: You asked if every multiple of $30$ behaved the same here, but I presented a multiple that doesn't behave like you thought (has a ratio of $3.75$). To calculate it, I showed that a counterexample is $210$. And to actually compare $210/\varphi (210)$ to $30/\varphi (30)$, one just needs to calculate $7/\varphi(7)$ to $1$.2012-07-14
  • 0
    @tijko: It will work with any number that has a prime in it that is not a 2,3,5, or 7.2012-07-14
  • 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$