A positive integer $N$ is rioplatense if it satifies the following conditions: 1 -There exist $34$ consecutive integers such that its product is divisible by $N$, but none of them is divisible by $N$. 2 - There not exist $30$ consecutive integers such that its product is divisible by $N$, but none of them is divisible by $N$. Determine all rioplatense numbers.
Problem
Source: Rioplatense L2 2023 #5
Tags: number theory
TiagoCavalcante
12.07.2024 21:23
Lemma 1: No prime number $N$ can be rioplatense.
ProofIf $N$ is prime, to divide the product of 34 integers, it must divide at least one of them. Thus, no prime $N$ satisfies the first condition.
Lemma 2: If $N$ has a prime factor $\leq 29$, then $N \leq 58$.
ProofAssume $N$ has its smallest prime factor $p \leq 29$. Consider the sequence $\frac{N}{p}, \frac{N}{p}+1, \dots, \frac{N}{p}+29$. The product of these 30 integers is divisible by $N$ as one of these numbers is divisible by $p$. Hence, $N$ must divide one of these numbers, implying $N \leq \frac{N}{p}+29 \leq \frac{N}{2}+29$, thus $N \leq 58$. However, no number $\leq 34$ satisfies the first condition, and verification shows that every non-prime $N$ between 35 and 58 divides $30!$ but does not divide any number in the set ${1, 2, \dots, 30}$, thus failing the second condition.
Lemma 3: If $N$ has more than two prime factors, and all of them are $>29$, then $N$ cannot satisfy both conditions.
ProofConsider any prime factor $p$ of $N$ and the sequence $i, i+1, \dots, i+29$ where $i \equiv 0 \pmod{p^\alpha}$ and $i \equiv -1 \pmod{\frac{N}{p^\alpha}}$, with $p^\alpha \parallel N$ (the existence of $i$ is guaranteed by the Chinese Remainder Theorem). Thus, $N \mid i(i+1)$ (and consequently $N \mid i(i+1)\cdots(i+29)$), but $N \nmid i, i+1, \dots, i+29$ as otherwise $p$ would divide both $i$ and $i+j$ for some $j \le 29$, and consequently $p \mid (i + j) - i = j$, what is impossible as $p > 29$.
SolutionsThe only candidates for rioplatense numbers are $N = p^\alpha$ for some prime $p$ and $\alpha > 1$. If $p > 31$, then $p \geq 37$, and $p$ cannot divide more than one of the 34 consecutive integers, and consequently $N$ fails the first condition. If $p \leq 29$, $N$ does not satisfy the second condition. Hence, the only possibility left is $N = 31^\alpha$ for any integer $\alpha > 1$. It is easy to see that such $N$ works.