10
$\begingroup$

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?

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

2 Answers 2

15
$\begingroup$

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)$.

$\endgroup$
1
  • 5
    $\begingroup$ 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$ $\endgroup$ Commented Sep 22, 2011 at 0:50
8
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .