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

Mono · Post by **Mono** » 02 May 2006 17:55

Привет!
Надо найти остаток от деления
2^2006:7
Спасибо!

katit · Post by **katit** » 02 May 2006 18:04

1, 2 или 4

будет 4

Mono · Post by **Mono** » 02 May 2006 19:14

katit wrote:1, 2 или 4

будет 4

А как это решить?

venco · Post by **venco** » 02 May 2006 19:42

2^(3k) mod 7 = 1
2^(3k+1) mod 7 = 2
2^(3k+2) mod 7 = 4

2^2006 mod 7 = 2^(2006 mod 3) mod 7 = 2^((2+0+0+6) mod 3) mod 7 = 2^2 mod 7 = 4

Mono · Post by **Mono** » 03 May 2006 03:26

Спасибо venco!

А как вы определили например, 2^(3k) mod 7 = 1

И почему 2^2006 mod 7 = 2^(2006 mod 3) mod 7 = 2^((2+0+0+6) mod 3) mod 7 :pain1:

Mono · Post by **Mono** » 03 May 2006 04:28

2^(3k) mod 7 = 1
2^(3k+1) mod 7 = 2
2^(3k+2) mod 7 = 4

Вроде понял. Наверное из-за 2^3=8==1(mod7)

Остальное еще не совсем понятно!

А вы можете объяснить вот это:

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

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, тогда действительно последняя цифра играет роль. А здесь совпадение или научный факт?

venco · Post by **venco** » 03 May 2006 04:39

Совпадение.
Для 2008 должно быть 2, а по "школьному" получается 6.

Helmsman · Post by **Helmsman** » 03 May 2006 10:01

Mono wrote:А как вы определили например, 2^(3k) mod 7 = 1

индукция вам в помощь

Mono · Post by **Mono** » 08 May 2006 09:58

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

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 позиция в списке)

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

venco · Post by **venco** » 08 May 2006 12:59

Всё правильно. :appl:

Mono · Post by **Mono** » 08 May 2006 19:41

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

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

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

Иоп · Post by **Иоп** » 09 May 2006 00:45

единицы подходят... черт их знает, почему их нет в ответе.

Вот лучше загадка:
как решить x^x = a?

KP580BE51 · Post by **KP580BE51** » 09 May 2006 01:00

Иоп wrote:единицы подходят... черт их знает, почему их нет в ответе.

Вот лучше загадка:
как решить x^x = a?

Муторно квадратный корень делается, однако.

Иоп · Post by **Иоп** » 09 May 2006 05:08

Про свое уравнение создал отдельную тему:
http://forum.privet.com/viewtopic.php?t=98969