Let us divide the odd positive integers into two arithmetic progressions; the red numbers are 1,...

Let us divide the odd positive integers into two arithmetic progressions; the red numbers are 1, 5, 9, 13, 17, 21, ... The blue numbers are 3, 7, 11, 15, 19, 23,....

(a) Prove that the product of two red numbers is red, and that the product of two blue numbers is red.

(b) Prove that every blue number has a blue prime factor.

(c) Prove that there are infinitely many blue prime numbers. Hint: Follow Euclid’s proof, but multiply a list together, multiply the result by four, then subtract one.

Expert Solution

Colby Messinger answered 2 years ago

Let Dn be the set of positive integers that divide evenly into n. List the elements...

Let Dn be the set of positive integers that divide evenly into n. List the elements of each of the sets D6, D16, D12, and D30

Let A[1..n] be an array of distinct positive integers, and let t be a positive integer....

Let A[1..n] be an array of distinct positive integers, and let t be a positive integer. (a) Assuming that A is sorted, show that in O(n) time it can be decided if A contains two distinct elements x and y such that x + y = t. (b) Use part (a) to show that the following problem, re- ferred to as the 3-Sum problem, can be solved in O(n2) time: 3-Sum Given an array A[1..n] of distinct positive integers, and...

Prove the following statements! 1. There is a bijection from the positive odd numbers to the...

Prove the following statements! 1. There is a bijection from the positive odd numbers to the integers divisible by 3. 2. There is an injection f : Q→N. 3. If f : N→R is a function, then it is not surjective.

Let us choose seven arbitrary distinct positive integers, not exceeding 24. Show that there will be...

Let us choose seven arbitrary distinct positive integers, not exceeding 24. Show that there will be at least two subsets chosen from these seven numbers with equal total sums. (Keep in mind that sets, and hence subsets, have no repeated elements.) Hint: How many subsets can you form altogether? What is the largest total sum of such a subset?

Prove that the following is true for all positive integers n: n is odd if and...

Prove that the following is true for all positive integers n: n is odd if and only if n2 is odd.

7. Let m be a fixed positive integer. (a) Prove that no two among the integers...

7. Let m be a fixed positive integer. (a) Prove that no two among the integers 0, 1, 2, . . . , m − 1 are congruent to each other modulo m. (b) Prove that every integer is congruent modulo m to one of 0, 1, 2, . . . , m − 1.

(a) Use a direct proof to show that the product of two odd numbers is odd....

(a) Use a direct proof to show that the product of two odd numbers is odd. (b) Prove that there are no solutions in integers x and y to the equation 2x2 + 5y2 = 14. (c) Prove that the square of an even number is an even number using (a) direct proof, (b) an indirect proof, and (c) a proof by contradiction. Q. 2. Maximum score = 25 (parts (a) 9 points, part (b-i) and (b-ii) 8 points) (a)...

Let a1 ≥ a2, . . . , an be a sequence of positive integers whose...

Let a1 ≥ a2, . . . , an be a sequence of positive integers whose sum is 2n − 2. Prove that there exists a tree T on n vertices whose vertices have degrees a1, a2, . . . , an. Sketch of solution: Prove that there exist i and j such that ai = 1 and aj ≥ 2. Remove ai, subtract 1 from aj and induct on n.

Let u and v be two integers and let us assume u^2 + uv +v^2 is...

Let u and v be two integers and let us assume u^2 + uv +v^2 is divisible by 9. Show that then u and v are divisible by 3. (please do this by contrapositive).

Let a and b be positive integers, and let d be their greatest common divisor. Prove...

Let a and b be positive integers, and let d be their greatest common divisor. Prove that there are infinitely many integers x and y such that ax+by = d. Next, given one particular solution x0 and y0 of this equation, show how to find all the solutions.

Question