Does $ab \equiv 0 \pmod n$ imply $n\mid a$ or $n\mid b$ if $n$ is prime? I know that $ab \equiv 0 \pmod n$ does not imply $n\mid a$ or $n\mid b$ for regular $n$. When $n$ is prime can I use  the fundamental theorem of arithmetic to say that $n\mid a$ or $n\mid b$ ? I am currently unsure how to express this as a proper proof.
 A: The result that $p \, \text{prime}, p \mid {ab} \Rightarrow p \mid a$ or $p \mid b$ is known as Euclid's lemma, and is used in the proof of the fundamental theorem of arithmetic, so to use the fundamental theorem of arithmetic to show Euclid's lemma would be circular reasoning.
A: The following is one of the standard proofs of the result you are interested in. In the usual presentations of number theory, it comes before the Fundamental Theorem of Arithmetic, because it is the key result used in the proof of the FTA.
Suppose that $p$ does not divide $a$, and $p$ divides $ab$. We show that $p$ must divide $b$.
Since $p$ does not divide $a$, the numbers $a$ and $p$ are relatively prime. Then, by Bezout's Theorem, there exist integers $x$ and $y$ such that $ax+py=1$.
Multiply through by $b$. We get $abx+pyb=b$.
But $p$ divides $ab$ by assumption, so $p$ divides $abx$. And of course $p$ divides $pyb$. It follows that $p$ divides $abx+pyb$, that is, $p$ divides $b$.
A: Yes, you can imply n|a or n|b if 'n' is a prime. You can start with the Fundamental Theorem by saying - 


*

*if ab ≡ 0 (mod n) => n|ab

*Now, given that 'n' is prime => n|a or n|b


I think these two steps would be perfectly fine provided you state the Theorem before this.
