Prove that $N_n = n(n-1)/2$.

Question

Let $n\ge 2, n\in\mathbb{Z}$ and define $N_n$ to be the number of $n$-tuples $(a_1,\cdots, a_n)$ of positive integers such that $(a_1 ! - 1)\cdots (a_n ! - 1)-16$ is a perfect square. Prove that $N_n = n(n-1)/2$.

Let $(a_1,\cdots, a_n)$ be an n-tuple of positive integers such that $e_n := (a_1!-1)\cdots (a_n! - 1)-16$ is a perfect square. I think it might be possible to obtain some upper bound on the $a_i$'s, but I'm not sure how to do so. For example, perhaps each $a_i < 10$, since otherwise $(a_1 ! - 1)\cdots (a_n ! - 1)-16$ might be congruent to some residue modulo some modulus that is known to not be a residue of a perfect square (we'll call the latter a quadratic residue for convenience, even though some definitions of quadratic residues exclude 0). The quadratic residues modulo 5 for instance are $0,1,4$. The quadratic residues modulo 8 are $0,1,4$. Obviously each $a_i > 1$ as $e_{n}$ must be positive. Any $a_i \ge 4$ satisfies that $a_i! - 1\equiv 7\mod 8$. Thus the possible residues modulo 8 of $e_n$ are $7,1,3,5$. In order to achieve the residue 1, the number of indices i with $a_i\ge 4$ must differ by an even number from the number of indices $i$ with $a_i= 3$. It could be useful to consider other moduli such as 16, 12, 9, etc.

Answer 1

We claim that every solution $(a_1,\dots,a_n)$ has $n-2$ variables equal to $2$ and the other two variables equal to $3$; the formula $N_n = \binom n2 = \frac{n(n-1)}2$ follows immediately from this claim. It's easy to check that these are indeed all solutions, since then the left-hand side equals $(2!-1)^{n-2}(3!-1)^2-16 = 1^{n-2}5^2-16=9=3^2$.

Suppose first that some $a_j\ge4$. Then $a_j!$ is divisible by $4$, so $a_j!-1\equiv3\pmod4$ and hence is divisible by some prime $p\equiv3\pmod4$. Modulo this prime we have $(a_1!-1)\cdots(a_n!-1)-16\equiv-16\pmod p$; but $-1$ is a quadratic nonresidue modulo $p$ since $p\equiv3\pmod 4$, and hence so is $-16=-(4^2)$. Therefore $(a_1!-1)\cdots(a_n!-1)-16$ is not a square modulo $p$ and hence cannot be a square.

The only remaining possibilities are that $(a_1,\dots,a_n)$ consists of $k$ copies of $3$ and $n-k$ copies of $2$. We easily work out then that $(a_1!-1)\cdots(a_n!-1)-16 = (2!-1)^{n-k}(3!-1)^k-16 = 5^k - 16$, which is not a square for $k=0,1$ (and is a square for $k=2$ as noted above). The other cases can be disposed of:

• If $k\ge3$ is odd, say $k=2j+1$, then $5^k-16\equiv 5^{2j+1} = 5\cdot25^j\equiv 5\pmod 8$ which is a quadratic nonresidue; therefore $5^k-16$ is not a square modulo $8$ and hence cannot be a square.
• If $k\ge4$ is even, say $k=2j$, then $5^k-16=(5^j)^2-16$, which is strictly between the two consecutive squares $(5^j)^2$ and $(5^j-1)^2 = (5^j)^2-(2\cdot5^j-1)$ (since $2\cdot5^j-1 \ge 2\cdot25-1>16$) and hence cannot be a square.

Remarks:

• It's good to try to construct solutions so that we know what shape they have; it helps us articulate the classes of solutions we need to rule out (which is particularly important in contest questions where presumably the solver has a nice solution in mind).
• Often we want to look at integers modulo convenient primes $p$ (looking for quadratic residues in this case). Sometimes a specific numerical prime can be selected ahead of time. But I've seen multiple contest questions for which that prime depends upon a choice for the variables, as it did in the second paragraph of this answer. So we can be on the lookout for using the modular argument we have in mind, but with a $p$ that varies with the parameters rather than a fixed $p$.