Головоломки по теории чисел

vitamin8808

Найти наименьшее n>17 для которого [math]$18^n-1$[/math] делится на n^2.
Ответ: [math]$n=\frac{18^{17}-1}{17}$[/math].
2. Найти наименьшее n>12 для которого [math]$11^n-2$[/math] простое.
Ответ: http://www.research.att.com/~njas/sequences/A128472
11^22420 - 2 простое, n=22420, was found by Rick L. Shepherd 09/29/2007.
В первой задачке [math]$n=\frac{18^{17}-1}{17}$[/math] подходит, но я не могу доказать, что оно наименьшее.

vitamin8808

Про первую задачку: [math]$n=\frac{18^{17}-1}{17}$[/math] подходит, но
непонятно, с чего бы оно было наименьшим(число огромное).
Почему оно подходит:
Лемма. Если A mod k = 1, то [math]$A^k-1$[/math] делится на (A-1)k.
Доказательство. Просто разложим на множители:
[math]$A^k-1=(A-1A^{k-1}+A^{k-2}+\cdots+A^2+A+1)$[/math],
во второй скобке k слагаемых. Каждая степень А имеет остаток 1 от деления на k, и во второй скобке k слагаемых, значит она делится на k.
QED
Обозначим [math]$A=18^{17}$[/math].
По лемме [math]$A-1=17^2k$[/math] для целого k(так как 18^17-1 делится на 17^2).
Значит A mod k = 1 и [math]$m=\frac{A^k-1}{(A-1)k}$[/math] целое.
Возьмём n=17k. Тогда
[math]$18^n-1=A^k-1=(A-1)k m=17^2 k^2 m = n^2 m$[/math],
так как [math]$(A-1)k=17^2k^2$[/math].
Тем же макаром можно показать, что вместо k подходит любой его делитель.
Кто прочитал, тот молодец :D

margo11

каково происхождение задач?

vitamin8808

Да просто на форуме одном народ выкладывает задачки, предлагавшиеся на интервью на работу.
Но там никто эту не решил.

margo11

а может это задачки по программированию а не по математике?

blackout

В первой задаче подходит 17 :)
По малой теореме Ферма 18^17-1 делится на 17, логично проверить, делится ли на 17^2. Как проверять без калькулятора пока не знаю.

vitamin8808

а может это задачки по программированию а не по математике?
Вряд ли.

vitamin8808

В первой задаче подходит 17 :)
По малой теореме Ферма 18^17-1 делится на 17, логично проверить, делится ли на 17^2. Как проверять без калькулятора пока не знаю.
Условие прочитай ;)

blackout

Ну и также, по малой теореме Ферма, не подходят 5 7 11 13. А те, что делятся на 2 или 3 тоже не подходят, так как 18 на них делится.
Значит 17 самое маленькое подходящее, тем больше смысла его проверить.

mboroday

n больше 17 должно быть по условию задачи...

philvoznes

Значит 17 самое маленькое подходящее
Найти наименьшее n>17

vitamin8808

А те, что делятся на 2 или 3 тоже не подходят, так как 18 на них делится.
Это верно. n должно быть нечётное и не делящееся на 3.

blackout

Спасибо, кэп номер 2.
Пусть p - наименьший простой делить n. n = k*(p^m). Очевидно, НОД(18, p) = 1
18^n == 1 (mod p)
18^k == 1
Значит есть некоторое b такое, что 18^b == 1 и p-1 делится на b и k делится на b. Так. как p - наименьший делитель, то b = 1. Значит p = 17.
Итого, n обязательно делится на 17.

vitamin8808

Пусть p - наименьший простой делитель n. n = k*(p^m). Очевидно, НОД(18, p) = 1
18^n == 1 (mod p)
18^k == 1
18^k == 1 по какому модулю и почему 1?
Значит есть некоторое b такое, что
1) 18^b == 1
2) p-1 делится на b
3) k делится на b.
В (1) какой модуль? И почему такое b существует?

blackout

Все сравнения по модулю p.
Для любого простого p и a таких, что (p, a) = 1 верно, что:
1) Существует минимальная степень, в которой a сравнимо с 1.
2) Все другие такие степени на нее делятся. В самом деле, если одна такая степень не делится на минимальную, то их остаток от деления меньше минимальной и одновременно обладает нужным свойством.

vitamin8808

Все сравнения по модулю p.
Для любого простого p и a таких, что (p, a) = 1 верно, что:
1) Существует минимальная степень, в которой a сравнимо с 1.
2) Все другие такие степени на нее делятся. В самом деле, если одна такая степень не делится на минимальную, то их остаток от деления меньше минимальной и одновременно обладает нужным свойством.
Ну (1) верно, так как [math]$a^{p-1} = 1 \, mod\, p$[/math], и существует минимальная степень.
(2) вроде тоже верно.
Но как из 18^n == 1 (mod p)
следует
18^k == 1 (mod p) ?

makaka

Просто интересно, при устройстве куда спрашивали эти задачи?

vitamin8808

В банк какой-то на Wall Street, на аналитику/трейдером. Это не меня спрашивали :D

blackout

Но как из 18^n == 1 (mod p)
следует18^k == 1 (mod p) ?
Малая теорема Ферма.
a^(k*p^m) == (a^p)^(k*p^(m-1 == a^(k*p^(m-1 == ... == a^k

vitamin8808

O! Вроде всё верно. Значит, действительно, если n решение, то n делится на 17 и это наименьший делитель.

vitamin8808

Про первую задачку: [math]$n=\frac{18^{17}-1}{17}$[/math] подходит, но
непонятно, с чего бы оно было наименьшим(число огромное).
Мне тут сказали, что [math]$\frac{n}{17}$[/math] простое (на компьютере проверили).
Кстати, http://gmplib.org/cgi-bin/gmp_calc.pl?expr=%2818%5E17-1%29%2...
[math]$\frac{n}{17}=\frac{18^{17}-1}{17^2}=7563707819165039903$[/math]

vitamin8808

PS google: http://community.livejournal.com/ru_math/477967.html
Тупо загуглил это простое число 7563707819165039903.

lenmas

То-есть получается, что задача чисто программистская. ;)

vitamin8808

То-есть получается, что задача чисто программистская. ;)
Нет, просто они при приёме на работу чуваков мучают по полной программе.
Посмотреть как товарищ в стрессовой ситуации себя ведёт, как у него мозги соображают, и т.д.

margo11

так а что со второй задачей-то?

blackout

Так почему это число умножить на 17 будет минимальным решением? В решении по ссылке смущает эта строка:
Поэтому для следующего по величине простого делителя p2 числа n мы с необходимостью имеем ordp2(18)=17

vitamin8808

Раз [math]$ord_{p_2} 18=17$[/math], значит 18^17-1 делится на p_2.
А 18^17-1 делится только на 17 и на тот гроб 7563707819165039903.
Значит p_2=7563707819165039903(так как n=17^k не подходит).

blackout

Вопрос как раз в том, почему ord_p2(18)=17 ?

vitamin8808

Вопрос как раз в том, почему ord_p2(18)=17 ?
Вроде бы точно так же, как в твоём посте "кэп номер 2" доказывается, что ord_p1(18)=1.

blackout

Да, верно. Так же можно доказать.
Оставить комментарий
Имя или ник:
Комментарий: