 # Proofs in Discrete Math. forall n in N+, n composite rightarrow exists p in N+, p is prime and p <= sqrtn and p|n. Graham Beasley 2022-07-16 Answered
Proofs in Discrete Math
$\mathrm{\forall }n\in N+$, n composite $\to \mathrm{\exists }p\in N+$, p is prime and $p\le \sqrt{n}$ and p|n.
Am I supposed to prove that $p\le \sqrt{n}$ and p|n when n is composite and p is prime? Could someone fix my translation if I'm wrong?
You can still ask an expert for help

## Want to know more about Discrete math?

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it Makenna Lin
Step 1
Our argument is based on the number of primes m that divide n. Thus if $m=1$, then n is of the form $n={p}^{k}$ wheareas p is a prime, and $k\ge 2$ (for n to be composite).
Step 2
Thus $n\ge {p}^{2}$ and $p\le \sqrt{n}$. if $m\ge 2$, then we can write n as $n=b\cdot {p}^{r}\cdot {q}^{s}$ whereas p,q are distinct primes, and $b,r,s\ge 1$ and are natural numbers. WLOG, assume $p\le q$. So: ${p}^{2}\le pq\le {p}^{r}\cdot {p}^{s}\le b\cdot {p}^{r}\cdot {q}^{s}=n$, and ${p}^{2}\le n$ or $p\le \sqrt{n}$. In both cases, p∣n.