как доказать, что число 2^x может быть поделено нацело только числом вида 2^y, где y<=x? И никаким другим числом не может, (в качестве разминки для мозгов) Опции

[Krys]

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

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

[blackfin]

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

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

Каждое натуральное число n > 1 можно представить в виде n = p₁ *...* p_k, где p₁ ,.., p_k — простые числа,
причём такое представление единственно с точностью до порядка следования сомножителей.

[ViKo]

Поскольку 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 множителя получаем кучу вариантов.

Сообщение отредактировал Эдди - Jan 20 2016, 08:49

[AlexeyW]

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

[iiv]

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

[Krys]

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

[alexvu]

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

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

[iiv]

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

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

[RCray]

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

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

[ViKo]

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

[RCray]

тогда "ой"

[jks]

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

Не силен я в математике но как-то так думаю.
Число 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.
другие делители можно найти после факторизации (или в интернете).

[iiv]

2. "1010...10101, в котором 2016 нулей" = 0x5555..555 (в котором 1008 пятерок), то есть делится на 5 = 0x1111..111 (в котором 1008 единиц)

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

[OlegNS]

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