# Efficient way to check if prime factors are the same

Given two positive integers $m$ and $n$ such that $1<m<n$, what is an efficient way to check if the prime factors of $m$ and $n$ are exactly the same, i.e, if $\mathcal{P}_m=\mathcal{P}_n$, where $\mathcal{P}_k$ denotes the set consisting of all the prime factors of the number $k$?

I have a guess, but don't know how to prove. If we set $a_1=n/m$, then if $a_1>1$ and if $\text{gcd}\,(a_1,m)=1$, then $m$ and $n$ don't have the same prime factors. Otherwise, and here's my guess, if $m>a_1>1$ and $\text{gcd}\,(a_1,m)\neq a_1$ or if $a_1>m$ and $\text{gcd}\,(a_1,m)\neq m$ then $m$ and $n$ don't have the same prime factors. Otherwise, if $m>a_1>1$ and $\text{gdc}\,(a_1,m)=a_1$, then $m$ and $n$ have the same primes factors and if $a_1>m$ and $\text{gdc}\,(a_1,m)=m$ we repeat the process with $a_2=a_1/m$. And if for some $r$, $a_r=1$, then $m$ and $n$ have the same prime factors.

In addition to the fact that I can't show if my process if correct, it seems to me that it is too complicated. So, if there is other (less complicated) algorithm, please show me.

• @AndréNicolas what I mean is that if we call by $\mathcal{P}_m$ the set consisting of all the prime factors of $m$, then I want $\mathcal{P}_m=\mathcal{P}_n$. Is the "i.e." part really not saying this? Commented Mar 15, 2016 at 4:19
• For the first $m=120, n=450$ is acceptable because the prime factors of both are $2,3,5$. Under the i.e. it is not acceptable because $i_1 \gt j_1$ For the i.e. part you can just check that $m$ divides $n$ Commented Mar 15, 2016 at 4:23
• @AndréNicolas you're right, thanks for noting this. I'll edit the question. Commented Mar 15, 2016 at 4:25
• @Larara Yes, your process is correct. This is a correct way of finding if $m$ and $n$ have the same set of factors. Commented Mar 15, 2016 at 10:26
• @Dhruv Isn't there another, more efficient, way? Commented Mar 15, 2016 at 21:21

You can base an algorithm on the following theorem:

$$P(m)\subseteq P(n)\iff \begin{cases} m=1\\\quad\text{or}\\ (m,n)\gt1\text{ and }P(m/(m,n))\subseteq P(n) \end{cases}$$ where $(m,n)=\gcd(m,n)$.

Borrowing one of Steven Gregory's examples, let's show that $P(120)=P(450)$ by showing first that $P(120)\subseteq P(450)$ and then that $P(450)\subseteq P(120)$.

For the first inclusion, we note that $(120,450)=30\gt1$, hence

$$P(120)\subseteq P(450)\iff P(4)\subseteq P(450)$$

We next see that $(4,450)=2\gt1$, hence

$$P(4)\subseteq P(450)\iff P(2)\subseteq P(450)$$

Finally, $(2,450)=2\gt$, hence

$$P(2)\subseteq P(450)\iff P(1)\subseteq P(450)$$

and the theorem says the last statement, $P(1)\subseteq P(450)$, is true.

For the reverse inclusion, similar considerations give

\begin{align} P(450)\subseteq P(120)&\iff P(15)\subseteq P(120)\quad\text{since }(450,120)=30\gt1\\ &\iff P(1)\subseteq P(120)\quad\text{since }(15,120)=15\gt1\\ \end{align}

Just to give one more example, let's show that $P(420)\not=P(450)$:

\begin{align} P(420)\subseteq P(450)&\iff P(14)\subseteq P(450)\quad\text{since }(420,450)=30\gt1\\ &\iff P(7)\subseteq P(450)\quad\text{since }(14,450)=2\gt1\\ \end{align}

but $(7,450)=1$ with $7\not=1$, so the theorem says $P(7)\not\subseteq P(450)$, which implies $P(420)\not\subseteq P(450)$, which means the two certainly aren't equal.

Remark: It's worth noting that the algorithm described here will take something like $10$ iterations to show $P(1024)\subseteq P(2)$, which seems excruciatingly slow, but in the grand scheme of things, that's only about three times the number of digits in the number $m$, which is not so bad. In particular, the algorithm never requires you to explicitly find any of the prime factors of $m$ or $n$; it will, for example, run happily on a pair of million-digit numbers each of which is a product of powers of some unknown set of thousand-digit primes.

• Just one thing, in showing that $P(1)\subseteq P(120)$, didn't you mean $(15,120)=15$ instead of $(15,120)=8$? Commented Mar 18, 2016 at 2:09
• @Larara, yes, thank you. I'll fix it. Commented Mar 18, 2016 at 2:13
• Does this theorem have a name? Commented Mar 18, 2016 at 3:48

Let $1 < m < n$ and let $g = gcd(m,n)$ This is what I came up with. I don't know how much help it is.

$(1.)\color{red}{ \quad P(m) = P(n) \iff P\left(\dfrac mg \cdot \dfrac ng \right) = P(m)\; \text{\{This is FALSE}\}}$

$(1') \quad \text{If}\; m=an \; \text{and} \; a \mid n, \; \text{then} \;P(m) = P(n)$

$(2.) \quad \text{If}\;d\mid m \; \text{ then}\; \left\{ P\left(\dfrac md \right) \subseteq P(d) \implies P(d) = P(m)\right\}$

$(3.) \quad \gcd(m,n) = 1 \implies P(m) \ne P(n)$

$(4.) \quad P(ab) = P(a) \cup P(b)$

# EXAMPLE 1

$450 = 15 \cdot 30 \;\text{and}\; 15 \mid 30 \implies P(450) = P(30)$

# EXAMPLE 2

$P(180) = P(1050) \iff P(6 \cdot 35) = P(180) \iff P(180) = P(210)$
$\iff P(6 \cdot 7) = P(180) \iff P(42) = P(180)$

$P(42) = \{2,3,7\} \nsubseteq P(180)$, so $P(180) \ne P(1050)$

## EXAMPLE 3

$P(180) = P(30) \cup P(6) = \{2,3,5\} \cup \{2,3\} = \{2,3,5\}$
$P(450) = P(30) \cup P(15) = \{2,3,5\} \cup \{3,5\} = \{2,3,5\}$
Hence $P(180) = P(450)$

• (1.) is wrong. Consider $m=6,n=12$. Commented Jan 18, 2017 at 6:46
• @ccorn - You are right. I need to think about that. Commented Jan 18, 2017 at 7:58