Tricks, Proof Methods, Equivalences

Question 1

Answer 1

1. Assume b | a
2. aq =b
3. |a| = |qb| = |q| |b| >= |b|
4. |b| <= |a|
5. b <= |a|

Question 2

Answer 2

1. There exists q1, q2, r1, r2 that both represent
2. Inequalities of r1 and r2
   
   1. 0 < r1 < b
   2. -b< -r2 < 0
3. -b < r1 - r2 < b
4. 0 = a - a = (q1 - q2)b + (r1 - r2)
5. (q1 - q2)b = (r1 - r2)
6. b| r1 - r2 ==> -b < kb < b = -1 < k < 1 ==> k = 0
7. r1 = r2
8. (q1-q2)b = 0 ==> q1 = q2

Question 3

Def: Common Divisor

Answer 3

Let a and b be integers. An integer c is called a common divisor of a and b if c | a and c | b.

Question 4

Answer 4

bx + cx = (ra)x + (sa)y = a (rx + sy)

Question 5

Answer 5

Case 1: a and b non-zero

1. a(1)+b(-1) (by DIC) = a - qb = r : d|r
2. let c: c | b, c | r
3. by DIC c | (qb + r) ==> c | a
4. c and d divide a, b, r –> gcd(a, b) = gcd(b, r)

Question 6

Answer 6

Case 1: a and b non-zero

1. c | (ax + by) = c | (as + bt) = c | d
2. from bounds of div : c <= |d|
3. d = gcd(a,b)

Case 2: a and b 0

1. as+bt = 0
2. gdc(0, 0) = 0 : d = gcd(a,b)

Question 7

Answer 7

Range is unrestricted and applies for all a and b

Question 8

Explain the steps of the algorithm

Answer 8

1. Table of 4 columns, x, y, r, q
2. compute q <- floor(ri-1 / ri-2)
3. compute row = row-2 - (q)row-1
4. x and y are the factors for gcd

Question 9

Answer 9

1. c | a, c | b
2. Bezouts lemme says as + bt = d where d = gcd(a,b)
3. by DIC c|(as +bt) hence c | d

Question 10

Def: Coprime

Answer 10

Two integers a and b are coprime if gcd(a,b) = 1

Question 11

Answer 11

1. Bezouts Lemma as + bt = 1
2. 1 | a, 1 | b, for all a and b
3. from GCD Characterization theorem we have gcd(a,b) = 1

Question 12

Answer 12

1. Bezout’s lemma:
   
   1. There exists s and t so that as + bt = d
2. hence a/d *s + b/d *t = 1
3. Since gcd(a,b) = d, d | a, d | b, a/d, b/d are ints
4. Hence by Coprimeness Characterization Theorem gcd (a/d, b/d) = 1

Question 13

Answer 13

1. From Bezouts Lemma
   
   1. as + ct = 1
   2. asb + cbt = b
2. since c | ab and c | c
   
   1. c | ab(s) + c(bt) = c | b

Question 14

Answer 14

Strong Induction

1. Base case (2)
2. Hypothesis - all k>=2 are true
3. P(k+1) case 1: prime is true
4. P(k+1) case 2: k+1 = rs
   
   1. Since both r and s are >=2 by inductive hypothesis can be written as primes

Question 15

Def: Prime vs Composite

Answer 15

Prime is >1 and its only positive divisors are 1 and prime itself.

Otherwise composite.

Question 16

Answer 16

Using Contradiction:

1. Define N = p1*p2*p3…. *pn + 1
2. P is no prime since N > pi for all pi
3. remainder 1 when dividing by pi
   
   1. 1 is not equal to 0
   2. 1 < p1
   3. pi>= 2 so pi doesnt divide N for all i
4. Cant be written as a product of primes which is a contradiction

Question 17

Answer 17

1. A ==> C V B
2. A & ¬ B ==> C
3. gcd(a, p)=1 or p
4. since p | a gcd(a, p) = 1
5. By Coprimeness and divisibility theorem, proven