Feb. 27th, 2015

knop: (qr)
Я пишу сейчас нечто по ТЧ. Там есть цикл задач про фи-функцию Эйлера, и в нем - такая вот задачка: докажите, что равенство phi(n)=n/2 равносильно тому, что n - степень двойки.

К ней я знаю два разных решения. Первое - на основе того, что phi(n)=n * П (1-1/p),
где произведение берется по всем простым делителям n. Второе - на основе тождества Гаусса
n = SUM phi(d), где сумма берется по всем делителям n. (Это тождество нужно записать дважды - для n и для n/2, потом учесть условие phi(n)=n/2 и сравнить результаты.)

Какое решение оставить? Только первое? Только второе? Привести оба?
А может, вы знаете еще какое-то решение этой задачи?

April 2017

S M T W T F S
      1
234567 8
9101112131415
16171819202122
23242526272829
30      

Style Credit

Expand Cut Tags

No cut tags
Page generated Jul. 27th, 2017 06:37 pm
Powered by Dreamwidth Studios