Loading [MathJax]/jax/output/SVG/jax.js

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


Определите все натуральные числа n=p1p2pk, которые являются делителем числа (p1+1)(p2+1)(pk+1), где p1p2pk — разложение числа n на простые множители (не обязательно различные).
посмотреть в олимпиаде

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

  1
8 года 6 месяца назад #

Ответ :n=3k22k2,если k-четное; n=3k122k+12, если k-нечетное

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

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

Пусть A=(p1+1)(p2+1)...(pk+1)

Заметим, что если n состоит из 2m=k простых множителей, то n=3m2m, а если n состоит из 2m+1=k простых множителей, то n=3m2m+1. Если n=3m2m, то A=4m3m. Каждая тройка nперешла в четверкуA, а двойка -в тройку. An=2mN. Аналогично для n=3m2m+1. Получается An=32m1N.

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

  2
5 года 3 месяца назад #

Пусть m=(p1+1)...(pk+1). Тогда если взять: n=3224, тогда m=3424, значит m делится n. Но ты не указал этот ответ.

  1
3 года 10 месяца назад #

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

Ответ:n=2x3y,где x,y натуральный числа такие что 2yxy.

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

Значит n=2x3y, из чего выходит что (p1+1)...(pk+1)=22y3x. Из этого выходит что 2yxy.