AoPS - Problem

Loading [MathJax]/jax/element/mml/optable/BasicLatin.js

Problem

Source: 2006 MOP Homework Red NT 2

Tags: number theory, divisible

parmenides51

12.04.2020 02:03

Determine all pairs of positive integers $(m,n)$ such that m is but divisible by every integer from $1$ to $n$ (inclusive), but not divisible by $n + 1, n + 2$ , and $n + 3$ .

Al3jandro0000

12.04.2020 04:52

We have $n!\mid m$ and $d\nmid m: d\in\{n+1,n+2,n+3\}$ . So we have $\gcd (d,n!)<d$ .

Let

$p_i$ be a prime divisor of

$k$ . Since

$p_i\le \frac{k}{2}<k$ we get

$p_i\mid (k-1)!$ . Let

$\nu_{p_i}(k)=u_i$ . Thus since

$p_i\ge 2$ we have

$\sum_{l=1}^\infty\left\lfloor \frac {k-1}{p_i^l}\right\rfloor\ge u_i$ and so

$\gcd ((k-1)!,k)=k$ . Similarly with

$k+1$ and

$k+2$ with minor work in

$\nu_2, \nu_3$ .

So this implies $n+1,n+2,n+3$ are primes, but this is impossible. So we have $n=1$ or $n=2$ . If $n=1$ this implies any $(m,1): \gcd(m,6)=1$ works. If $n=2$ this implies any $(m,2): \gcd(m,15\cdot 4)<4$ works.