Олимпиада Туймаада по математике. Старшая лига. 2004 год

О натуральных числах $m$ и $n$ известно, что $m > n^{n-1}$ и все числа $m+1$, $m+2$, $\dots$, $m+n$ — составные. Докажите, что существуют такие различные простые числа $p_1$, $p_2$, $\dots$, $p_n$, что $m+k$ делится на $p_k$ при $k = 1$, 2, $\dots$, $n$. ( C.A.Grimm )

Комментарий/решение

Заметим что $m>n^{n-1}>lcm[1,2,…,n-1]=q$

Определим $a_j=\dfrac{m+j}{gcd(m+j,q)} \forall j \in [1,2,..,n]$

Из неравенство $a_j>1$, и допустим что $\exists j,i$ так что $p | a_j, a_i$ тогда:

$V_p(m+j) > V_p(gcd(m+j,q))=MIN[V_p(m+j);V_p(q)] \Rightarrow V_p(m+j) > V_p(q)$ и аналогично $V_p(m+i) > V_p(q)$ что ведет к тому что $|j-i|$ делится на $p^{V_p(q)}$, но $q$ делится на $j-i$ отсюда противоречие.

Значит все $a_j$ взаимно просты и беря с каждого по одному простому числу, мы доказываем задачу.