Здравствуйте. Вопросик в качестве разминки для мозгов:
Как математически доказать, что число 2^x может быть поделено нацело только числом вида 2^y, где y<=x, и никаким другим числом не может (или наоборот может и ещё есть какие-то числа)?

Т.е. например число 2 в 12 степени это 4096 нацело делится двойкой в любой степени до 12 и ничем другим. Т.е. для меня важно доказать, что нет ничего другого, кроме 2^y

Это следует из Основной теоремы арифметики:

Поскольку 2^y = 2 * 2 * 2 ...
очевидно, что никаких других сомножителей, кроме степени двойки, у числа нет. И 2 уже ни на что не раскладывается.
Аналогичные свойства будет иметь x ^ y, если x - простое число.

Во-во, присоединяюсь к предыдущему оратору. Просто разложим: 2^a = 2^{m+n}, где a = m+n по определению. Таким образом, множителями 2^a яляются два числа: 2^m и 2^n, где m≤a и n≤a. ЧТД.

А вот для непростых чисел это уже не так. Непростое число x есть произведение N чисел: Пa_i
Т.е. x^y = (Пa_i)^y = Пa_i^y = Пa_i^{m+n}
Т.о. здесь уже даже при разложении на 2 множителя получаем кучу вариантов.

Задача для разнообразия: перемножаем числа от 1 до 99, сколько нулей будет в конце результата?
А можно еще попробовать в общем виде - от 1 до N.

ну раз ту все задачки выкладывают, можно я на злобу дня (года) выложу: как доказать, что число 1010...10101, в котором 2016 нулей не является простым? Как подсказку, озвучу один из делителей 80681

Спасибо откликнувшимся. Мне это не просто для развлекухи надо было, а для математического обоснования при составлении одного документика

А должно быть красивое решение или Вы знаете только метод подбора на компе?

я знаю три решения:
1. красивое,
2. требующее знания очень специфических методов (считаю его не красивым, более того, на раз даже его не напишу, надо в книжки заглядывать),
3. ну и перебор, конечно.
возможно есть еще какие-то другие решения

1. B соответствии с формулой геометрической прогрессии само число "1010...10101, в котором 2016 нулей" = (2^4032-1)/3. Но это нам ничего не дает.
2. "1010...10101, в котором 2016 нулей" = 0x5555..555 (в котором 1008 пятерок), то есть делится на 5 = 0x1111..111 (в котором 1008 единиц)

Постойте, разве число 1010... - записано в двоичной системе?

тогда "ой"

Не силен я в математике но как-то так думаю.
Число 101010....10101<4033> содержит 2016*2 + 1 дес. цифр.
Если умножить 101010....10101<4033> на 11 , то получим число с одними единицами (репьюнит Rn(N=4034)).
101010....10101<4033> * 11 = 11111...11<4034> = RN(4034)
Так как N - четно его можно представить в виде произведения:
RN(4034) = 111...111<2017> * 100...001<2018>
число 100...001<2018> делится на 11 т.к. содержит 2 единицы и четное число групп из двух цифр.
100...001<2018> mod(11) == 0, 10000...0001<2018> : 11 = 909090...9091<2016>
т.о. 101010....10101<4033> = 111...11<2017>*909090....91<2016>.
т.е. 101010....10101<4033> содержит по крайней мере два делителя 111...111<2017> и 9090...9091<2016>.
один из делителей 9090...9091<2016> равен 80681.
другие делители можно найти после факторизации (или в интернете).

не 0x5555..555 а 0x15555..555 хотя задача изначально в десятичной системе сформулирована, в двоичной системе не все так просто, хотя число тоже не простое, для тех, кому хочется и в двоичной системе помучиться, дам подсказку на делитель: 2936753

Число "1010...10101, в котором 2016 нулей" = 10^0 + 10^2 + 10^4 + ... + 10^2016, что как сказал RCray действительно является геометрической прогрессией и ее сумма равна 10^0*(100^2017 - 1)/(100 -1). Как видно число делится на на 99, а также на 3, 33, 11, 9.

Данное число А= 1+100+10000+… — сумма 2017 членов геометрической прогрессии с первым членом 1 и знаменателем 100. Тогда по формуле суммы
А=(100^2017-1)/(100-1) => 99А = 10^4034 — 1 = (10^2017+1)(10^2017-1), как разность квадратов.
Каждый из множителей правой части равенства больше 99, а значит меньше А.
Следовательно, с каждым из чисел (10^2017+1) и (10^2017-1) наше число А имеет общий делитель, отличный от 1 и А.
В общем случае аналогично можно доказать, что любое число вида 101..01, кроме 101, является составным.

Правильно?

Число А делится на число В нацело только в том случае если В является произведением простых множителей числа А.

Разложение числа А=х^2 на простые множители тривиально: x множителей, каждый из которых равен 2.
Поэтому любой делитель числа А будет произведением этих простых сомножителей: В = 2*2.....2*2 = 2^y, где y: 1<=у<=x;

И ничего не надо доказывать.