Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 3 down vote accepted

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

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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