Привет всем, помогите плиз, не могу решить сравнение. $$x^2 = 71 (\mod 5^2 \cdot 23)$$

задан 18 Дек '14 11:08

изменен 18 Дек '14 22:22

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
0

Отдельно решаем сравнение по модулю 23 и по модулю 25, а затем применяем китайскую теорему об остатках. По модулю 23 получается $%x^2\equiv2\pmod{23}$%. По простому модулю сравнение имеет не более двух решений, и здесь корни легко находятся подбором (к 2 начинаем прибавлять по 23, и сразу же получаем точный квадрат). Следовательно, $%x\equiv\pm5\pmod{23}$%.

Теперь решаем сравнение $%x^2\equiv-4\pmod{25}$%. Для начала выясняем, каков остаток $%x$% от деления на 5. Легко видеть, что $%x=5k\pm1$% для целого $%k$%. Подставляем $%x=5k+1$% и упрощаем. Получается $%25k^2+10k+5\equiv0\pmod{25}$%, то есть $%2k+1\equiv0\pmod5$%. Это линейное сравнение, из которого $%k=5t+2$% для целого $%t$%, и тогда $%x=5(5t+2)+1=25t+11$%, то есть $%x\equiv11\pmod{25}$%. Для случая $%x=5k-1$% получается противоположное значение, то есть $%x\equiv-11\pmod{25}$%.

Осталось решить четыре системы. Первая состоит из сравнений $%x\equiv5\pmod{23}$% и $%x\equiv11\pmod{25}$%. У других систем перед 5 и 11 берутся знаки "плюс" или "минус" всевозможными способами. Техника решения стандартная: из второго сравнения имеем $%x=25t+11$%, подставляем в первое, что даёт $%2t+6\equiv0\pmod{23}$%, то есть $%t=23s-3$% при целом $%s$%, откуда $%x=25(23s-3)+11=575s-64$%, в результате чего $%x\equiv511\pmod{575}$%.

Аналогично решается система с заменой 5 на -5, что даёт значение 386. Две другие системы можно не решать, так как они дадут противоположные по знаку числа, эквивалентные -511 и -386, то есть 64 и 189.

Окончательно имеем четыре решения: $%x\equiv64,189,386,511\pmod{5^2\cdot23}$%.

ссылка

отвечен 18 Дек '14 22:08

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

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

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

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

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

отмечен:

×43

задан
18 Дек '14 11:08

показан
313 раз

обновлен
18 Дек '14 22:21

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

по почте:

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

по RSS:

Ответы

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

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