# What is the least prime factor of $n^i \cdot m^j$, for prime numbers $n, m$ such that $n < m$?

The least prime factor (lpf) of a natural number is the smallest prime number that divides that number. In particular the least prime factor of any even number equals $$2$$ and the least prime factor of a prime number is itself. But a less trivial fact about least prime factors is that the least prime factor of $$n^i$$ equals $$n$$, for a prime number $$n$$ and a non zero positive integer $$i$$, that is,

$$\mathsf{lpf} (n^i) = n, \qquad \text{for } i > 0.$$

This can be proven by induction on $$i$$: the base case is trivial because $$n$$ is prime; for the inductive case, we can use the fact that $$\mathsf{lpf} (n^{i+1})$$ divides $$n^{i+1}$$ and a lemma that implies that if any natural number $$m$$ divides $$n^{i+1}$$ then there exists a zero positive integer $$j$$ such that $$j \le i +1$$ and $$m = n^j$$.

However, now I wish to prove a slightly more general theorem, namely that given two prime numbers $$n$$ and $$m$$ such that $$n < m$$ we have

$$\mathsf{lpf} (n^i \cdot m^j) = n, \qquad \text{for } i, j > 0.$$

I am trying to prove it by double induction on $$i$$ and $$j$$ but I am getting stuck. First I need to show that the least prime factor of $$n \cdot m$$ is $$n$$, but how? Well, I could suppose that there exists a prime number $$k < n$$ that factors $$n \cdot m$$ and try to derive a contradiction. But now I have no clue how to proceed... And what about the inductive cases?

Any help would be greatly appreciated!

• Are you not allowed to use uniqueness of prime factorizations? Oct 19 '18 at 13:11
• You didn't actually state that $n$ is prime in your less trivial fact. It's implicit in what you say after the first equation, but you should fix that. And that's a pretty trivial fact if you're allowed to use the fundamental theorem of arithmetic, as is the whole thing really. Even if you're not allowed to just use the fundamental theorem of arithmetic, it's easy enough to prove, and then the desired result follows pretty much immediately. Oct 19 '18 at 13:16
• Or use the fact that if a prime $p$ divides $ab$, then it must divide $a$ or $b$. Oct 19 '18 at 13:20

By the fundamental theorem of arithmetic (existence and uniqueness of prime decomposition), the prime factors of $$n^i \cdot m^j$$, where $$n$$ and $$m$$ are prime, are precisely $$n$$ and $$m$$. Since $$n < m$$, we must have $$\textrm{lpf}\left(n^i \cdot m^j\right) = n$$.
The fundamental theorem of arithmetic is easy to prove. The uniqueness part is what is useful here. To prove that, assume two distinct prime decompositions and use the fact that, for $$p$$ prime and $$a$$, $$b \in \mathbb{N}$$, $$p|ab \implies p|a$$ or $$p|b$$ along with the definition of prime numbers.
• No need to prove the uniqueness part of FTA, if you have the fact that $p \mid ab \implies p \mid a \text{ or } p \mid b$. Oct 19 '18 at 13:24
$$n; $$n. Since $$n,m\in \mathbb{P}$$, there can be no smaller prime than $$n$$ which divides $$n^im^j$$.