Quiz 1 Lemmas/Theorems

Question 1

2-out-of-3 Lemma

Answer 1

Let a,b,c,d ∈Z, such that a + b = c. If d divides any two of a,b,c, it also divides the 3rd

Question 2

First important Lemma about GCD

Answer 2

For any integer a, GCD(a,0) = |a|

Question 3

Second important Lemma about GCD

Answer 3

For any integers a,b,q,r ∈Z satisfying a = qb + r, GCD(a,b) = GCD(b,r)

Question 4

Euclid’s Lemma

Answer 4

Let a,b,c ∈Z be such that GCD(a,b) = 1. If a|bc then a|c

Question 5

Theorem about LDE

Answer 5

Let ax + by = c be a LDE, Then either:
1) GCD(a,b) does not divide c and it has no solutions
2) If GCD(a,b)|c, then it has infinitely many solutions. They are given by the equations used in solving for Diophantine Equations

Question 6

Prime Factorization Lemma

Answer 6

Every integer n >= 2 is divisible by a prime

Question 7

Prime Factorization Corr.

Answer 7

Every integer n >= 2 can be written as a product of primes

Question 8

Euclids Lemma for Primes

Answer 8

If p is a prime and a,b ∈Z such that p|ab then either p|a or p|b

Question 9

Uniqueness of prime factorization Theorem

Answer 9

Let n∈Z, n >= 2. Let n = p1 x p2 … x pk be a prime factorization of n. Then this factorization is unique up to ordering of the primes

Question 10

Lemma about LCM

Answer 10

LCM(a,b) = 2^max(e2, f2) x 3^max(e3, f3)

Question 11

Corr. about LCM

Answer 11

LCM(a,b) x GCD(a,b) = ab

Question 12

Multiplicative Functions

Answer 12

An arithmetic function, f, is said to be multiplicative if, for any a,b ∈Z+ such that GCD(a,b) = 1, f(a,b) = f(a)f(b) and f(1)=1

Question 13

Theorem about coprime positive integers

Answer 13

Let a,b be co-rime positive integers. If u|a and v|b, then uv|ab.

Question 14

Corr. about sigma(n)

Answer 14

sigma(n) is multiplicative