Показатели и первообразные корни
Ошибка.
Попробуйте повторить позже
Пусть 
— простое число. Оказалось, что 
— простое. Докажите, что 
является первообразным корнем по модулю
Подсказка 1
Пусть s — показатель 2 по модулю p. Какие значения может принимать s?
Подсказка 2
Верно! s — это одно из чисел 2, 4, q, 2q или 4q. Поскольку p — простое число, то по модулю p есть первообразный корень. Тогда остаток 2 — некоторая степень k этого первообразного корня. Тогда мы знаем, что 4q | sk. Как доказать, что s не может быть равно 2 или 4?
Подсказка 3
Точно! Тогда бы получилось, что 16 сравнимо с 1 по модулю p, что невозможно для p вида 4q+1 с простым q. Для того, чтобы доказать, что s не может быть равно q или 2q вспомним, что 4q | sk. Какими свойствами обладает k?
Подсказка 4
Верно! В обоих случаях k четно, поэтому 2 является квадратичным вычетом по модулю p. Возможно ли это?
Пусть 
— первообразный корень по модулю 
и 
Тогда 
по малой теореме Ферма, а потому 
С
другой стороны, 
поскольку 
Таким образом, 
следовательно 
Ясно, что тогда
В случае 
имеем 
поэтому 
следовательно, 
поскольку 
Очевидно, что
При простых 
это возможно только для 
и 
которые не представляются в виде 
для простых
Предположим, что 
Тогда 
Тогда 
является квадратичным вычетом по модулю 
Найдем символ
Лежандра
Тогда 
не может являться квадратичным вычетом по модулю 
— противоречие. В случае 
снова получаем, что 
поэтому 
но 
не может являться квадратичным вычетом по модулю 
Таким образом, 
что и
требовалось.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
