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!

  • 2
    $\begingroup$ Are you not allowed to use uniqueness of prime factorizations? $\endgroup$ – Bill Dubuque Oct 19 '18 at 13:11
  • 1
    $\begingroup$ 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. $\endgroup$ – Sam Streeter Oct 19 '18 at 13:16
  • $\begingroup$ Or use the fact that if a prime $p$ divides $ab$, then it must divide $a$ or $b$. $\endgroup$ – Robert Israel 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.

  • 2
    $\begingroup$ 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$. $\endgroup$ – Robert Israel Oct 19 '18 at 13:24
  • $\begingroup$ True. I guess I should replace "essential" with "useful". $\endgroup$ – Sam Streeter Oct 19 '18 at 13:25

$n<m \Rightarrow n<m^j$; $n<n^i$. Since $n,m\in \mathbb{P}$, there can be no smaller prime than $n$ which divides $n^im^j$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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