Totient function and distinct primes.

[Yuqing]

It is true that phi(pq)=(p-1)(q-1) when p and q are distinct primes, but is it true that given phi(pq) = (p-1)(q-1) then p and q have to be distinct primes? It seems intuitive, but I'm having some difficulty proving it.

Also, if this was true, is it possible to generalize this into more than 2 primes? Given phi(m) = (p_1-1)(p_2-1)..(p_k-1) then m is a product of k distinct primes.

 

[disregardthat]

For your first question, if p = q, then phi(pq)=phi(p^2)=p^2-p =/= (p-1)(q-1).

For your second, what happens if some of them are equal? As you can see above p divides phi(pq). This will also happen generally if some prime occurs more than once.

 

[Yuqing]

Sorry, I should've been more clear.

For the question, I am assuming that we do not know the nature of p or q. As you have mentioned, if p and q are both primes, they have to be distinct, but if p and q are not necessarily primes (they could be primes, composite, coprime or non-coprime) then could phi(pq) = (p-1)(q-1).

So basically I am asking, given two numbers p and q, where we do not know if p or q is prime, coprime or any detail in general, can we prove that if phi(pq) = (p-1)(q-1) then p and q are distinct primes. To give a numerical example, say we want to prove that 2 and 3 are primes, can we use

phi(2*3) = (2-1)(3-1) = 2 to prove that 2 are 3 are in fact distinct primes.

The same idea with the generalized case, say we know that

phi(p_1 *p_2 * ... *p_k) = (p_1-1)(p_2-1)..(p_k-1)

can we then say that p_1, p_2, ... p_k are distinct primes?

 

[I like Serena]

So basically I am asking, given two numbers p and q, where we do not know if p or q is prime, coprime or any detail in general, can we prove that if phi(pq) = (p-1)(q-1) then p and q are distinct primes.

Suppose we have phi(m q)=(m-1)(q-1) and m=pr and with p,q,r distinct primes (so p,q,r > 1).
Then we would also have phi(m q)=phi(pr q)=(p-1)(r-1)q

In other words, we would have (pr-1)=(p-1)(r-1), implying p+r=2 which is a contradiction (since both are > 1).

Similarly if we have phi(m q)=(m-1)(q-1) with m=r² and q,r distinct primes.
Then we would have phi(m q)=phi(r² q)=(r-1)rq
In this case we would have (r²-1)=(r-1)r, implying r=1 which again is a contradiction.

In general each factorisation of m would yield a value for phi(m q) that is lower than (m-1)(q-1).
And more generally each factorisation of m and n would yield a value for phi(m n) that is lower than (m-1)(n-1).

So I'd say, yes, if we have phi(m n)=(m-1)(n-1) then m and n must be distinct primes.
Qed.

 

[Yuqing]

I agree that it does seem like the case, but from what I can see, that proof relies on the fact that q is prime (which is required to properly cancel q-1). I cannot see an immediately obvious way to prove the proposition for the case that both p and q are composite. Especially troubling (for me at least) is the case where p and q might be non-coprime.

 

[disregardthat]

phi(ab) <= phi(a)phi(b) <= (a-1)(b-1), and the last inequality is equality if and only if a and b are primes. This extends easily to an arbitrary number of factors. The second inequality is obvious, and the first inequality can be seen from a easily derived general formula for phi(n) given the prime factorization of n.

 

[Yuqing]

But the first inequality is not true.

phi(24) = 8 > phi(4)*phi(6) = 2*2 = 4

 

[disregardthat]

But the first inequality is not true.

phi(24) = 8 > phi(4)*phi(6) = 2*2 = 4

My mistake, the inequality is the wrong way.