# 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.

-
Yes, for $n$ prime the implication is correct. I wouldn't call it the Fundamental Theorem of Arithmetic, but it is the key result used for the proof of the FTA. Are you familiar with the result often called Bezout's Theorem (gcd of $a$ and $b$ can be expressed as a linear combination of $a$ and $b$)? – André Nicolas Feb 8 '13 at 7:58
I've always thought $(p \mid ab) \implies (p \mid a) \lor (p \mid b)$ is the definition of prime numbers. – dtldarek Feb 8 '13 at 9:37

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

-

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.

-

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.

-