Войти через ВК
Каталог курсов
Каталог задач
Отзывы
Акции
О нас
Контакты
Благотворительность
Обратная связь
Политика конфиденциальности
Сведения об образовательной организации
Договор оферты
Партнерам
Телефон
Telegram
Вконтакте
Каталог задач
Отзывы
Акции
Контакты
Тема . Остатки и сравнения по модулю

Квадратичные вычеты

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

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

Задача 1#122189

Поймем для каких простых p число r⁄≡ 0 (mod p) является квадратичным вычетом.

(a) Рассмотрим множество вычетов p−1 S ={r⋅1,r⋅2,r⋅3,...,r⋅ 2 }. Докажите, что для каждого ненулевого a∈𝔽p ровно один из вычетов a,p − a содержится в S;

(b) Отождествим каждый элемент S с целым числом из множества {1,2,3,...,p − 1}. Докажите, что (r) ν(r) p =(−1) , где ν(r) — количество элементов в S, больших p−12 .

Показать доказательство

(a) Так как r⁄≡p 0, умножение на r в поле 𝔽p является биекцией. Следовательно, множество S содержит p−-1 2 различных ненулевых вычетов.

Для любого a⁄≡p 0:

  • Если a ∈S, утверждение доказано.

  • Если a ∕∈S, то a≡p r⋅k для некоторого p−1 k> 2 . Заметим, что:

    r⋅k≡ −r⋅(p− k) (mod p).

    Поскольку p− k≤ p−21, то p− a≡ r⋅(p− k) (mod p) принадлежит S.

Если бы a и p− a одновременно принадлежали S, то пусть a≡p r⋅k, p− a≡p r ⋅m, причем p−1 m,k≤ 2 ⇒ m + k≤ p− 1 тогда

0≡p a +(p− a) ≡p r⋅(m+ k)⁄≡p 0

(b) Рассмотрим произведение ∏ s∈Ss. Каждый вычет s ∈S можно представить в диапазоне p−-1 1≤ s≤ 2 . Если p−1 s> 2 , заменим его на p− s, что изменяет знак произведения на − 1. Тогда ν(r) — количество таких замен.

∏ ( ) s≡p (−1)ν(r)⋅ p−-1! , s∈S 2

и

∏ ( ) s≡p rp−21-⋅ p−-1! . s∈S 2

Приравнивая их, получаем:

p−1- ν(r) r 2 ≡ (−1) (mod p).

По критерию Эйлера:

(r) p−1- p ≡ r 2 (mod p),

откуда:

( ) rp = (−1)ν(r).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

cyberpunkMouse
cyberpunkMouse

Мы в социальных сетях

©2025 «Школково». Все права защищены.

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