Question

1. ATestforPrimalityisthefollowing:

   Given an integer n > 1, to test whether n is prime check to see if it is divisible by a prime number less than or equal to it’s square root. If it is not divisible by an of these numbers then it is prime.

We will show that this is a valid test.

1. prove

∀n, r, s ∈ N+, r s ≤ n → (r ≤ √n ∨ s ≤ √n)

b) Prove ∀ n ∈ N+ , n is not prime →∃p ∈ N ,(p prime ∧ (p≤√n) ∧ p∣n )

(c) State the contrapositive of the statement of part(b).

Answer 1

1. This statement in plain English says that , for every positive integer n,r,s , if the product of r and s is less than equal to n then this means either or and this statement is correct because if then

Hence the statement given is correct.

2. This statement says that if a natural number n is not prime then this means that there exist some prime number p with p \leq \sqrt{n} such that p | n I.e. p divides n.

Since statement is exactly aligned with property of non-prime number and hence it is correct.

3. The counter positive statement is

This basically means that for every natural number n, if for every integer p, either p is not prime, or p is greater than equal to root n, or p does not divide n, then n is prime

Please comment for any clarification

T<in

syn

T<in

n/r> in

Vn e N+, n is prime → Vp E N(p not prime V (p > n) Vpin)