Ex 3. Consider the following definitions: Definition: Let a and b be integers. A linear combination...

Ex 3. Consider the following definitions:

Definition: Let a and b be integers. A linear combination of a and b is an expression of the form ax + by, where x and y are also integers. Note that a linear combination of a and b is also an integer.

Definition: Given two integers a and b we say that a divides b, and we write a|b, if there exists an integer k such that b = ka. Moreover, we write a - b if a does not divide b.

For each proof state clearly which technique you used (direct proof, proof by contrapositive, proof by contradiction). Even if you are not able to prove some of the following claims, you can still use them in the proof of the following ones, if needed.

(a) Given the above definition, is it true that a|0 for all a in Z? Is it true that 0|a for all a in Z? Is it true that a|a for all a in Z? Explain your answers.

(b) Prove that if a and b are two integers such that b≠0 and a|b, then |a| ≤ |b|.

(d) Let a be a natural number and b be an integer. If a|(b + 1) and a|(b − 1), then a = 1 or a = 2. (Hint: you may use a clever linear combination...)

(e) Prove that if a and b are two integers with a ≥ 2, then a - b or a - b + 1

Solutions

Expert Solution

Colby Messinger answered 7 months ago

Next > < Previous

Related Solutions

Let a and b be integers and consider (a) and (b) the ideals they generate. Describe...

Let a and b be integers and consider (a) and (b) the ideals they generate. Describe the intersection of (a) and (b), the product of (a) and (b), the sum of (a) and (b) and the Ideal quotient (aZ:bZ).

a.) Prove the following: Lemma. Let a and b be integers. If both a and b...

a.) Prove the following: Lemma. Let a and b be integers. If both a and b have the form 4k+1 (where k is an integer), then ab also has the form 4k+1. b.)The lemma from part a generalizes two products of integers of the form 4k+1. State and prove the generalized lemma. c.) Prove that any natural number of the form 4k+3 has a prime factor of the form 4k+3.

3. (4 marks) Let a and b be positive integers. Is gcd(5a + b, 11a +...

3. Let a and b be positive integers. Is gcd(5a + b, 11a + 2b) = gcd(2a + b, 3a + 2b)? If yes provide a proof. If not, provide a counterexample.

Let A be a subset of the integers. (a) Write a careful definition (using quantifiers) for...

Let A be a subset of the integers. (a) Write a careful definition (using quantifiers) for the term smallest element of A. (b) Let E be the set of even integers; that is E = {x ∈ Z : 2|x}. Prove by contradiction that E has no smallest element. (c) Prove that if A ⊆ Z has a smallest element, then it must be unique.

Problem Definition: Problem: Given an array of integers print all pairs of integers a and b...

Problem Definition: Problem: Given an array of integers print all pairs of integers a and b where a + b is equal to a given number. For example, consider the following array and suppose we want to find all pairs of integers a and b where a + b = 16 A= [ 10, 4, 6, 15, 3, 5, 1, 13] The following are pairs that sum to 16: 13, 3 6, 10 15, 1 Your program should print these...

Topic: Linear combination of random variables Let X1, X2, . . . , X16 be 16...

Topic: Linear combination of random variables Let X1, X2, . . . , X16 be 16 independent variables identically distributed as N(2, 4), with an average X̄(Note: This is X bar, It was formatted as X¯ before but I assumed X̄ is more clear in text ) . Find the value c for which P(2 − c ≤ X̄ ≤ 2 + c) = 0.99. Please show work and relevant formula's Thanks.

Consider the four definitions of information presented in this chapter. The problem with the first definition,...

Consider the four definitions of information presented in this chapter. The problem with the first definition, “knowledge derived from data,” is that it merely substitutes one word we don’t know the meaning of (information) for a second word we don’t know the meaning of (knowledge). The problem with the second definition, “data presented in a meaningful context,” is that it is too subjective. Whose context? What makes a context meaningful? The third definition, “data processed by summing, ordering, averaging, etc.,”...

Let a and b be integers. Recall that a pair of Bezout coefficients for a and...

Let a and b be integers. Recall that a pair of Bezout coefficients for a and b is a pair of integers m, n ∈ Z such that ma + nb = (a, b). Prove that, for any fixed pair of integers a and b, there are infinitely many pairs of Bezout coefficients.

Let a and b be integers which are not both zero. (a) If c is an...

Let a and b be integers which are not both zero. (a) If c is an integer such that there exist integers x and y with ax+by = c, prove that gcd(a, b) | c. (b) If there exist integers x and y such that ax + by = 1, explain why gcd(a, b) = 1. (c) Let d = gcd(a,b), and write a = da′ and b = db′ for some a′,b′ ∈ Z. Prove that gcd(a′,b′) = 1.

Let a,b be an element in the integers with a greater or equal to 1. Then...

Let a,b be an element in the integers with a greater or equal to 1. Then there exist unique q, r in the integers such that b=aq+r where z less than or equal r less than or equal a+(z-1). Prove the Theorem.

Subjects