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

Graham Beasley

Answered question


Proofs in Discrete Math
n N +, n composite p N +, p is prime and p n and p|n.
Am I supposed to prove that p n and p|n when n is composite and p is prime? Could someone fix my translation if I'm wrong?

Answer & Explanation

Makenna Lin

Makenna Lin

Beginner2022-07-17Added 16 answers

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 2 (for n to be composite).
Step 2
Thus n p 2 and p n . if m 2, then we can write n as n = b p r q s whereas p,q are distinct primes, and b , r , s 1 and are natural numbers. WLOG, assume p q. So: p 2 p q p r p s b p r q s = n, and p 2 n or p n . In both cases, p∣n.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?