Областная олимпиада по математике, 2009 год, 11 класс

Определите все натуральные числа $n = p_1 p_2 \dots p_k$, которые являются делителем числа $(p_1 + 1)(p_2 + 1) \dots (p_k + 1)$, где $p_1 p_2 \dots p_k$ — разложение числа $n$ на простые множители (не обязательно различные).

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

Ответ :$n=3^{\frac{ k}{2}}\cdot{2^{\frac{k}{2}}} $,если $k $-четное; $n=3^{\frac{k-1}{2}}\cdot {2^{\frac {k+1}{2}}} $, если $k $-нечетное

Решение. Лемма 1. Числа $n $ и $n+1$ взаимнопросты для $n>1$, где $n\in N $.

Доказательство. Понятно,что $n+1$ не делится нацело на $n $. Ведь $\dfrac {n+1}{n} =1+\dfrac {1}{n} $; $\dfrac {1}{n}\in N $ только если $n=1$; но по условию $n>1$. Пусть $n $ и $n+1$ имеют общий делитель $y$, тогда $n=ay;n+1=by $, где $a $ и $b $ - взаимнопросты. Тогда $by-ay=y (b-a)=1$, то есть $y=1$. Другими словами, числа $ n $ и $n+1$ не имеют общих множителей.

Пусть $A=(p_1+1)(p_2+1)... (p_k+1) $

Заметим, что если $n $ состоит из $2m=k $ простых множителей, то $n=3^m2^m $, а если $n $ состоит из $2m+1=k $ простых множителей, то $n=3^m2^{m+1} $. Если $n=3^m2^m $, то $ A=4^m3^m $. Каждая тройка $n $перешла в четверку$A $, а двойка -в тройку. $\dfrac {A}{n}=2^m\in N $. Аналогично для $n= 3^m2^{m+1} $. Получается $\dfrac {A}{n}=3\cdot {2^{m-1}}\in N $.

Покажем,что в $n $, делящее число $A $ нацело, является произведение двоек и троек. По лемме 1 ,$p_1$ и $p_1+1$ взаимнопросты. Чтобы $p_1$ вошло в состав множителей числа $ A $, должно быть простое число $p_1-1$,а такая пара лишь одна $p_1=3;p_1-1=2$.

Пусть $m=(p_{1}+1)...(p_{k}+1)$. Тогда если взять: $n= 3^2•2^4$, тогда $m=3^4•2^4$, значит $m$ делится $n$. Но ты не указал этот ответ.

Вот правильное решение:

$Ответ: n=2^x*3^y,$где $x,y$ натуральный числа такие что $2y \geq x \geq y$.

Заметим что $n$ не может иметь простого делителя больше 3. Докажем это противного, пусть имеет. Рассмотрим самый большой простой делитель $n$ - $p_{i}$. Так как $(p_{k}+1)...(p_{1}+1)$ делится на $p_{i}$, тогда найдётся $j$ что: $р_{j}+1$ делится на $p_{i}$. Но так как он максимум, и больше всех $p_{j}+1$, кроме $p_{i}=p_{j}$, то $p_{i}+1$ делится на $p_{i}, что невозможно.

Значит $n=2^x*3^y$, из чего выходит что $(p_{1}+1)...(p_{k}+1)=2^{2y}*3^x$. Из этого выходит что $2y \geq x \geq y$.