Reasoning about the product of $n$ distinct, positive integers and their relation to $n^n$

Question

Let $x_1>1, x_2>1, \dots, x_n>1$ be $n$ distinct positive integers with the following properties:

• gcd$(x_i, 6) = 1$ where gcd$(a,b)$ is the greatest common divisor of $a$ and $b$.
• $x_1 < x_2 < \dots < x_n$

Does it now follow that: $n^n < \prod\limits_{i=1}^n x_i$?

It seems to me that this should be provable through considering the minimal product that satisfies the condition.

Examples:

• for $n=1$, $x_1 = 5$
• for $n=2$, $x_1, x_2 = \{5, 7\}$
• for $n=3$, $x_1, x_2, x_3 = \{5, 7, 11\}$

I am not clear how to proceed. One thought is to use induction for $n=1$ and then show that:

$$\prod\limits_{i=1}^{n+1} x_i - \prod\limits_{i=1}^n x_i\ge [(n+1)^{n+1} - (n+1)^n] + [(n+1)^n - n^n]$$

which gets me to this:

$$\left(\prod\limits_{i=1}^n x_i\right)(x_{n+1} - 1) > (n+1)^n(n) + \prod\limits_{k=0}^{n-1}{n \choose k}n^k = n^{n+1} + (n+1)\left(\prod\limits_{k=0}^{n-1}{n \choose k}n^k\right)$$

Is there a straight forward way to resolve this question? What would be a recommended way to proceed?

Answer 1

Note that for $i$ odd we have $x_i=3i+2$ while for $i$ even we have $x_i=3i+1$. If we ignore those pesky $+2$s and $+1$s we have $$\prod\limits_{i=1}^n x_i\gt 3^nn!$$ while Stirling's approximation gives $$n^n \approx n!e^n\sqrt {2\pi n}$$ For $n \gt 25$ we have $\left(\frac 3e\right)^n \gt \sqrt{2 \pi n}$ so we just have to compute the values up through $n=24$ to see the claim is correct.

Answer 2

Let's use the following simple fact: all the integers $x$ that are coprime with $6$ may be represented as $x = 6k + r$, where $0 \le r < 6$ and $\gcd(r,6) = 1$. Since there are are only two such numbers $r$ ($1$ and $5$), the sequence $y_0,y_1,\dots$ given by $$ y_{2k} = 1 + 6k, \quad y_{2k + 1} = 5 + 6k $$ contains all the positive integers that are relatively prime with $6$.

Let's now order given numbers $1 < x_1 < x_2 < \dots < x_n$ and note that $$x_k \ge y_k > 3k \quad\quad k=1,\dots,n$$ and so we have inequality $$\prod_{k=1}^{n}x_k > \prod_{k=1}^{n}3k = 3^nn!.$$ Now let's prove that $$3^nn! > n^n\tag{*}$$ by induction. For $n = 1$ this is true. Suppose that (*) is holds for some $n$. Then $$ 3^{n+1}(n+1)! = 3(n+1)\cdot 3^n n! > 3(n+1)n^n > (n+1)\cdot (n+1)^n = (n+1)^{n+1}. $$ Here we use inequality $(n + 1)^n < 3 n^n$ given by monotonically increasing sequence $(1 + \frac{1}{n})^n \to e < 3$.