Please explain in detail... the textbook solution here does not give thorough ex
ID: 3144436 • Letter: P
Question
Please explain in detail... the textbook solution here does not give thorough explanation
Discrete Mathematics
a. Prove by contraposition: For all positive integers n, r, and s, if rs sn, thenr s norss n b. Prove: For all integers n1, if n is not prime, then there exists a prime number p such that p-yM and n is divisible by p. (Hints: Use the result of part (a), Theorems 4.3.1,4.3.3, and 4.3.4, and the transitive prop- erty of order.) c. State the contrapositive of the result of part (b) The results of exercise 31 provide a way to test whether an integer is prime.Explanation / Answer
a. For all positive integers n,r and s if rs <= n, then r <= n or s <= n.
The contrapositive of the statement is if r > n and s > n, then rs > n.
Proof: Since r > n and s > n, multiplying
=> rs > n * n
=> rs > n.
b. For all integers n > 1, if n is not a prime, then there exists a prime number p such that p <= n and n is divisible by p.
Proof: Since n is not a prime, there are 2 factors (not necessarily distinct) a and b such that ab = n where a and b are neither 1 nor n.
If b > n, then a = n / b
=> a < n / n
=> a < n
If b = n, a = n / n = n
Thus atleast one of a and b <= n
Thus n has a factor p <=n.
c. The contrapositive of this statement is if there does not exist a prime number p such that p <= n and n is not divisible by p, then n is a prime.