This is for discrete, Please explain all the steps and this is worth 20 marks, s

Question

This is for discrete, Please explain all the steps and this is worth 20 marks, so the solution must be explained thoroughly

We will use N+ to refer to the set of all positive natural numbers (ie, starting at ). 1. (a) Prove (b) Prove Vn E Nt n composite 3p EN+,p is prime and pS vn and p n (c) One way to test whether a number is prime is the following: Given an integer n > 1, check if n is divisible by any prime number less than equal to its square root. If n is not divisible by any of these primes, then n prime. Write the contrapositive of 1b). Your solution should be written so that it clearly shows that the above test is indeed a valid method

Explanation / Answer

1. (a) Let us assume the result is false

i.e rs <= n ; r > n and s > n

Multiplying the two inequalities, we have

r * s > n * n

=> rs > n

This directly contradicts the statement rs <= n.

Therefore the assumtption that r > n and s > n is false.

=> r <= n or s <= n.

(b) Since n is composite, by definition, it must have atleast one prime factor.

Let p be a prime factor of n.

=> p | n.

If p <= n, the result is proved.

If not then, p > n

=> n/p < n/n

=> n/p < n

Since p | n, n | p is an integer.

Let n/p = q. Note that since n/q = p, q is also a factor of n.

=> q < n.

If q is a prime, the result is proved.

If q is composite, then it should have atleast one prime factor.

Let r be a factor of q. Since r|q and q|n, r|n.

Also since q < n and r|q, r < n and the result is proved.

(c) The contrapositive of 1(b) is :

~[p N+, p is prime and p <= n and p | n] -> ~[n N+, n is composite]

=> p N+ , ~[p is prime and p <= n and p | n] -> n N+, ~[n is composite]

=> p N+, p is composite or p > n or p n -> n N+, n is prime.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.