|
Пусть $%\sigma(n)$%-сумма положительных делителей числа $%n,d(n)$%-их количество, $%\phi(n)$%-количество натуральных чисел $%i\leq n$%, взаимно простых с $%n$%. Докажите, что тождество $%\sigma(n)+\phi(n)=n\cdot d(n).$% верно тогда и только тогда, когда $%n$% простое. задан 16 Июн '12 11:19 
dmg3 |
|
Выполним проверку для 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$%.
отвечен 19 Июн '12 12:21 
Anatoliy Извините, не дописал условие
(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
|
Что можно сказать по поводу решения этой задачи? Все-таки нужно проявлять внимательность.