Делимость чисел

defender · Post by **defender** » 26 Oct 2007 20:10

Как же доказать делимость 2^41+1 на 83 ?

PavelM · Post by **PavelM** » 26 Oct 2007 23:14

не особо долго думая

2^41+1 = 0 (mod 83)
2^41 = -1 (mod 83) = 82 (mod 83)
2^40 = (2^10)^4 = 41(mod 83) = -42 (mod 83)
2^10 = 1024 = 28 (mod 83)
28^4 (mod 83) = 7^4 * 2^8 (mod 83) = -42 (mod 83)
7^3 * 2^7 = -3 (mod 83) = 80 (mod 83)
7^3 * 2^3 = 5 (mod 83) = -78 (mod 83)
7^3 * 2^2 = -39 (mod 83) = 44 (mod 83)
7^3 = 11 (mod 83)

343/83 = 11 (mod 83)

vm__ · Post by **vm__** » 27 Oct 2007 04:40

PavelM wrote:не особо долго думая
2^41+1 = 0 (mod 83) ...

Поток сознания потрясающий! :great:

А для бестолковых - может словами какими-никакими разбавите-поясните? Типа на уровне 3-4 класса, если можно, начальной школы? Please....

PavelM · Post by **PavelM** » 27 Oct 2007 05:15

vm__ wrote:
PavelM wrote:не особо долго думая
2^41+1 = 0 (mod 83) ...
Поток сознания потрясающий!
А для бестолковых - может словами какими-никакими разбавите-поясните? Типа на уровне 3-4 класса, если можно, начальной школы? Please....

1. Делимость на X означает что остаток деления по модулю X равен нулю

Терминология:

запись 1 (мод 5) означает остаток 1 деления по модулю 5.
запись 1 (мод 5) тождественна -4 (мод 5)

Тут нужны знаки тождества вместо равенств, но у меня таких на клавитуре нет. :wink:

2. Вспоминаем некоторые базовые правила для a = b (mod c)

a = b (mod c) = b-с (mod c)

a^n = b^n (mod c)
a*k = b*k (mod c)
a/k = b/k (mod c)
a+x = b+x (mod c)
a-x = b-x (mod c)

Далее используя эти правила пытаемся доказать справедливость равенства

2^41+1 = 0 (mod 83)

получаем

7^3 = 343 = 11 (mod 83)

проверяем поделив 343 на 83 получаем остаток 11, значит исходное утверждение верно.

defender · Post by **defender** » 27 Oct 2007 07:13

Огромное спасибо!
Но ведь моды не проходят в школе в 8 классе!
Конечно можно все это расписать без этих спецформул, типа все решили интуитивно и по ходу дела доказвая кучу теорем. Не думаю, что школьнику, не знакомому с теорией чисел удастся получить имено такое решение.
1000 извинений, но в условии по запарке вместо - я напечатал +.
Должно быть "доказать делимость 2^41-1 на 83"
Прошу извинить за баг.

vm__ · Post by **vm__** » 27 Oct 2007 08:37

PavelM wrote: Вспоминаем некоторые базовые правила для a = b (mod c)

Не все могут вспомнить то, чего никогда не видели...

Спасибо, забавно...

PavelM · Post by **PavelM** » 27 Oct 2007 15:56

defender wrote:"доказать делимость 2^41-1 на 83"

а вот это число не делится без остатка
доказательство аналогично

PavelM · Post by **PavelM** » 27 Oct 2007 16:18

defender wrote:Огромное спасибо!
Но ведь моды не проходят в школе в 8 классе!

А в условии не было 8 класса

Деление по модулю в школе проходят.
Остальное - для желающих на факультативах и мат. кружках.
Так что в 8-9 классах некоторые это уже проделывали.

пример
http://mmmf.math.msu.su/archive/20042005/z8/5.html