Test2ReferenceSheet

.pdf
Reference for MATH 135 Test 2, Fall 2022 Notation In MATH 135, we define the natural numbers N = { 1 , 2 , 3 , . . . } to be the set of positive integers. List of Propositions You may use any of the results below without proof. When you do, make sure to clearly state the name (e.g. Transitivity of Divisibility) or the acronym (e.g. TD) associated with the result that you are using. De Morgan's Laws (DML) For statement variables A and B , we have 1. ¬ ( A ∧ B ) ≡ ( ¬ A ) ∨ ( ¬ B ) 2. ¬ ( A ∨ B ) ≡ ( ¬ A ) ∧ ( ¬ B ) For statement variables A , B and C , the following rules hold for the logical operators ∧ and ∨ : Commutative Laws • A ∧ B ≡ B ∧ A • A ∨ B ≡ B ∨ A Associative Laws • A ∧ ( B ∧ C ) ≡ ( A ∧ B ) ∧ C • A ∨ ( B ∨ C ) ≡ ( A ∨ B ) ∨ C Distributive Laws • A ∧ ( B ∨ C ) ≡ ( A ∧ B ) ∨ ( A ∧ C ) • A ∨ ( B ∧ C ) ≡ ( A ∨ B ) ∧ ( A ∨ C ) Transitivity of Divisibility (TD) For all integers a , b and c , if a | b and b | c , then a | c . Divisibility of Integer Combinations (DIC) For all integers a , b and c , if a | b and a | c , then for all integers x and y , a | ( bx + cy ). Pascal's Identity (PI) For all positive integers n and m with m < n , we have n m = n − 1 m − 1 + n − 1 m Binomial Theorem, Version 1 (BT1) For all integers n ≥ 0 and for all real numbers x , (1 + x ) n = n X m =0 n m x m Binomial Theorem, Version 2 (BT2) For all integers n ≥ 0 and for all real numbers a and b , ( a + b ) n = n X m =0 n m a n − m b m Bounds By Divisibility (BBD) For all integers a and b , if b | a and a ̸ = 0 then b ≤ | a | . Division Algorithm (DA) For all integers a and positive integers b , there exist unique integers q and r such that a = qb + r and 0 ≤ r < b.
GCD With Remainders (GCD WR) For all integers a , b , q and r , if a = qb + r , then gcd( a, b ) = gcd( b, r ). GCD Characterization Theorem (GCD CT) For all integers a and b , and non-negative integers d , if d is a common divisor of a and b , and there exist integers s and t such that as + bt = d , then d = gcd( a, b ). B´ ezout's Lemma (BL) For all integers a and b , there exist integers s and t such that as + bt = d , where d = gcd( a, b ). Common Divisor Divides GCD (CDD GCD) For all integers a , b and c , if c | a and c | b then c | gcd( a, b ). Coprimeness Characterization Theorem (CCT) For all integers a and b , gcd( a, b ) = 1 if and only if there exist integers s and t such that as + bt = 1. Division by the GCD (DB GCD) For all integers a and b , not both zero, gcd ( a d , b d ) = 1, where d = gcd( a, b ). Coprimeness and Divisibility (CAD) For all integers a , b and c , if c | ab and gcd( a, c ) = 1, then c | b . Prime Factorization (PF) Every natural number n > 1 can be written as a product of primes. Euclid's Theorem (ET) The number of primes is infinite. Euclid's Lemma (EL) For all integers a and b and prime numbers p , if p | ab , then p | a or p | b . Unique Factorization Theorem (UFT) Every natural number n > 1 can be written as a product of prime factors uniquely, apart from the order of factors. Divisors From Prime Factorization (DFPF) Let n and c be positive integers, and let n = p α 1 1 p α 2 2 · · · p α k k be a way to represent n as a product of the distinct primes p 1 , p 2 , . . . , p k , where some or all of the exponents may be zero. The integer c is a positive divisor of n if and only if c can be represented as a product c = p β 1 1 p β 2 2 · · · p β k k , where 0 ≤ β i ≤ α i for i = 1 , 2 , . . . , k. GCD From Prime Factorization (GCD PF) Let a and b be positive integers, and let a = p α 1 1 p α 2 2 · · · p α k k , and b = p β 1 1 p β 2 2 · · · p β k k , be ways to express a and b as products of the distinct primes p 1 , p 2 , . . . , p k , where some or all of the exponents may be zero. Then gcd( a, b ) = p γ 1 1 p γ 2 2 · · · p γ k k where γ i = min { α i , β i } for i = 1 , 2 , . . . , k. Linear Diophantine Equation Theorem, Part 1 (LDET 1) For all integers a , b and c , with a and b both not zero, the linear Diophantine equation ax + by = c (in variables x and y ) has an integer solution if and only if d | c , where d = gcd( a, b ). Linear Diophantine Equation Theorem, Part 2, (LDET 2) Let a , b and c be integers with a and b both not zero, and define d = gcd( a, b ). If x = x 0 and y = y 0 is one particular integer solution to the linear Diophantine equation ax + by = c , then the set of all solutions is given by { ( x, y ) : x = x 0 + b d n, y = y 0 − a d n, n ∈ Z } . 2
Uploaded by DeaconDuck3251 on coursehero.com