[일반] Euler phi function 하한 관련된거 뭐 있을까요?

[익명(oneself2189)]

phi(n)이면 적어도 몇보단 크다든지 하는거요

- dc official App

[Delpcon(bare3888)]

n=p1^a1...pn^an라 하면 phi(n)=(p1^(a1-1))(p1-1)...(pn^(an-1))(pn-1)이므로 ((phi(n))^2)/n=(p1^(a1-2))(p1-1)^2...(pn^(an-2))(pn-1)^2 입니다. 그런데 ai들은 1 이상의 자연수이므로 (pk^(ak-2))(pk-1)^2>=(pk-1)^2/pk.

[Delpcon(bare3888)]

그런데 3이상의 소수 p에 대해 (p-1)^2/p는 1 이상이고, p가 2면 (p-1)^2/p=1/2이므로 (p1^(a1-2))(p1-1)^2...(pn^(an-2))(pn-1)^2>=1/2가 되어 (phi(n)^2)/n>=1/2, 즉 phi(n)>=sqrt(n/2) 라는 하한을 얻게됩니다.

[Delpcon(bare3888)]

이거 말고 더 빡센 하한을 원하시면
https://math.stackexchange.com/questions/301837/is-the-euler-phi-function-bounded-below?noredirect=1&lq=1

[익명(oneself2189)]

오 그렇군요 감사합니다! - dc App