# divisibility by prime number

###### Theorem.

Let $a$ and $b$ be integers and $p$ any prime number.  Then we have:

 $\displaystyle p\mid ab\quad\Leftrightarrow\quad p\mid a\;\lor\;p\mid b$ (1)

Proof. Suppose that  $p\mid ab$.  Then either  $p\mid a$  or  $p\nmid a$.  In the latter case we have  $\gcd(a,\,p)=1$,  and therefore the corollary of Bézout’s lemma gives the result  $p\mid b$.  Conversely, if  $p\mid a$  or  $p\mid b$,  then for example  $a=mp$  for some integer $m$; this implies that  $ab=mb\cdot p$,  i.e.  $p\mid ab$.

Remark 1. The theorem means, that if a product is divisible by a prime number, then at least one of the factor is divisibe by the prime number. Also conversely.

Remark 2. The condition (1) is expressed in of principal ideals as

 $\displaystyle(ab)\subseteq(p)\quad\Leftrightarrow\quad(a)\subseteq(p)\,\lor\,(% b)\subseteq(p).$ (2)

Here, $(p)$ is a prime ideal of $\mathbb{Z}$.

Title divisibility by prime number DivisibilityByPrimeNumber 2013-03-22 14:48:18 2013-03-22 14:48:18 pahio (2872) pahio (2872) 18 pahio (2872) Theorem msc 11A05 divisibility by prime PrimeElement DivisibilityInRings EulerPhiAtAProduct RepresentantsOfQuadraticResidues