Пусть $%x = \left(\frac{p-1}2\right)! $%, где p - нечетное простое.

Доказать, что
а) если $% p \equiv 1 \pmod4 $%, то $%x^2+1 \equiv 0 \pmod p$%
б) если $% p \equiv 3 \pmod4 $%, то $%x^2-1 \equiv 0 \pmod p$%

задан 30 Янв '17 15:59

изменен 30 Янв '17 16:05

knop's gravatar image


20.3k529

1

Обратите внимание, что доллар+процент - это один спецсимвол, открывающий и закрывающий math mode. То есть для закрытия нужно ставить не процент+доллар, а снова доллар+процент

(30 Янв '17 16:07) knop

Константин, спасибо. Я искал в каких тегах здесь ТеХ оформляется, но почему то не нашел.

По поводу самой задачи. Я не помню, чтобы встречал ее среди олимпиадных (школьных/студенческих) задач. И как-то по быстрому доказать не получилось. Возможно туплю.

(30 Янв '17 16:19) spades

@spades - ну, я уже ответил по существу... Задача-то довольно известная. Ее можно и без т.Вильсона решить, ну просто передоказав ее фактически.

(30 Янв '17 16:23) knop

Спасибо! Действительно тупил.

(30 Янв '17 16:43) spades
10|600 символов нужно символов осталось
3

Разберемся, как связаны $%x^2$% и $%(p-1)! \pmod p$%. Второй равен произведению $%x$% на все множители от $%(p+1)/2$% до $%(p-1)$%. Последний из этих множителей сравним с $%-1$%, предыдущий с $%-2$%, и т.д., $%(p+1)/2 \equiv -(p-1)/2$%. Таким образом, их произведение сравнимо с $%x$%, умноженным на некоторое количество минус единиц.

Это количество равно количеству чисел от $%(p+1)/2$% до $%(p-1)$%, то есть оно нечётно для $%p=4k+3$% и чётно для $%p=4k+1$%. Таким образом, для $%p=4k+1$% получаем $%x^2 \equiv (p-1)! \pmod p$%, а для $%p=4k+3$% получаем $%x^2 \equiv -(p-1)! \pmod p$%. Осталось воспользоваться теоремой Вильсона.

ссылка

отвечен 30 Янв '17 16:15

изменен 30 Янв '17 16:15

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×378
×175
×79

задан
30 Янв '17 15:59

показан
920 раз

обновлен
30 Янв '17 16:43

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

по почте:

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

по RSS:

Ответы

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

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