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

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?

• How are the $x_i$ defined? If $x_i$ is the greatest integer of the set you are considering, is $x_{i+1}$ the next integer that satisfies $\text{gcd}(x_{i+1}, 6)=1$? Sep 28 '20 at 20:24
• Thanks for your question. I'm assuming that $x_i$ is in ascending order. I'll add this point to the question. Sep 28 '20 at 20:25
• I am sorry to be so picky, but I imagine that you cannot choose, for example, $x_n=n^n+c$ such that $\text{gcd}(n^n+c,6)=1$ right? How does this follow from the definition? I imagine that, once you have $x_i$, you define $x_{i+1}$ as the smallest number bigger than $a_i$ such that $\text{gcd}(x_{i+1},6)$, right? Sep 28 '20 at 20:30
• I appreciate the questions. :-). $n$ is just the number of elements. $x_i$ could $=n$ if gcd$(n,6) =1$. I am trying to find out if the value $n^n$ is lways less regardless of the $n$ distinct values chosen. A list of $n$ distinct i$x_i$ with the product less tgan $n^n$ would be a counter example. Sep 28 '20 at 20:46

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.
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$$.