I understand that $\text{gcd}(m,n)$ needs to be $1$ so we can apply the Euler's theorem, and if it's not $1$, the result is one of the prime factors of $n$. But Why the result it is always $p$ or $q$? Couldn't it be any other number?

  • $\begingroup$ It's pretty much a no brainer, because $p$ and $q$ are by definition the factors of $n$. $\endgroup$
    – DannyNiu
    Oct 31, 2022 at 12:47

2 Answers 2


Let $m$ and $n$ be products of two primes as in RSA: $n=pq$ and $ m = rs$.

if $m=n$ then we cannot learn about the primes,

if $m\not= n$ and $\gcd(m,n) >1$: since $m\not =n$ then $1<\gcd(m,n) < \min(m,n)$
gcd is the max of divisors sets intersection $D_n=\{1,p,q,n\}$ and $D_m = \{1,r,s,m\}$ hence we know now the $ \gcd(m,n) \in \{p,q\}\cap \{r,s\}\subset\{p,q,r,s\}$ hence the gcd returns a prime divisor of $n$ and $m$.


A positive $d'$ with $d'\mid n$ and $d'\mid x$ is called a common divisor and the greatest of them is called the greatest common divisor $d = \gcd(x,n)$.

Since $n$ is the product of two distinct primes, then any common divisor must divide $n$. By the fundamental theorem of arithmetic, the prime factorization of $n$ is unique (up to order), namely $n=p\cdot q$

Therefore any common divisor of $x$ and $n$ must divide at least one of $1,p,q,pq=n$.

  • $1$ iff $p\not\mid x$ or $q\not\mid x$
  • $p$ if $p \mid x$ and $q \not\mid x$
  • $q$ if $q \mid x$ and $p \not\mid x$
  • $n$ if $x \equiv 0 \bmod n$

as a conclusion $\gcd(x,n) \in \{1,p,q,n\}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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