Direct Proof and Counterexample

Even and Odd

n is even ⇒ n = 2k for some integer k

n is odd ⇒ n = 2k+1 for some integer k

a. Is 0 even?

Yes, 0 = 2·0.

b. Is −301 odd?

Yes, –301 = 2(–151) + 1.

c. If a and b are integers, is 6a2b even?

6a2b = 2(3a2b), and since a and b are integers, so is 3a2b

Prime and composite integers (소수와 합성수)

prime = if and only if n > 1 and for all positive integers r and s, if n = rs, then either r or s equals n.

composite = if and only if n > 1 and n=rs for some integer r and s with 1 < r < n and 1< s < n

prime은 n=rs이면 모든 양의 정수 r과 s에 대해서 하나는 1이고 하나는 n인 수이다.

composite은 n=rs일때 적어도 하나의 양의 정수 쌍 r과 s에 대해서 둘다 1보다 크고 n보다 작은 수

a. Is 1 prime?

No. A prime number is required to be greater than 1.

b. Is every integer greater than 1 either prime or composite?

b. Yes. Let n be any integer that is greater than 1. Consider all pairs of positive integers r and s such that n = rs.

• There exist at least two such pairs, namely, r = n and s = 1 and r = 1 and s = n. Moreover, since n = rs, all such pairs satisfy the inequalities 1 ≤ r ≤ n and 1 ≤ s ≤ n.