An exercise in number theory

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 = p1a1psas, where the pi are distinct primes and ai positive integers. The general question asks whether φ(n) is always at least as big as the multinomial coefficient (a1+…+as)!/(a1)!…(as). This is true if s = 1 or 2, false if s = 4 (or larger) – the smallest example I know is 27.35.53.72 = 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.)

I count all the things that need to be counted.
This entry was posted in doing mathematics, open problems and tagged , . Bookmark the permalink.

6 Responses to An exercise in number theory

1. David Bevan says:

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

2. David Bevan says:

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.

3. Jon Awbrey says:

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

4. Martin Pettet says:

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}

5. Martin Pettet says:

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.