State/Primes dividing a product must divide a factor

From SlugmathWiki

Proposition
Proof

Proposition: (Primes dividing a product must divide a factor) Suppose that $p$ is a prime number. Suppose that $a,b \in \NN$. If $p$ divides $ab$, then $p$ divides $a$ or $p$ divides $b$.

More generally, suppose that $a_1, \ldots, a_k$ is a finite sequence of natural numbers. If $p$ divides the product $\prod_{i=1}^k a_i$, then there exists $i \in \NN$, such that $1 \leq i \leq k$ and $p$ divides $a_i$.

Logical Connections

This statement logically relies on the following definitions and statements: Def/Prime number, Def/Product, Def/Greatest common divisor, State/Linear Diophantine equations can be solved with the Euclidean algorithm, State/Two out of three principle for divisibility

The following statements and definitions rely on the material of this page: State/Being relatively prime to a product is equivalent to being relatively prime to the factors, and State/Uniqueness of prime factorization

To visualize the logical connections between this statements and other items of mathematical knowledge, you can visit the following cluster(s), and click the "Visualize" tab: Clust/Basic number theory

Products of two numbers

We begin by proving that if a prime divides a product of two natural numbers, it must divide one of the two numbers.

Suppose that $p$ is a prime number, and $a,b \in \NN$, and $p$ divides $ab$.

We prove if $p$ does not divide $a$, then $p$ divides $b$.

Suppose that $p$ does not divide $a$.

Let $g$ be the greatest common divisor of $p$ and $a$. Then $g$ divides $p$. Since $p$ is prime, it follows that $g = 1$ or $g = p$.

	If $g = p$, then since $g$ divides $a$, $p$ would divide $a$.
	This contradicts our previous hypothesis that $p$ does not divide $a$.

Hence $g = GCD(p,a) = 1$. Since linear Diophantine equations can be solved with the Euclidean algorithm, there exist integers $x$ and $y$, such that $px + ay = 1$.

Multiplying both sides in this equality by $b$, one finds that: $$pxb + aby = b.$$ Observe that $p$ divides $pxb$, and $p$ divides $aby$ (since it is assumed that $p$ divides $ab$). Therefore, by the State/Two out of three principle for divisibility, it follows that $p$ divides $b$.

Hence $p$ divides $b$.

We have proven that if $p$ does not divide $a$, then $p$ divides $b$. Hence $p$ divides $a$ or $p$ divides $b$.

Products of many numbers

Now, we prove that primes which divide a product $\prod_{i=1}^k a_i$ of many numbers must divide a factor. We prove this by induction on the number of terms, $k$, in the product.

$k=1$	Suppose that $p$ is a prime number, and $a_1$ is a natural numbers. Suppose that $p$ divides $\prod_{i=1}^1 a_i = a_1$. Then $p$ divides $a_1$, as desired.
$k > 1$.	Suppose that $k > 1$, and the desired result is proven for all smaller values of $k$. Suppose that $a_1, \ldots, a_k$ is a finite sequence of natural numbers, and that $p$ divides $\prod_{i=1}^k a_i$. Let $b = \prod_{i=2}^k a_i$; observe that this makes since since $k \geq 2$. It follows that $p$ divides $a_1 b$. By our previously proven result, it follows that $p$ divides $a_1$ or $p$ divides $b$. If $p$ divides $b$, the inductive hypothesis implies that $p$ divides at least one element of the set $\{ a_2, \ldots, a_k \}$. Hence $p$ divides at least one element of the set $\{a_1, \ldots, a_k \}$.
Hence, a prime which divides a product $\prod_{i=1}^k a_i$ must divide one of the factors $a_1, \ldots, a_k$ of the product.

State/Primes dividing a product must divide a factor

From SlugmathWiki

Logical Connections

Products of two numbers

Products of many numbers

Views

Personal tools

Navigation

Mathematics

Pegagogy

Search

Toolbox