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 = 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.)

About Peter Cameron

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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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