Euler Function

Method 1:
phi(12) = ?
12 = 2^{2} x 3 ( where 2 and 3 are prime)

let p = 2, q = 3, so formula is phi(n) = n x (1 - 1/p) x (1 - 1/q)


so, phi(12) = 12 x (1 - 1/2) x (1 - 1/3)
= 12 x (1/2) x (2/3)
= 4
Method 2: Use this method if and only if we can factor the number into
prime that no repeatation. (but, i seem can find some way to fix it,
need further clarification with Dr lim, will update here once succeed)


if we can find ....phi(n) = phi(p) x phi(q) x phi(r) x ...... where
p , q , r are prime and no repeat,
example phi(26) = phi(2) x phi(13)
= (how many number that < 2 are prime with 2,
find 0<a<2, where gcd(a,2)= 1) x
(how many number that < 13 are prime with
13, find 0<a<13, where gcd(a,13)= 1)
= 1 x 12
= 12


******p/s: we need method 2 for RSA