Chapter 2: Direct Proofs

Question 1

Definition of an even integer?

Answer 1

An integer n is even if n=2k for some integer k;

Question 2

Definition of an odd integer?

Answer 2

An integer n is odd if n=2k + 1 for some integer k;

Question 3

Proof:

Proposition that the sum of two even integers is even?

Answer 3

• Let two random int. (m and n) be even so that m=2a and n= 2b where a,b are integers
• Then,
  * n + m = 2a + 2b = 2 (a + b)
• Given that the sum of two integers are also integers this meets the definition of an even number. ( n = 2k where k is any integer).

Question 4

Prove this Proposition:

The sum of two odd integers is even?

Answer 4

Question 5

Prove the Proposition that:

If n is an odd integer, then N^2 is an odd integer?

Answer 5

Question 6

What is the symbol in mathematics for “implies”?

Answer 6

⟹

Question 7

What is the Structure of a Direct Proof?

Answer 7

• Proposition. P ⟹ Q
• Proof Assume P
  * “An Explanation of what P means
  * apply algebra, logic, techniques
  * Get to the definition of Q
• Therefore Q

Question 8

What is Proof by Cases?

Answer 8

• Breaks up proofs into smaller proofs
• E.g. in an example with all integers you may need to break this down into a case for even numbers and one for odd.

Question 9

Prove the Proposition:

If n is an integer, then n^2 + n + 6 is even?

Answer 9

Question 10

What is the definition of divisibility?

Answer 10

A nonzero integer a is said to divide an integer b if b = ak for some integer k.

When a does divide b, we write “ a|b” and when a does not divid b we write “a∤b”

Question 11

Prove this Proposition:

Let a, b and c be integers. If a|b and b|c, then a|c?

Answer 11

Question 12

What is the Division Algorithm Theorem?

Answer 12

For all integers a and m with m > 0 there exist unique integers q and r such that:

a = mq + r

where 0 <= r < m

EXAMPLESSSSS

Question 13

What is the Definition of the Greatest Common Divisor?

Answer 13

Let a and b integer. If c|a and c| b, then c is said to be a common divisor of a and b

The greatest common divisor of a and b is the largest integer d such that d|a and d|b. This number is denoted gcd(a,b)

EXAMPLESSSSS

Question 14

What is the Bézout Identity?

Answer 14

If a and b are positive integers, then there exist integers k and l such that:

gcd(a,b) = ak + bl

Question 15

What is the Proof for the greatest common divisor?

Answer 15

GENERAL LOGIC –> ref proof

Question 16

What is the definition of Modular Congruence?

Answer 16

For integers a, r and m we say that a is congruent to r modulo m and we write a ≡ r (mod m), if m | (a-r)

*** EXAMPLES

Question 17

What are the two metaphors for Modular Congruence?

Answer 17

1. Boxes
2. Clocks

Question 18

What are the Properities of Modular Arithmetic?

Answer 18

Assume that a,b,c,d and m are integers, a ≡ b (mod m) and c ≡ d (mod m). Then,

i) a + c ≡ b+d (mod m)
i) a - c ≡ b-d (mod m)
i) a * c ≡ b*d (mod m)

Question 19

Prove this Proposition:

Assume that a,b,c,d and m are integers and a ≡ b (mod m) and c ≡ d (mod m), Then:

a + c ≡ b + d (mod m)

Question 20

What is the definition of a prime and composite number?

Answer 20

An integer p >= 2 is prime if its only positive divisors are 1 and p.

An integer n >= 2 is composite if it is not prime, Equivalently, n is composite if it can be written as n =st where s and t are integers and 1 < s,t < n

Question 21

What is the Lemma Required for the Proof of the Modular Cancellation Law?

Question 22

What is the Proof for the Prime Number Lemma?

Question 23

What is the Modular Cancellation Law?

Answer 23

Let a,b,k and m be integers with k ≠ 0. If ak ≡ bk (mod m) and gcd(k,m) = 1, then a ≡ b(mod m).

Question 24

What is the Proof for the Modular Cancellation Law?

Question 25

What is Fermat’s Little Theorem?

Answer 25

If a is an integer and p is prime which does not divide a, then

a^p-1≡1(mod p).

Question 26

What is the proof for the following Proposition:

Assume that x and y are positive numbers. If x >= y, then sqrt(x) >= sqrt(y).

Question 27

What is the AM-GM inequality?

Answer 27

If x and y are positive real numbers, then sqrt(xy) <= (x+y)/2

Question 28

What is the Proof for the AM-GM Inequality Theorem?