Пусть $%\sigma(n)$%-сумма положительных делителей числа $%n,d(n)$%-их количество, $%\phi(n)$%-количество натуральных чисел $%i\leq n$%, взаимно простых с $%n$%. Докажите, что тождество $%\sigma(n)+\phi(n)=n\cdot d(n).$% верно тогда и только тогда, когда $%n$% простое.

задан 16 Июн '12 11:19

изменен 26 Июн '12 9:39

Что можно сказать по поводу решения этой задачи? Все-таки нужно проявлять внимательность.

(2 Окт '12 20:08) Anatoliy
10|600 символов нужно символов осталось
0

Выполним проверку для n=4: $%\sigma \left( n \right) =1+2+4=7,\phi \left( n \right) =2\left( 1,3 \right) ,d\left( n \right) =3\left( 1,2,4 \right) $%. Должно выполняться равенство $%7+2=4\cdot 3$%, но это не так.

Формулы:

$$\sigma \left( n \right) =\frac { p_1^{ \alpha_1 +1 } -1 }{ p_1 - 1 } \cdot \frac { p_2^{ \alpha_2 + 1 } - 1 }{ p_2 - 1 } \cdot ...\cdot \frac { p_k^{ \alpha_k + 1 } - 1 }{ p_k - 1 }$$

$$\phi \left( n \right) =n\cdot \left( 1 - \frac { 1 }{ p_1 } \right) \cdot \left( 1 -\frac { 1 }{ p_2 } \right) \cdot ...\cdot \left( 1-\frac { 1 }{ p_k } \right)$$

$$d\left( n \right) =\left( \alpha_1 + 1 \right) \cdot \left( \alpha_2 + 1 \right) \cdot ...\cdot \left( \alpha_k + 1 \right) $$

где $%n=p_1^{ \alpha_1 }\cdot p_2^{ \alpha_2 }\cdot ...\cdot p_k^{ \alpha_k }$% - разложение натурального числа $%n$%на простые множители. Если сравнить левую и правую части равенства, то имеем разную зависимость от $%\alpha_i$%.

alt text

alt text

ссылка

отвечен 19 Июн '12 12:21

изменен 30 Июн '12 19:29

Извините, не дописал условие

(19 Июн '12 12:38) dmg3

Тогда и ТОЛЬКО тогда, в этом то и заключается сложность задачи.

(26 Июн '12 9:38) dmg3

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

(26 Июн '12 18:33) Anatoliy

Ну глуповат я, мое решение не очевидное.

(26 Июн '12 19:24) dmg3

Анализируя эти формулы ( в первой Вашей версии задачи), я пришел к выводу, что нужно искать контрпример и нашел (это не сложно). Если посмотреть на показатели простых чисел в разложении на простые множители, то в левой части равенства - это показатели степеней, а в правой части равенства - это просто их произведение (на единицу больше). Я не пытался в комментарии проявить некое верхоглядство. Думаю, что можно, учитывая сказанное, провести аккуратное исследование равенства и доказать утверждение задачи.

(26 Июн '12 19:53) Anatoliy

У вас две ошибки. Почему $%\phi(n)=..$%? При $%n=12$% у вас получается 4, а их всего 3:5,7,11. И почему $%(1+p_j+..+{p_j}^{\alpha_j})$% не может делиться на $%p_i$%?

(6 Окт '12 19:05) dmg3

1,5,7,11, по идее

(6 Окт '12 21:46) chameleon
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×551

задан
16 Июн '12 11:19

показан
1449 раз

обновлен
6 Окт '12 22:19

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru