RSA and phi function

Question

I am in process of writing essay about cryptography and math behind it. I know that φ(n)=(p-1)(q-1), but would it be true if p and q are not primes but just ordinary factors of n?

Answer 1

Decompose n into prime factors- (a)^r,(b)^s,(c)^t... and use the result phi(p^x) = p^x -p^x-1.

Answer 2

Suppose $n=p_1^{k_1}p_2^{k_2}...p_m^{k_m}$, where $p_i,i=1,...,k$ are distinct primes.

Then $\phi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdot...\cdot (1-\frac{1}{p_m})$.

Answer 3

In general,

If the integer $n\ge1$ has the prime factorization $n=p^{k_1}_1p^{k_2}_2 \cdot\cdot\cdot p^{k_r}_r$, then $$\phi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right) \cdot\cdot\cdot \left(1-\frac{1}{p_r}\right)$$.

There is a paper coming out on Rose-Hulman Institute of Technology Math Journal on Dec 15 about this function if you are interested. The latest issue is here,

http://www.rose-hulman.edu/mathjournal/v14n1.php.

You will want to wait until the 15th for the next one. The paper was written by undergrads so it should very accessible.

Update: This is the link to the above mentioned paper: http://www.rose-hulman.edu/mathjournal/archives/2013/vol14-n2/paper6/v14n2-6pd.pdf