# If m satisfies Euclid's Lemma does it mean m is prime?

Let $$m$$ be a natural number larger than 1, and suppose that $$m$$ satisfies the following property:

For any integers $$a$$ and $$b$$, if $$m$$ divides $$ab$$, then $$m$$ divides either $$a$$ or $$b$$ (or both).

Show that $$m$$ must be prime.

I think we should solve this question with a proof by contradiction. So, suppose $$m$$ is not prime, therefore $$\existsk$$ $$\in$$ $$\mathbb{Z}$$ such that $$k|m$$. We also notice that the property $$m$$ satisfies is Euclid's Lemma, and from it we can conclude $$gcd(a,m) = m$$ and $$gcd(b,m) = m$$ depending on if $$m|a$$ or $$m|b$$ or both.

Now from here I don't know how I should proceed further. In fact, I'm not sure if I'm looking in the right direction, so your help would be appreciated.

• Hint: If $m$ is not prime then $m=ab$ with $m>a,b>1$. – lulu Jul 20 '19 at 19:49

You are right: suppose $$m\in \mathbb{N}$$ is not prime and let's fix $$(k,l)\in \mathbb{N}^2$$ such that $$m=kl$$ and $$k,l \neq m$$ then either $$m\mid k$$ or $$m\mid l$$ which is absurd as both k and l are strictly less than m (and positive)
Hint:  first show: $$\,p\,$$ is prime $$\!\iff\! [\,p \color{#c00}{\bf =} ab\,\Rightarrow\, p\mid a\,$$ or $$\,p\mid b\,],\,$$ then use $$\,p\color{#c00}{\bf =}ab\,\Rightarrow\, p\mid ab$$