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

и задачки для интервью.
Mono
Новичок
Posts: 73
Joined: 27 Feb 2005 14:01

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

Post by Mono »

Привет!
Надо найти остаток от деления
2^2006:7
Спасибо!
User avatar
katit
Уже с Приветом
Posts: 23960
Joined: 05 Jul 2003 22:34
Location: Брест -> St. Louis, MO

Post by katit »

1, 2 или 4 :)

будет 4
Лучше водки — хуже нет! ©
Mono
Новичок
Posts: 73
Joined: 27 Feb 2005 14:01

Post by Mono »

katit wrote:1, 2 или 4 :)

будет 4


А как это решить?
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

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
Новичок
Posts: 73
Joined: 27 Feb 2005 14:01

Post by Mono »

Спасибо 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
Новичок
Posts: 73
Joined: 27 Feb 2005 14:01

Post by Mono »

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, тогда действительно последняя цифра играет роль. А здесь совпадение или научный факт?
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Совпадение.
Для 2008 должно быть 2, а по "школьному" получается 6.
User avatar
Helmsman
Уже с Приветом
Posts: 6625
Joined: 15 May 2003 00:04
Location: LA

Post by Helmsman »

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


индукция вам в помощь
Mono
Новичок
Posts: 73
Joined: 27 Feb 2005 14:01

Post by Mono »

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

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

Или опять что-то не так?
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Всё правильно. :appl:
Mono
Новичок
Posts: 73
Joined: 27 Feb 2005 14:01

Post by Mono »

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

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

Вроде -1, 1, 2.
А в ответе 2.
Чем единицы плохи? :pain1:
User avatar
Иоп
Уже с Приветом
Posts: 8832
Joined: 18 Feb 2005 08:00
Location: Yekaterinburg --> Toronto

Post by Иоп »

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

Вот лучше загадка:
как решить x^x = a?
User avatar
KP580BE51
Уже с Приветом
Posts: 15007
Joined: 14 Jun 2005 11:50
Location: Ukraine

Post by KP580BE51 »

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

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

Муторно квадратный корень делается, однако. :(
User avatar
Иоп
Уже с Приветом
Posts: 8832
Joined: 18 Feb 2005 08:00
Location: Yekaterinburg --> Toronto

Post by Иоп »

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

Return to “Головоломки”