Квадратичные вычеты
Ошибка.
Попробуйте повторить позже
задана рекуррентно: 
, 
при всех натуральных 
. Пусть
делится на 
если 
— простое;
не делится на 
если 
— составное.
Подсказка 1, пункт а
В этой задаче можно явно написать формулу a_i. Что делать дальше? Примените критерий Эйлера и воспользуйтесь тем, что 3 не является квадратичным вычетом.
Подсказка 1, пункт б
Вспомните про существование показателя. По какому модулю и какому основанию стоит его рассмотреть?
Подсказка 2, пункт б
Рассмотрите показатель числа 3 по модулю m. Поймите, что он должен быть равен m-1. Почему это плохо? Воспользуйтесь теоремой Эйлера и придите к противоречию.
(a) По индукции несложно доказать, что 
для всех натуральных 
Тогда понятно, что 
Заметим, что 
то есть 
не является квадратичным вычетом по модулю 
. Тогда 
из
критерия Эйлера, что и требовалось.
(b) Пусть 
— составное число, и выполнена делимость. Отметим, что 
и 
взаимно просты (
), поэтому
определено понятие показателя 
по модулю 
Рассмотрим показатель 
числа 
по модулю 
Из 
получаем
откуда 
делится на 
то есть 
является степенью двойки. С другой стороны из первого сравнения получаем
откуда 
Теперь воспользуемся теоремой Эйлера: согласно ей, 
Поскольку 
– составное, то 
Получается, что
но 
причем 
– натуральное число. Это невозможно, поэтому мы достигли противоречия.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
