помогите решить задачку

ipipauer707

Товарищи! Помогите решить следующую задачу:
1. Доказать что число делителей числа n не превосходит числа делителей числа 2^n - 1 (2 в степени n и все это минус 1)

kica

Может, я что-то не понимаю, но либо условие не такое, либо это доказывается очень просто.
Число делителей числа n не превосходит самого n. Осталось показать, что n \leq 2^n - 1, что вполне очевидно (можно, например, доказать индукцией ).

afony

По-моему, все просто: если k - делитель n, то 2^k-1 - делитель 2^n-1, т.о. число делителей n не больше числа делителей 2^n-1.

zuzaka

имхо ты чего-то не понимаешь

zuzaka

стильно

afony

Я думаю, что это решение и имелось в виду составителями.

plugotarenko

Пусть d - делитель числа n.
Вспоминаем формулу (a^n-1)=(a-1a^{n-1}+...+a+1)
Применяем.
2^n-1=2^{d n/d}-1=(2^d-1...)
таким образом 2^d-1 есть делитель числа 2^n-1.
Ч т д.

ipipauer707

все всем спасибо
Оставить комментарий
Имя или ник:
Комментарий: