# Given two primes $p$, $q$ and their product $pq$, find $\phi(pq)$ mod $p + q$

This is actually from a past year exam question for a computer security module, which I am doing to prepare for my upcoming test.

The question provides $$pq = 1669806207577$$ (for ease of reference, I will refer to it as $$n$$.

Define $$\phi(n) = n \left(1-\frac{1}{p_1}\right) \cdots \left(1-\frac{1}{p_k}\right)$$ as the the Euler Phi function, where $$p_1, \cdots, p_k$$ are the prime factors of $$n$$.

The question asks us to find $$\phi(pq) \text{ mod } (p+q)$$.

My approach is as follows,

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

I have tried to express $$2pq$$ as $$(p+q)^2 - p^2 - q^2$$ and substituting it to the above, such that,

$$\phi(pq) = pq - p - q + 1 = [(p+q)^2- p^2 - q^2]/2 - (p+q) + 1$$.

But now, I do not know how to proceed.

• You have $\varphi(pq)=pq+1-(p+q)\equiv pq+1\pmod {p+q}$ already. – lulu Sep 30 at 12:38

This is the basis of the RSA cryptosystem and there is no known parametric solution for this in terms of $$p$$ and $$q$$ which is less than $$pq+1$$ otherwise you will have cracked the RSA encryption system. So the best you can hope for is a brute force computer attack to factorize $$n$$ and find $$p$$ and $$q$$.