Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In an RSA paper I am reading it is assumed that where $p$ and $q$ are distinct prime numbers:

$\phi(pq)=\phi(p)\phi(q)=(p-1)(q-1)$

I would love to know why/how this is so? Is there some way to prove this?

share|improve this question
2  
The totient function is a multiplicative function. The wikipedia page has a proof. –  Unreasonable Sin Sep 21 '11 at 23:55
    
@UnreasonableSin Can you point out where it's proven? –  yydl Sep 21 '11 at 23:57
    
Right underneath "Computing Euler's function". But on second glance it's kind of a high level sketch of a proof. –  Unreasonable Sin Sep 21 '11 at 23:59
    
Huh. I hadn't realized we already had the specialized tag for the totient, so I thought to remove it. Oh well. –  J. M. Sep 22 '11 at 0:10
3  
You meant where $p$ and $q$ are distinct prime numbers. The formula is false if $p = q$. –  KCd Sep 22 '11 at 0:38

2 Answers 2

up vote 14 down vote accepted

The positive integers less than $pq$ that are not relatively prime to $pq$ are the positive multiples of $p$ less than $pq$ and the positive multiples of $q$ less than $pq$. The positive multiples of $p$ less than $pq$ are the numbers $kp$ for $k=1,2,\dots,q-1$, so there are $q-1$ of them. Similarly, the positive multiples of $q$ less than $pq$ are the numbers $kq$ for $k=1,2,\dots,p-1$, so there are $p-1$ of them. Thus, there are altogether $(p-1)+(q-1) = p+q-2$ positive integers less than $pq$ that are not relatively prime to $pq$.

There are altogether $pq-1$ positive integers less than $pq$, so there must be $$(pq-1)-(p+q-2) = pq-p-q+1 = (p-1)(q-1)$$ positive integers less than $pq$ that are relatively prime to $pq$. Thus, $\varphi(pq) = (p-1)(q-1) =$ $\varphi(p)\varphi(q)$.

share|improve this answer
4  
Crucial is that the two sets of multiples are disjoint, since $\rm\ p\:\mathbb Z\cap q\:\mathbb Z\ =\ p\:q\:\: \mathbb Z\ $ by $\rm\:(p,q)=1\:.\quad$ –  Bill Dubuque Sep 22 '11 at 0:50

What you are asking about is a special case of the multiplicativity of the totient function $\varphi$. In general, a function $f: \mathbb{Z}^+ \rightarrow \mathbb{R}$ is multiplicative if for all $n_1$ and $n_2$ with $\operatorname{gcd}(n_1,n_2) = 1$, $f(n_1 n_2) = f(n_1) f(n_2)$. (One might not have expected the definition to include the restriction that $n_1$ and $n_2$ have no common factor: functions which satisfy $f(n_1 n_2) = f(n_1) f(n_2)$ for all $n_1,n_2 \in \mathbb{Z}^+$ are called completely multiplicative. But this latter property is somehow too strong: many of the most common "arithmetical functions" studied in elementary / analytic number theory are multiplicative, but very few are completely multiplicative. For instance $\varphi$ is not completely multiplicative: for any prime number $p$, $\varphi(p^2) = p^2 -p = p(p-1) \neq (p-1)^2 = \varphi(p) \varphi(p)$.)

An elementary proof (well, I have never seen any other kind...) of the multiplicativity of $\varphi$ using the Chinese Remainder Theorem can be found in $\S 2.4$ of these notes. Knowing that $\varphi$ is multiplicative leads to an explicit formula for $\varphi(n)$ in terms of the prime factorization of $n$, since for any prime power $p^a$, the numbers between $1$ and $p^a$ which are relatively prime to $p^a$ are precisely the ones which are not multiples of $p$, so $\varphi(p^a) = p^a - p^{a-1} = p^{a-1}(p-1)$. For a second (still elementary!) proof of the multiplicativity of $\varphi$, see $\S 2.1$ of these notes. This latter proof uses the Möbius Inversion Formula.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.