Докажите, что при любом $%k$% существует ровно 4 решения сравнения $%x^2 ≡ x (\mod 10^k)$%.

задан 14 Янв '15 14:24

изменен 14 Янв '15 15:08

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


9917

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

Рассмотрим два сравнения $%x^2\equiv x\pmod{2^k}$% и $%x^2\equiv x\pmod{5^k}$%. Для того, чтобы $%x$% удовлетворяло сравнению из условию задачи, необходимо и достаточно, чтобы оно удовлетворяло обоим эти сравнениям. Это следует из того, что делимость числа $%x^2-x$% на $%10^k$% в точности означает его делимость как на $%2^k$%, так и на $%5^k$%.

Если $%x(x-1)$% делится на $%2^k$%, то это может быть ровно в двух случаях: $%x$% делится на $%2^k$%, или $%x-1$% делится на $%2^k$%. Поскольку числа $%x-1$% и $%x$% последовательные, оба они одновременно делиться на $%2$% не могут. Значит, на степень двойки делится какое-то одно из них. Аналогично для степени числа $%5$%.

Таким образом, у нас имеют место условия: $%x\equiv r_1\pmod{2^k}$% и $%x\equiv r_2\pmod{5^k}$%, где $%r_1,r_2\in\{0;1\}$%. Для каждой фиксированной пары значений остатков $%r_1,r_2$% существует ровно одно решение системы двух сравнений по модулю $%2^k\cdot5^k$% в силу китайской теоремы об остатках (она применима в силу взаимной простоты сомножителей). Поэтому всего решений будет $%2\cdot2=4$%.

ссылка

отвечен 14 Янв '15 17:20

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

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

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

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

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

отмечен:

×591

задан
14 Янв '15 14:24

показан
348 раз

обновлен
14 Янв '15 21:49

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

по почте:

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

по RSS:

Ответы

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

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