Перейти к содержанию
    

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

Здравствуйте. Вопросик в качестве разминки для мозгов:

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

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

Каждое натуральное число n > 1 можно представить в виде n = p1 *...* pk, где p1 ,.., pk — простые числа,

причём такое представление единственно с точностью до порядка следования сомножителей.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Поскольку 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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

я знаю три решения:

1. красивое,

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

3. ну и перебор, конечно.

возможно есть еще какие-то другие решения :)

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

 

1. B соответствии с формулой геометрической прогрессии само число "1010...10101, в котором 2016 нулей" = (2^4032-1)/3. Но это нам ничего не дает.

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

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

ну раз ту все задачки выкладывают, можно я на злобу дня (года) выложу: как доказать, что число 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.

другие делители можно найти после факторизации (или в интернете).

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

не 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.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.

Гость
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
  • Создать...