Definition of prime number. Prove that If $p$ is a prime and $p ~|~ ab$, then $p ~|~ a$ or $p ~|~ b$.

Definition: An integer $p > 1$ is called a prime number, or simply a prime, if its only positive divisors are $1$ and $p$. An integer greater than $1$ that is not a prime is termed composite.


Example: We can observe that $2, 3, 5, 7$ etc. are prime numbers whereas $4, 6, 8, 9, 10$ etc. are composite numbers.

Theorem: If $p$ is a prime and $p ~|~ ab$, then $p ~|~ a$ or $p ~|~ b$.

Proof: If $p ~|~ a$, then we are done. So suppose that $p \nmid a$. Therefore $gcd(p,a) = 1$. Hence by Euclid Lemma, $p ~|~ b$..



Popular posts from this blog

Definition of divisibility and Theorem on divisibility

The Division Algorithm / Prove that given integers $a$ and $b$, with $b > ~ 0$, there exist unique integers $q$ and $r$ such that $a = b \cdot q +r$, where $0 \leq r < b$. The integer $q$ is called the $\textbf{quotient}$ and the integer $r$ is called $\textbf{remainder}$.

Define Greatest Common Divisor and Prove that if $a$ and $b$ are any integers, not both of them are zero. Then there exist integers $x$ and $y$ such that $gcd(a, b) =a \cdot x + b \cdot y$.