простая задача

[santadambri]

http://valiev.blogspot.com/2009/07/blog-post.html

Comments

[allafterall]

Ну раз простая, значит ответ N = 2. По крайней мере я уверен, что совсем непросто доказать простоту чисел вида 1010..01, куда проще найти у них какой-нибудь делитель(я лично поставил бы на 7)
Вот такой вот reverse engineering=)

[santadambri]

то, что 101 - простое, сразу видно. Для остальных надо подумать :)

[allafterall]

то есть ты не знаешь решения?

[rasschepkin]

одного и того же делителя у них всех быть не может:
an + 1 = 100 * an + 1
пусть k ≠ 1 - общий делитель, получим:
0 ≡ 1 (mod k)

теперь, пусть n составное и k - его делитель (отличный от единицы и n), тога n = k * m,
an = ak(m-1) * 102k + ak
по индукции элементарно доказывается что an делится на ak
то есть n у нас как минимум простым должно быть, ну и конечно при n = 3, an делится на 3

задачу это конечно хер решает, но однозначно говорит, что смотришь ты пока не в ту сторону )

[tanyoushka]

А я жнааааю)))

Доказательство для четных n не равных 2 просто (можно явно предъявить делитель).
Доказательство для нечетных - требует большей изобретательности, но уловив общий смысл вида делителя для каждого такого n, тоже труда особого не доставляет :-)

P.S. меня прямо распирает все написать, но не буду этого делать, чтобы не испортить настоение _думающим_ :-)

[santadambri]

я сначала решил, и только потом уловил общий вид делителя. ;)

[tanyoushka]

Ну, тут уж, как кому повезет :-)

[rasschepkin]

ст, это ты скрыл мой ответ или я что-то не то сделал? и еще более интересный вопрос. почему я не вижу твой ответ, а на почту он мне ришел? )

[santadambri]

я скрыл, и коммент тоже скрыл :)