4
$\begingroup$

I have been asked to prove that $\phi(n) > \dfrac{9n}{50}$ for all $n$ that have at most seven prime factors. I'm trying to think of how this relates to any theorems/ properties I have learnt regarding the totient function, but I have drawn a blank. Could anyone help to explain how the property holds?

$\endgroup$
3
  • 2
    $\begingroup$ Well, why not try a simpler problem? Suppose $n$ has a single prime factor? Can you do it then? What about two prime factors? $\endgroup$
    – lulu
    May 7 at 22:25
  • $\begingroup$ I'm not really sure where that bound for the inequality is pulled from. Looking at n with a single prime factor, I fail to see how you would make the relation that their totient function value be greater than $\dfrac{9n}{50}$ simply by observing; is there some property that I am missing that brings about this bound? $\endgroup$ May 7 at 22:47
  • 1
    $\begingroup$ Nobody said you should do it "simply by observing", it's going to take some effort. (Spoiler: that number is just a numerical accident. If you look at a counterexample for $8$ prime factors you will see the point). Why not follow my suggestion and try it for one or two prime factors? That's a lot easier and it ought to show you how to do it generally. $\endgroup$
    – lulu
    May 7 at 23:08

2 Answers 2

3
$\begingroup$

The important part is to know the first few primes, and the formula for the totient function.

$$n = \Pi_{k=0}^{m}p_k^{\alpha_k} \\ \phi (n)=n\Pi_{k=0}^{m}(1-\frac1{p_k})$$

There are at most 7 prime factors, and this can give us a lower bound. The terms in the RHS product are fractions smaller than 1, so increasing the number of terms to 7 would minimize the product. In order to make the 7 fractions as small as possible, the primes need to also be as small as possible. Hence choosing the first 7 primes would minimize the product. $$ \phi (n)=n\Pi_{k=0}^{m}(1-\frac1{p_k})\geq n\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)\left(1-\frac{1}{7}\right)\left(1-\frac{1}{11}\right)\left(1-\frac{1}{13}\right)\left(1-\frac{1}{17}\right)$$

Expand the fractions, and if you will forgive the usage of a calculator, this does prove the statement. $$ \phi (n)=n\Pi_{k=0}^{m}(1-\frac1{p_k})\geq n\frac{3072}{17017}>\frac9{50}n$$

I imagine that there is a neater proof, but I cannot think of one at the moment.

$\endgroup$
3
$\begingroup$

This answer isn't as succinct as it possibly could be, but I want to make sure everything is explained well, at least for a first pass.


I'm not sure this is the "right" answer but this is one answer:

When you calculate $\phi(n)$, you look for numbers relatively prime to $n$, i.e. they share no common prime factors with it. So you look at all of $n$'s prime factors on the number line e.g. 11, and cross out for example every $11^\text{th}$ number on the number line. Once you hit the product of it's prime factors the way you cross stuff out repeats from the beginning. The only difference between $\phi(2^5\cdot3^6)$ and $\phi(2^1\cdot 3^1)$ is that $2^5\cdot3^6$ is $\frac{2^5\cdot3^6}{2^1\cdot 3^1}$, or $2^4\cdot3^5$ times larger, so $\phi(2^5\cdot3^6)=\frac{2^5\cdot3^6}{2^1\cdot 3^1}\phi(2\cdot3)$. This isn't the best interpretation, but hopefully you see what I mean. Anyways, as you could guess the general pattern is:

$\phi(n)=\frac{n}{\rho}\phi(\rho)$,

where $\rho$ is the product of the prime factors that go into the prime factorization of $n$ (you might've even seen this before). Now, we can rearrange this to get:

$\phi(n)=\left(\frac{\phi(\rho)}{\rho}\right)n$

where here the $\left(\frac{\phi(\rho)}{\rho}\right)n$ part looks an awful lot like the $\left(\frac{9}{50}\right)n$ part that you see in your problem.

So now we just have to find the smallest possible value of $\left(\frac{\phi(\rho)}{\rho}\right)$ for up to a total of seven prime factors and see what we get. Firstly, you notice that if $p_1,p_2,...$ are the primes dividing $n$ then

$\left(\frac{\phi(\rho)}{\rho}\right)=\frac{p_1-1}{p_1}\cdot\frac{p_2-1}{p_2}\cdot...$

and since for any prime $p$, $\frac{p-1}{p}<1$, this only gets smaller the more primes you add (multiplying by a number less than 1 makes it smaller).

Cool. So you're going to want to use all 7 primes. Now the question is, which 7 distinct primes make this value as small as possible?!? Well, the answer to that is simple. Just as you know $\lim_{x\to\infty}\frac{x-1}{x}$ approaches 1, the higher the value of $p$ is the higher the value of $\frac{p-1}{p}$ is, just like if you're 1 year younger than someone, when you're 1 they're twice your age but by the time they're 60, the phenomenon is that you're age is $\frac{60}{61}$ of theirs! Or you could explain this the boring way, which is that as $p$ gets larger $\frac1p$ gets smaller, so it's negative, $-\frac1p$, as you're subtracting it, gets smaller, and so $1-\frac1p=\frac{p-1}{p}$ gets larger.

So to minimize $\left(\frac{\phi(\rho)}{\rho}\right)$ you simply want to choose the smallest 7 distinct primes possible (i.e. the seven smallest different ones - remember you want have seven which is your limit, but you can't pick a prime for $\frac{p_1-1}{p_1}\cdot\frac{p_2-1}{p_2}\cdot...$ more than once)! That would be 2, 3, 5, 7, 11, 13, and 17 of course. Now we just need to calculate the coefficient $\left(\frac{\phi(\rho)}{\rho}\right)$ for those 7 primes. The answer comes out to about 0.18052535699, which is actually a slightly better bound than your lower bound $\frac{9}{50}=0.18$

$\left(\frac{\phi(\rho)}{\rho}\right)=\frac{(p_1-1)(p_2-1)(p_3-1)(p_4-1)(p_5-1)(p_6-1)(p_7-1)}{p_1p_2p_3p_4p_5p_6p_7}$

$=\frac{2^{11}\cdot3^2\cdot5}{2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17}$

$=\frac{2^{10}\cdot3}{7\cdot11\cdot13\cdot17}$

$\approx0.18052535699$ (of course you could also show that $\frac{2^{10}\cdot3}{7\cdot11\cdot13\cdot17}$ is a strictly larger bound than the $\frac9{50}$ by cross multiplying their numerators and denominators - $(2^{10}\cdot3)\cdot50>(7\cdot11\cdot13\cdot17)\cdot9$, etc, you get the idea)

Now, this isn't an absolutely rigorous proof obviously, but you get the idea.

The great thing about this method is that it generalizes to when the number of primes is even greater than seven!!! :)


Also as a side note, the precise generalization of this for a maximum of $L$ prime factors is:

$\phi(n)\ge\left[\prod_{i=1}^{L}\frac{p_i-1}{p_i}\right]n$

where $p_i$ is the $\text{i}^\text{th}$ smallest prime, e.g. $p_1=2$, $p_2=3$, $p_3=5$, and so on and so forth.

From this formula, you can see that if you were granted 9 or even ten primes, this lower bound would've gotten even smaller due to the larger number of primes; and conversely less primes makes this bound tighter. Again, we choose the $L$ smallest primes because we basically want to answer the question "what makes this coefficient as small as possible?" And that is why we are trying to minimize it rather than maximize it, btw, because we want it to be low enough to account for the lowest value possible, so we have to see what that smallest possible value is; since you have that $\phi(n)$ is greater than something, you're really just trying to catch the lowest value of that something across all possibilities you can consider and make sure you are accounting for it. This isn't my best description, but it works fairly well.

$\endgroup$
1
  • $\begingroup$ Oh yeah its basically already like the question math.stackexchange.com/questions/773119/… . except basically the idea here is that you're to pull out an $n$ from the Euler-Phi function. That sets you up to solve the problem. Isn't that so neat?!? :) :) $\endgroup$ May 7 at 23:41

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.