Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Well, you can use the fact that $$\phi(n)=n\prod\limits_{p\in\mathbb P,p|n}\left(1-\frac1p\right)$$ –  J. M. Jul 14 '12 at 6:18
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. –  André Nicolas Jul 14 '12 at 7:04
3  
@tijko: One needs to use all the primes that divide $n$. –  André Nicolas Jul 14 '12 at 7:20
    
@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. –  tijko Jul 14 '12 at 7:24
add comment

3 Answers 3

up vote 6 down vote accepted

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

share|improve this answer
    
I like how we addressed the two opposite aspects of this problem. Together, it's a full answer. +1 –  mixedmath Jul 14 '12 at 6:19
    
@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. –  André Nicolas Jul 14 '12 at 7:09
    
@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. –  tijko Jul 14 '12 at 7:55
add comment

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.

share|improve this answer
    
@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$. –  mixedmath Jul 14 '12 at 6:44
    
@tijko: It will work with any number that has a prime in it that is not a 2,3,5, or 7. –  mixedmath Jul 14 '12 at 6:49
    
@tijko: It is a good question. The full answer turns out to be simple to state, but not all that easy to prove. –  André Nicolas Jul 14 '12 at 7:00
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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