If $n$ is composite then there are integers $a$ and $b$ such that $n$ divides $ab$ but $n$ divides neither $a$ nor $b$.

Question

Theorem says-

If $n$ is composite then there are integers $a$ and $b$ such that $n$ divides $ab$ but $n$ divides neither $a$ nor $b$.

I knew that proof could be simple enough if we suppose n=$ab $ . But I want to know about any other better method of proving it. Sorry for latex mistakes.

Answer 1

Proof 1

Since $n$ is composite, just assume $n=a·b$. Thus

$$n\mid a·b\quad n\nmid a\quad n\nmid b$$

---

Proof 2

In virtue of the Fundamental Theorem of Arithmetic $$n=\prod ^k_{i=0}p_i^{\alpha_i}$$ where there are at least two primes $p_1$ and $p_2$ which divide $n$ (since $n$ is composite). So we can divide it into two parts: $$n=\prod ^{k-j}_{i=0}p_i^{\alpha_i}\times \prod ^k_{h=k-j+1}p_h^{\alpha_h}$$

Take now a prime $t>n$ (which you can certainly find since there are infinitely many primes).

Note that

$$n\mid \prod ^{k-j}_{i=0}p_i^{\alpha_i}\times \prod ^k_{h=k-j+1}p_h^{\alpha_h}\times t$$

However

$$n \nmid \prod ^{k-j}_{i=0}p_i^{\alpha_i}\quad \text{and} \quad n\nmid \prod ^k_{h=k-j+1}p_h^{\alpha_h}\times t$$