Показатели и первообразные корни
Ошибка.
Попробуйте повторить позже
Найдите все упорядоченные тройки простых чисел 
таких, что
Подсказка 1
Для начала поймем могут ли быть равные числа среди p, q, r?
Подсказка 2
Правильно, не могут! Попробуем теперь доказать следующую лемму: если p,q,r — такие различные простые числа, что p делит q^r+1 и p > 2, то либо p − 1 кратно 2r, либо q^2 − 1 кратно p. Заметим, что из условия леммы следует, что q^r сравнимо с -1, но не сравнимо с 1 по модулю p. Что можно сделать с этим сравнением?
Подсказка 3
Верно! Надо возвести его в квадрат и получить, что q^(2r) сравнимо с 1 по модулю p. Что тогда можно сказать про ord(q) по модулю p?
Подсказка 4
Точно! Он делит 2r, но не делит r. Так как p простое, то какой вывод можно сделать?
Подсказка 5
Ага! либо (ord q по модулю p) = 2, либо (ord q по модулю p) = 2r. Если верно второе, то p− 1 кратно 2r, поэтому лемму доказали. Теперь остается ее применить и поразбирать случаи. Предположим, что p, q, r — нечетные. Что следует из того, что p - 1 делится на 2r?
Подсказка 6
Верно! 0 ≡ p^q + 1 ≡ 2, то есть r = 2, а значит, противоречие. Теперь пусть q^2 - 1 делится на p. Какое тогда неравенство можно написать на p и q?
Подсказка 7
Точно! Из того, что q^2 - 1 делится на p следует, что либо (q-1)/2, либо (q+1)/2 делится на p, а значит, q > (q+1)/2 ≥ p. Теперь легко получаем противоречие. Осталось только разобрать случай, когда одно из чисел равно 2 и вычислить два других.
Ясно, что 
не кратно 
а значит 
Аналогично 
и 
то есть 
и 
различные.
_________________________________________________________________________________________________________________________________________________________________________________
Докажем теперь следующую лемму: если 
— такие различные простые числа, что 
делит 
и 
то либо 
кратно
либо 
кратно 
Из условия леммы следует, что 
сравнимо с 
по модулю 
но не сравнимо с 
поскольку 
Следовательно,
Получаем, что 
кратно 
и 
не кратно 
Поскольку 
— простое, это возможно лишь когда
или 
Если верно второе, то 
кратно 
В первом же случае получим, что 
кратно 
Лемма
доказана.
_________________________________________________________________________________________________________________________________________________________________________________
Начнём решение со случая, когда 
и 
нечётны. Поскольку 
делит 
по лемме либо 
кратно 
либо 
кратно
Но первый случай невозможен, поскольку сравнение 
влечёт за собой сравнения 
то есть 
что противоречит нашему предположению. Следовательно, 
делит 
Простое число 
нечётно, a 
и 
чётны. Значит, одно из чисел 
или 
кратно 
Отсюда следует, что 
Аналогично 
и 
противоречие.
Значит, среди чисел есть хотя бы одна двойка. Поскольку при циклической перестановке ничего не изменится, можно положить, что
Теперь 
делит 
тогда по лемме либо 
делит 
либо 
кратно 
Но первый случай невозможен,
поскольку 
делит 
и 
Следовательно, 
кратно 
По условию 
кратно 
Ранее мы
заключили, что 
откуда 
то есть 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
