Здравствуйте. Подскажите как решить задачу: Найти все нечетные простые модули p, по которым имеет решение сравнение x(x − 2) ≡ 4 (mod p).

задан 21 Май '17 14:02

изменен 21 Май '17 14:03

Сравнение равносильно (x-1)^2=5 (mod p). Решения есть, когда 5 является квадратом по модулю p. Используем символы Лежандра. Случай p=5 очевиден, решения там есть. Пусть p=5k+r, где r=1,2,3,4. Тогда закон взаимности Гаусса даёт (5/p)=(p/5)=(r/5). Значение 1 будет при r=1, r=4. Таким образом, необходимо и достаточно условие делимости на 5 числа (p-1)(p+1)=p^2-1. Подходят p=11,19,29,31,... .

(21 Май '17 14:12) falcao

@falcao:(p/5)=(r/5) почему это равенство выполняется? Подходят p=11,19,29,31,... у этого числа р есть общий вид (p=5k+r, при k = 0, p=1,4, k=1, p=6,9...)?

(21 Май '17 14:24) SergeY
1

@SergeY: равенство (p/5)=(5k+r/5)=(r/5) выполняется в силу простейшего свойства символа Лежандра. Оно в списке свойств идёт обычно самым первым. "Числитель" всегда можно заменять на остаток от деления на "знаменатель".

Общий вид числа p я назвал: подходят простые числа вида p=5k+1 и p=5k+4. Другие значения не подходят (вида 5k+2 и 5k+3). Это полное описание.

(21 Май '17 14:30) falcao

@falcao: первый вопрос понял - спасибо. По второму же: Общий вид числа p я назвал: подходят простые числа вида p=5k+1 и p=5k+4. Для k = 0, p = 1 и 4. Для k = 1, p = 6 и 9. Для k = 2, p = 11 и 14. Для k = 3, p = 16 и 19. И т.д. У вас список такой: p=11,19,29,31,... Этот момент меня смущает.

(21 Май '17 14:34) SergeY

Числа должны быть простыми...Вопрос снят)

(21 Май '17 14:38) SergeY

@falcao: а нельзя ли подобрать такой общий вид числа p, чтобы при подстановке в него k (k=0,1,2,3,...) и r сразу получалось необходимое нечетное простое число? То есть чтобы не приходилось "в ручную" отбрасывать не подходящие варианты (четные или непростые числа).

(21 Май '17 14:51) SergeY

@SergeY: отделять простые числа от не простых придётся в любом случае. Разумно с самого начала рассматривать только простые, а потом уже для каждого p проверять, верно ли, что соседним с p будет число, кратное 5. Такая проверка очень проста.

Формулы, которая выделяла бы простые числа из натурального ряда, науке не известно.

(21 Май '17 15:10) falcao

@falcao: а если бы в таком сравнении (x-1)^2=5 (mod p) вместо 5 стояло, например, 17. Не думаю, что мы бы перебирали все варианты от 1 до 16. Значит есть какой - то еще вариант решения этой задачи?

(21 Май '17 15:54) SergeY

@falcao: p=5k+1 и p=5k+4 (k > 0, целое)?

(22 Май '17 0:02) SergeY

@SergeY: я дал полную информацию по этому вопросу. Вы сейчас что-то уточняете, но ничего нового ведь это не даст. Сказано, что подходят все простые числа, дающие при делении на 5 в остатке либо 1, либо 4. Отдельно надо также назвать значение p=5. Остальные значения не подходят. Понятно, что если остаток равен 1 или 4, то числа имеют вид p=5k+1 или 5k+4, где k будет натуральным числом. Но это самоочевидно, и нет нужды переливать из пустого в порожнее.

(22 Май '17 0:11) falcao

@SergeY: если бы было число 17, то мы точно так же использовали бы свойства символов Лежандра. Там (17/p)=(p/17), а квадраты по модулю 17 нам известны. Здесь основную роль играет закон взаимности, так как это сложная и нетривиальная теорема. А всё остальное получается уже автоматически.

(22 Май '17 0:27) falcao

@falcao:теперь все понял. Спасибо! Ведь важно разобраться в задании и его решении =)

(22 Май '17 0:32) SergeY

@SergeY: совершенно согласен с общим принципом. Поэтому я на содержательный вопрос (про 17 вместо 5) охотно ответил. Но вот записи 5k+1 и 5k+4 уже были! Там, правда, не было сказано, что k -- целые положительные. Ясно, что в "академическом" тексте такое пишут, а в комментариях для простоты опускают. Но тогда, если блюсти "форму", надо писать, что p простое, и не упускать случай p=5. А ещё лучше не обсуждать то, что и так понятно и однозначно.

(22 Май '17 0:37) falcao
показано 5 из 13 показать еще 8
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×879

задан
21 Май '17 14:02

показан
474 раза

обновлен
22 Май '17 0:37

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru