Description

CS 113 Discrete Mathematics
kisi ka bharosa nahi
√ √
1. Show that 2 is irrational. In other words, 2 cannot be written in the form where p,q ∈Z and q ̸= 0
√
Solution: Assume 2 is rational, then , where p,q ∈Z and q ̸= 0.
And is the lowest form it can be.

This implies p is even which means p = 2k, for some k ∈Z
4k2 = 2q2
2k2 = q2
This implies q is even.
But p and q cant both be even as they are in the lowest form possible thus the 2 would be canceled.
Here we have a contradiction.√
Thus 2 cannot be written in formwhere p,q ∈Z
√
Thus 2 is irrational.
2. Explain what you must do to disprove the statement: x3 + 5x + 3 has a root between x = 0 and x = 1
Solution: The statement in logical notation is
∃x such that (0 < x < 1 ∧ x3 + 5x + 3 = 0)
Giving a counterexample is not enough. Saying that when x = 0.5 then x3 + 5x + 3 ̸= 0 is not sufficient.
1
To disprove this statement, we need to prove that the negation is true which is
¬∃x such that 0 < x < 1 ∧ x3 + 5x + 3 = 0 ≡∀x such that ¬(0 < x < 1 ∧ x3 + 5x + 3 = 0)
Or in English
For all x, it is not the case that both x is between 0 and 1 and x3 + 5x + 3 = 0
3. Prove that for any integer n the number n2 + 5n + 13 is odd
Solution:
4. State the statement of Contradiction and verify that it is a valid argument.
Hint: In contradiction we are saying that A implies B is the same as saying that A and ¬B happening together is false.
Solution:
5. Show through contraposition the following proposition is true: x ∈Z. If 7x + 9 is even, then x is odd.
Solution:
6. Prove that “(a + b)2 = a2 + b2” is not an algebraic identity where a,b ∈R
Solution:
7. Prove the following claim: There exists irrational numbers a and b such that ab is rational.
Solution:
Show that xn + yn = zn has no solutions where x,y,z ∈Z with and x ̸= 0, whenever n ∈Z and n > 2 y ̸= 0, z ̸= 0
Solution:
8.
9. Prove that for m and n integers, if 2 divides m or 10 divides n, then 4 divides m3n2
Solution:
10. Show that there are infinitely many primes, in other words the set containing all prime numbers is infinite.
Definition: A prime number is a Natural number that is only divisible by 1 and itself, and has to be divisible by 2 different numbers.
Fundamental Theorem of arithmetic: Every integer N > 1 has a prime factorization, meaning either N is itself prime or can be written as a product of prime numbers.
Solution:
11. Show a direct proof that you are worthy of love
Solution: This statement is true by the axiom of humanity. The proof is trivial.
12. Give a counterexample to the statement
“If n is an integer and n2 is divisible by 4, then n is divisible by 4”
Solution:
13. Show through contraposition the following proposition is true : If x2 − 6x + 5 is even, then x is odd.
Solution:
14. In this question we will prove Euclid’s Lemma that if p is a prime number that divides ab then p divides a or p divides b.
We shall prove this by proving a lemma and using a corollary from that lemma.
Well ordering principle: Every set of positive integers have a smallest element.
Division algorithm: if a,b ∈Z, where b > 0, then there exists unique q,r ∈Z, a = bq + r where, 0 ≤ r < b
(a) Bezout’s lemma: for all integers a and b there exist integers s and t such that gcd(a,b) = as + bt
Solution:
(b) Corollary of bezout’s lemma: If a and b are relatively prime then as + bt = 1
Solution:
(c) Using the above corollary prove Euclid’s lemma.
Solution:
15. In solving coding questions, you would want to know whether your solution is valid or not in all cases. You can easily do that by giving a proof of correctness. Come up with a solution and give a proof of correctness for the following problem.
https://codeforces.com/problemset/problem/1635/C
Solution: