Thursday, March 5, 2015

Euler's Totient Function of Odd Composite

Let 'N'  be any odd composite. 

Find semi-prime Sp = uv such that 

(2u+1)(2v+1) <= N <= 3(2Sp+1). or N <= (2u+1)(2v+1) < 3(2Sp+1)

 [[ For example let N = 65 then required semi-prime is 14 = 2*7 such that 65 < (2*2 + 1)(2*7 +1)  < 3*(2*14 + 1) i.e., 65 < 5*15 < 3*29 i.e., 65 < 75 < 87]]
{{ Note: Finding Semi-prime Sp will be optimized through Trial & Error }}

Let Lsp be any semiprime nearer and lesser than Sp compared to other.

Then Euler's Totient function Phi(N) = 4*(Sp - k) where 0 <=  k <= (Sp - Lsp).

[[ For example for 65 = 5*13 Phi(65) = 4*12 = 48 =  4*(14-2) Look above example Sp = 14, Lsp = 9, Sp - Lsp = 14-9 = 5; here we saw that 0 < k < 5]]