Answers must be correct. Or else it will be flagged. All sub-parts need to be an

ID: 3199197 • Letter: A

Question

Answers must be correct. Or else it will be flagged. All sub-parts need to be answered with step by step process showing all work and reasoning.

YOU MUST PROVIDE ALL ANSWERS AS PER THE QUESTIONS.

DON'T PROVIDE WRONG ANSWERS AND DON'T ANSWER IF YOU DON'T WANT TO ANSWER ALL SUB-PARTS. INCOMPLETE ANSWERS WILL BE FLAGGED

DISCRETE STRUCTURES

For part a. The symbol means not divisible.

Question 2 (8 points) Prove the following using a contrapositive proof. a) If 7? 7 b) For any integer z, if 3r37 is even then z is odd. n', then

a) The statement is if 7 does not divide n2, then 7 does not divide n.

The contrapositive is

If 7 | n, then 7 | n2.

Proof : Since 7 divides n, let n = 7k where k is an integer.

=> n2 = (7k)2 = 49k2 = 7 * 7k2.

Let 7k2 = r where r is an integer.

=> n2 = 7r.

Since RHS has a factor 7, LHS must be divisible by 7.

Therefore, 7 | n2.

By proof of contraposition, the given statement is true.

b) For any integer x, if 3x3 - 7 is even, then x is odd.

The contrapositive is

If x is even, then 3x3 - 7 is odd.

Proof : Since x is even, let x = 2k where k is an integer.

=> 3x3 - 7 = 3*(2k)3 - 7

= 3 * 8k3 - 7

= 24k3 - 7

= 24k3 - 8 + 1

= 2(12k3 - 4) + 1

Let 12k3 - 4 = r where r is an integer.

=> 3x3 - 7 = 2r + 1

Since RHS is of the form 2r + 1, it is odd and therefore, LHS is also odd.

=> 3x3 - 7 is odd.

By proof of contraposition, the given statement is true.

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