Here is a cute little problem which I can’t solve. I thought I needed the answer but it turned out that I didn’t, so as far as I know there is no application.

Let *n* = *p*_{1}^{a1}…*p*_{s}^{as}, where the *p*_{i} are distinct primes and *a*_{i} positive integers. The general question asks whether φ(*n*) is always at least as big as the multinomial coefficient (*a*_{1}+…+*a*_{s})!/(*a*_{1})!…(*a*_{s}). This is true if *s* = 1 or 2, false if *s* = 4 (or larger) – the smallest example I know is 2^{7}.3^{5}.5^{3}.7^{2} = 190512000.

**Problem:** Is it true for *s* = 3? I am inclined to guess that it is, but it is quite delicate and I didn’t find a proof. (I have stopped looking now I don’t actually need this any more.)

### Like this:

Like Loading...

*Related*

##
About Peter Cameron

I count all the things that need to be counted.

It’s false: 2^51 * 3^34 * 5^20 is the smallest example.

And 2^8 * 3^5 * 5^2 * 7^2 = 76204800 is the smallest example for s = 4.

Sorry — when I said “smallest” I actually meant “largest exponent smallest” (though I didn’t know I meant that…) Thanks for the update.

Incidentally, here’s a place where I explore the combinatorial properties of primes factorizations, for anyone who likes that sort of thing —

Riffs and Rotes

If I’m not mistaken, this problem is not so much number theoretic as algebraic.

By the multinomial theorem,

(31/30)^m = ((1/2) + (1/3) + (1/5))^m

= \sum_{a+b+c=m} {m \choose a, b, c} (1/2)^a (1/3)^b (1/5)^c

= (2/15) \sum_{a+b+c=m} {m \choose a, b, c} (1/2)^{a+1} (1/3)^{b-1} (1/5)^{c-1}

= (2/15) \sum_{a+b+c=m} ({m \choose a, b, c} / \phi(2^a 3^b 5^c})

Therefore, if $2^{a+1}3^{b-1}5^{c-1} = \phi(2^a 3^b 5^c) \ge {m \choose a, b, c}

for all a, b, c with a+b+c = m, then

(31/30)^m \le (2/15)\sum_{a+b+c=m} 1 = (2/15)m^2.

But this inequality holds for only finitely many values of m since

lim_{m\rightarrow \infty} (1/m^2)(31/30)^m = \infty.

Therefore, for any sufficiently large m, there exist a, b, c with a+b+c = m and

$\phi(2^a 3^b 5^c) < {m \choose a, b, c}

Oops! I just noticed that “n^2” in my earlier comment should be “(n+1)^2”. The conclusion is the same though. My apologies.