We have a number $n$ for which we can find 5 consecutive numbers, none of which is divisible by $n$, but their product is. Show that we can find 4 consecutive numbers, none of which is divisible by $n$, but their product is.
Problem
Source:
Tags: modular arithmetic, number theory unsolved, number theory
15.09.2011 11:57
From the givens, $n$ cannot be any prime $p$, for obvious reasons; cannot be equal to $2^2 = 4$, since one among five consecutive numbers is divisible by $4$; cannot be a power $p^{\alpha}$ of a prime $p\geq 5$, with $\alpha \geq 2$, since $p \mid a$, $p \mid b$, $a\neq b$, implies $|a-b| \geq p \geq 5$. However, we could have $n=2^{\alpha}$, with $\alpha \geq 3$, since $2^{\alpha} \mid (2^{\alpha - 1} - 1)2^{\alpha - 1}(2^{\alpha - 1}+1)(2^{\alpha - 1}+2)(2^{\alpha - 1}+3)$; we could have $n=3^{\alpha}$, with $\alpha \geq 2$, since $3^{\alpha} \mid 3^{\alpha - 1}(3^{\alpha - 1}+1)(3^{\alpha - 1}+2)(3^{\alpha - 1}+3)(3^{\alpha - 1}+4)$. Also notice that $5\cdot 7\cdot 8\cdot 9\cdot 11 \mid 7\cdot 8\cdot 9\cdot 10\cdot 11$, but not four consecutive out of them, so we cannot just use those five guaranteed by the givens. For $n=2^{\alpha}$, with $\alpha \geq 3$, we can take $2^{\alpha} \mid (2^{\alpha - 1} - 1)2^{\alpha - 1}(2^{\alpha - 1}+1)(2^{\alpha - 1}+2)$; for $n=3^{\alpha}$, with $\alpha \geq 2$, we can take $3^{\alpha} \mid 3^{\alpha - 1}(3^{\alpha - 1}+1)(3^{\alpha - 1}+2)(3^{\alpha - 1}+3)$. In all other cases, $n$ has at least two distinct prime factors, so we can write $n = k\ell$, with $k,\ell > 1$, $\gcd(k,\ell) = 1$. Take $m\equiv 0 \pmod{k}$, $m\equiv -1 \pmod{\ell}$, by the Chinese Remainders Theorem; so $k \mid m$ and $\ell \mid m+1$, therefore $k\ell = n \mid (m-1)m(m+1)(m+2)$, but $k \nmid m-1$, $k \nmid m+1$, $\ell \nmid m+2$, $\ell \nmid m$.
30.06.2014 15:51