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

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

Question 3 (16 points) Prove the following statements by contradiction a) Let a, b,c E Z. If c2, then a or b is even. (You may use results from Question 1) b) The number 3 is irrational.

Explanation / Answer

1)

Assumption: Every odd perfect square is of the form 4m+1.

Proof:

(2k+1)2 = 4 (k2+k) + 1 = 1 (mod 4). An integer is odd iff its square is odd. Now, if c2=a2+b2 with both a and b odd, then c2 =1+1=2( mod 4), a contradiction, since the only squares modulo 4 are 0 and 1.

2)

Suppose that 91/3 = m/n m, n integers with GCD(m,n)=1

This may be assumed because if d is an integer divisor of both m and n, then m/n=(m/d)/(n/d)m/n=(m/d)/(n/d).

Then 9n3=m3

so that 3 divides m3, hence m since 3 is prime. Thus 33=27 divides both sides of the equality so that 3 divides n3, hence n for the same reason as above. This contradicts the assumption that m and n are coprime.

This arguent generalizes immediately to showing that the n-th root of an integer which is not an n-th power of an integer is not rational.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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