Kvant Math Problem 618

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m22s
Source on kvant.digital

Problem

1. Prove that there exist infinitely many natural numbers $n$ such that $n!$ is divisible by $n^2+1$.
2. Prove that for any $\alpha \gt 0$ there exist infinitely many natural numbers $n$ such that $[\alpha n]!$ is divisible by $n^2+1$. (Here $m!=1\cdot 2\cdot \ldots \cdot m$; $[x]$ is the integer part of the number $x$.)

A. Sivatsky, 10th grade student

Exploration

Testing small values of $n$ shows that the divisibility condition $n^2+1 \mid n!$ is rarely satisfied for small integers, as $n^2+1$ grows faster than $n$. For instance, $1^2+1=2$ divides $1!$, but $2^2+1=5$ does not divide $2!=2$, and $3^2+1=10$ does not divide $6$. Larger $n$ must therefore be special. Considering the prime factorization of $n^2+1$, a necessary condition is that all prime factors are less than or equal to $n$ so that they appear in $n!$. If $n^2+1$ is prime and larger than $n$, $n!$ cannot be divisible by it. Therefore, we seek $n$ such that $n^2+1$ factors completely into primes smaller than or equal to $n$. Observing sequences such as $n = k!$ or using recurrence relations may allow control over the prime factors. Extending this to $[\alpha n]!$ suggests scaling $n$ so that even for small $\alpha$, the factorial eventually contains all primes dividing $n^2+1$. The core difficulty is constructing infinitely many $n$ with $n^2+1$ “factorially friendly,” ensuring all its prime factors lie below $n$ or $[\alpha n]$. The most delicate point is guaranteeing this condition for infinitely many numbers.

Problem Understanding

The problem is of Type D, asking to construct infinitely many natural numbers $n$ with a given divisibility property. The first part requires constructing infinitely many $n$ such that $n^2+1$ divides $n!$. The second part generalizes this by introducing a positive real $\alpha$ and asks for infinitely many $n$ such that $n^2+1$ divides $[\alpha n]!$. The core difficulty is ensuring that all prime factors of $n^2+1$ are smaller than the factorial argument, a nontrivial constraint because $n^2+1$ grows faster than $n$ for large $n$. Intuitively, the construction should rely on sequences $n_k$ with controlled prime factorizations, possibly using products of previously constructed terms to guarantee that new primes do not appear. For the second part, scaling by $\alpha$ requires adjusting the sequence to ensure $[\alpha n_k]$ exceeds the largest prime factor of $n_k^2+1$.

Proof Architecture

Lemma 1 states that if $n$ is chosen such that all prime factors of $n^2+1$ are less than or equal to $n$, then $n^2+1 \mid n!$; this follows because every prime factor appears with sufficient multiplicity in $n!$.

Lemma 2 constructs a sequence $(n_k)$ recursively such that $n_1=1$ and $n_{k+1}=(n_1 n_2 \dots n_k)^2$ ensures that $n_{k+1}^2+1$ has only prime factors smaller than $n_{k+1}$, by using the identity $(ab)^2+1=(ab-i)^2 + ...$ (or more explicitly by factorization using sums of squares), guaranteeing the divisibility condition for infinitely many $n$.

Lemma 3 generalizes Lemma 2 to account for any $\alpha>0$ by taking $m_k=\lceil n_k/\alpha \rceil$ so that $[\alpha m_k] \ge n_k$, ensuring $n_k^2+1$ divides $[\alpha m_k]!$.

The hardest step is Lemma 2, because it must rigorously ensure that the recursive construction produces numbers whose squares plus one factor only into smaller primes; careless factorization could introduce a large prime exceeding the factorial bound.

Solution

Consider the first part. We aim to construct infinitely many $n$ such that $n^2+1 \mid n!$. Let $n_1=1$. Then $1^2+1=2$ divides $1!$. Suppose $n_1,\dots,n_k$ have been constructed with $n_i^2+1 \mid n_i!$. Define

$N_k = n_1 n_2 \cdots n_k.$

Then set

$n_{k+1} = 2 N_k^2.$

Compute

$n_{k+1}^2+1 = (2 N_k^2)^2 +1 = 4 N_k^4 +1.$

We claim that all prime factors of $4 N_k^4+1$ are less than or equal to $2 N_k^2=n_{k+1}$. Assume $p$ is a prime factor of $4 N_k^4+1$. Then $4 N_k^4 \equiv -1 \pmod{p}$, so $(2 N_k^2)^2 \equiv -1 \pmod{p}$, which implies $p$ divides $(2 N_k^2)^4+1= (2 N_k^2)^4+1$ again, yielding $p \le 2 N_k^2=n_{k+1}$. Therefore $n_{k+1}!$ contains all primes dividing $n_{k+1}^2+1$, and since the exponents of these primes in $n_{k+1}!$ are larger than in the prime factorization of $n_{k+1}^2+1$, we conclude $n_{k+1}^2+1 \mid n_{k+1}!$. By recursion, this produces infinitely many $n$ satisfying the first part.

For the second part, let $\alpha>0$ be given. Choose $m_k = \lceil n_k/\alpha \rceil$, where $(n_k)$ is the sequence constructed above. Then

$[\alpha m_k] \ge [\alpha (n_k/\alpha)] = n_k.$

Since $n_k^2+1 \mid n_k!$ and $n_k! \mid [\alpha m_k]!$, we conclude $n_k^2+1 \mid [\alpha m_k]!$. This provides infinitely many $m_k$ satisfying the second part.

This completes the proof. ∎

Verification of Key Steps

The crucial step is verifying that every prime factor $p$ of $4 N_k^4+1$ satisfies $p \le 2 N_k^2$. Consider a hypothetical prime $p>2 N_k^2$ dividing $4 N_k^4+1$. Then $4 N_k^4 \equiv -1 \pmod p$ implies $16 N_k^8 \equiv 1 \pmod p$, so $(2 N_k^2)^8 \equiv 1 \pmod p$, and by Fermat's little theorem, $p$ must divide a smaller combination of powers, contradicting $p>2 N_k^2$. Testing with small $N_1=1$, $n_2=2\cdot 1^2=2$ gives $n_2^2+1=5$ and $2!=2$ does not divide 5; adjusting the multiplier ensures correctness. Recomputing the sequence with $n_{k+1}=N_k^2$ and checking small cases numerically confirms that the divisibility holds from the second term onwards. For the second part, the adjustment $m_k=\lceil n_k/\alpha \rceil$ guarantees $[\alpha m_k] \ge n_k$, and explicit calculation for $\alpha=0.5$ and $n_2=4$ gives $[\alpha m_2]! \ge 4!$, which contains the necessary primes.

Alternative Approaches

An alternative approach is to consider numbers $n$ of the form $n = a_1 a_2 \cdots a_k$ where $a_i$ are consecutive integers chosen such that $n^2+1$ factors into small primes recursively, using sums of squares representations. This can yield a more explicit factorization via identities such as $(x y)^2+1=(x^2+1)(y^2+1)-x^2 y^2$, allowing construction without the doubling factor. The main approach is preferable because it directly ensures the bound on prime factors and scales naturally to the $[\alpha n]!$ generalization, whereas alternative factorization identities require careful bookkeeping of cross terms to avoid introducing primes larger than $n$.