Как найти остаток без калькулятора:-)

[Dad]

Надо найти остаток от деления 2^2006:7. Как можно это решить?

[PSP]

Надо найти остаток от деления 2^2006:7. Как можно это решить?

2^2006 = 4*(2^3)^668 = 4*8^668.
Поскольку 8 при делении на 7 даёт остаток 1, то 4*8^668 будет иметь при делении на 7 тот же остаток, что и 4*1^668, т. е. 4.

[Dad]

Надо найти остаток от деления 2^2006:7. Как можно это решить?

2^2006 = 4*(2^3)^668 = 4*8^668.
Поскольку 8 при делении на 7 даёт остаток 1, то 4*8^668 будет иметь при делении на 7 тот же остаток, что и 4*1^668, т. е. 4.

Спасибо PSP!
Все понял! А где можно почерпнуть информацию о таких задачках?

[Dad]

В школе почему-то решают ее с помощью нахождения последней цифры.

2^1=...2
2^2=...4
2^3=...8
2^4=...6

(далее все повторяется)

Берут от этих последних цифр остатки от деления на 7
2, 4, 1, 6.

2006 делят на 4 (период повторений) остаток=2, значит остаток от деления будет 4, так как на 2-м месте в списке остатков идет 4!

Я бы согласился, если бы делили на 5 а не на 7, тогда действительно последняя цифра играет роль. А здесь совпадение или научный факт?

[PSP]

Если учитель в школе именно так показывает решение этой задачи, то учитель профессионально безграмотный.
По такой "логике":
у числа 2^4, т. е. 16, остаток от деления на 7 равен 6,
у чиcла 2^5, т. е. 32, остаток равен 2.
Это же полнейшая глупость.

Вот примеры чисел, у которых последние цифры одинаковы, а остатки от деления на 7 различны: 11, 21, 31, 41, 51, 61, 71 (остатки соответственно 4, 0, 3, 6, 2, 5, 1).

Последняя цифра числа - это остаток от его деления на 10. Поэтому, зная только последнюю цифру, однозначно можно установить остаток при делении на 1, 2, 5 и 10 (натуральные делители числа 10).

[PSP]

А где можно почерпнуть информацию о таких задачках?

Если под "такими задачками" подразумеваются исключительно задачи на определение последней цифры числа N^K, то не знаю книжку, в которой специально расмматривались бы только такие задачи. Впрочем, почитать можно раздел "Сравнения по модулю" в книжках по теории чисел.

Что касается, вообще целых чисел, то могу порекомендовать, например, вполне доступные для школьников книги:
И. М. Виноградов "Основы теории чисел",
Е. П. Ожигова "Что такое теория чисел",
Г. И. Курбатова "Начала теории чисел",
В. Серпинский "250 задач по элементарной теории чисел",
В. Серпинский "Что мы знаем и чего не знаем о простых числах",
В. С. Малаховский "Эти загадочные простые числа".

А также книжки из серии "Популярные лекции по математике":
выпуск 8, А. О. Гельфонд "Решение уравнений в целых числах",
выпуск 39, Н. Н. Воробьёв "Признаки делимости",
выпуск 40, С. В. Фомин "Системы счисления",
выпуск 47, Л. А. Калужнин "Основная теорема арифметики".

Неоднократн печатались материалы по этой теме в журнале "Квант".

[Dad]

Спасибо Psp!

Отличный список!
Скачал три книги и нашел много интересного.
Кстати, в методе решения задачи есть ошибка, которую мы нашли с вами, но она не учителя а ученика оказывается!

Со временем напишу, что к чему! А пока я побежал по делам!

[Dad]

А вот так если поступить, то получается вроде

2^1=2=2(mod7)
2*2=4=4(mod7)
4*2=8=1(mod7)
далее повторяется все. Здесь остаток умножаем на 2.
Потом ищем остаток от деления 2006 на 3 = 2. то есть 4 (он на 2 позиции в списке)

Например, при 3^2006 надо делать так

3^1=3=3(mod7)
3*3=9=2(mod7)
2*3=6=6(mod7)
6*3=18=4(mod7)
4*3=12=5(mod7)
5*3=15=1(mod7)
далее опять повторяется.

ищем остаток от деления 2006 на 6 = 2 значит остаток будет 2 (2 позиция в списке)

Или опять что-то не так?

[PSP]

Если известны сравнения по модулю, то именно так.
Но при первоначальной постановке задачи не было ясно, каким математическим аппаратом Вы владеете, поэтому я и привёл решение "от печки".

[Dad]

Это я Ваши книжки почитал!

[Dad]

Теперь другой вопрос

Решить уравнение
|x|^x=x^2

Вроде -1, 1, 2.
А в ответе 2.
Чем единицы плохи?

[PSP]

Ничем. Плох ответ.

[Dad]

Спасибо!