Тема . Остатки и сравнения по модулю

Лемма об уточнении показателя

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела остатки и сравнения по модулю
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#83962

Пусть p   — простое число, a  и n   — натуральные числа такие, что pa−-1= 2n.
p − 1  Каким может быть количество натуральных делителей числа na?

Показать ответ и решение

При p= 2  уравнение имеет вид 2a− 1= 2n  и не имеет решений в натуральных числах, следовательно, p  нечетно.

Если a  является нечетным, то число

pa− 1   a− 1  a−2
p-− 1-= p  +p   + ...+ p+1

так же нечетно, что невозможно, следовательно a  кратно 2.

Предположим, что p− 1  кратно 4.  Степень вхождения 2  в правую часть равна v2(pa− 1)− v2(p− 1),  что, в силу LTE для числа pa− 1,  равно v2(a),  следовательно, v2(a)= n,  а значит a≥ 2n.  С другой стороны,

     a
2n = p-−-1 =pa−1+ pa−2 +...+ p+ 1> a
     p− 1

что влечет противоречие.

Таким образом, p  дает остаток 3  при делении на 4,a  — четно. Тогда p2 ≡ 32 ≡ 1 (mod 4),  то есть p2− 1  кратно 4,  а значит, в силу LTE,

v(pa− 1)= v (p2− 1)+v (a∕2)= v(p+ 1)+v (p− 1)+ v(a)− 1
 2        2        2       2       2        2

то есть степень вхождения 2 в левую часть исходного уравнения v2(p+ 1)+ v2(a)− 1,  что не превосходит

log (p +1)+ log (a)− 1= log (p+1)a
  2         2         2  2

Таким образом, верна серия неравенств

 a
p-−-1= 2n ≤ (p+-1)a
 p− 1         2

pa− 1 ≤ a (p2− 1)
       2

 a  a  ap2
p + 2 ≤ 2 + 1

При a> 2  верны неравенства a∕2> 1  и a    2a   a 2
p =(p )2 > 2p ,  сложив которые получим противоречие.

Если a= 2,  то уравнение имеет вид

p+1 =2n

В случае, если n  является составным (обозначим его произвольный делитель за d  ), имеем

    n      d nd
p= 2 − 1= (2 ) − 1

кратно 2d− 1> 1,  что невозможно в силу простоты p,  а значит n  — так же простое число.

При n =2  уравнение p+ 1= 4  имеет решение, количество делителей числа an =2n  равно 3.

Если n⁄= 2,  то число делителей числа an =2n  равно 4  (делителями являются числа 1,2,n  и 2n  ).

Ответ:

 3  или 4

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!