# How do I prove that if $\text{gcd}(m,n) \neq 1$, the result is $p$ or $q$ in RSA?

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?

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

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\}$$