Efficient way to check if prime factors are the same

Question

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.

Answer 1

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.

Answer 2

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)$