Question 1

Use the Euclidean algorithm to ﬁnd the greatest common divisor of 284 and 168. Show your work.

Accepted Answer

The answer of Use the Euclidean algorithm to ﬁnd the...

Question 2

Prove the following statement directly from the deﬁnitions of the terms. Do not use any other
facts previously proved in class or in the text or in the exercises. $\text { For all rational numbers } r \text {, and } s \text {, if } s \neq 0 \text {, then } \frac { 2 r } { 5 s } \text { is a rational number. }$

Accepted Answer

Proof: Suppose $r$ and $s$, are any rational numbers with $s \neq 0$. $/$ We must show that $\frac { 2 r } { 5 s }$ is a rational number./By definition of rational, there exist integers $a , b , c$, and $d$ with $b \neq 0$ and $d \neq 0$ such that
$$r = \frac { a } { b } \quad \text { and } \quad s = \frac { c } { d }$$
In addition, since $c = s \cdot d$ and since neither $s$ nor $d$ equals 0 , then $c \neq 0$ by the zero product property. Then
$$\frac { 2 r } { 5 s } = \frac { 2 \cdot \frac { a } { b } } { 5 \cdot \frac { c } { d } } = \frac { 2 a d } { 5 b c }$$
Now both $2 a d$ and $5 b c$ are integers because they are products of integers, and $5 b c \neq 0$ by the zero product property. Hence $\frac { 2 r } { 5 s }$ is a ratio of integers with a nonzero denominator, and so $\frac { 2 r } { 5 s }$ is a rational number by definition of rational [as was to be shown].

Question 3

State precisely (but concisely) what it means for an integer n to be odd.

Accepted Answer

Some acceptable answers:
a. An integer n is odd if, and only if, n = 2k + 1 for some integer k.
b. An integer n is odd if, and only if, n equals 2 times some integer plus 1.
c. An integer n is odd if, and only if, there exists an integer m such that n = 2m +1 .

Question 4

Outline a proof of the following statement by writing the "starting point" and the "conclusion to be shown" in a proof of the statement. 
$\forall \text { real numbers } r \text { and } s \text {, if } r \text { and } s \text { are rational then } r - s \text { is rational. }$
That is, complete the sentences below. Proof: Suppose______
We must show that__________

Accepted Answer

Proof: Suppose @#LAT-DLM& and @#LAT-DLM&, are any

Question 5

Prove the following statement: The sum of any two consecutive integers can be written in the form 4n + 1 for some integer n.

Accepted Answer

@#LAT-DLM& Suppose @#LAT-DLM& is any integer. By the parity

Question 6

Prove the following statement directly from the deﬁnitions of the terms. Do not use any other facts previously proved in class or in the text or in the exercises. $\text { For all integers } a , b \text {, and } c \text {, if } a \mid b \text { and } a \mid c \text {, then } a \mid ( 5 b + 3 c ) \text {. }$

Accepted Answer

Proof : Suppose @#LAT-DLM&, and @#LAT-DLM& are any integers

Question 7

Prove the following statement: There is no smallest positive rational number.

Accepted Answer

Proof (by contradiction): Suppose not. T

Question 8

$\text { If } m \text { and } n \text { are integers, is } 6 m ^ { 2 } + 34 n - 18 \text { an even integer?}$
Justify your answer

Accepted Answer

No matter what integers replace @#LAT-DLM& and @#LAT-DLM& in

Question 9

Is 56.745 a rational number? Justify your answer.

Accepted Answer

56.745 a r

Question 10

True or false? For any irrational number r, r2 is irrational. Justify your answer.

Accepted Answer

A) True 
 B)False

Question 11

Show that the following statement is false: The product of any two irrational numbers is irrational.

Accepted Answer

@#LAT-DLM&  Then a a

Question 12

State precisely (but concisely) what it means for an integer n to be divisible by an integer d.

Accepted Answer

Some acceptable answers:
a.An integer n

Question 13

Does 12 divide 72? Justify your answer.

Accepted Answer

12 divides

Question 14

Prove the following statement by contradiction: For all real numbers r and s, if r is rational and s is irrational, then r + 2s is irrational.

Accepted Answer

Proof (by contradiction):Suppose not. Th

Question 15

Prove by contradiction that
$4 + 3 \sqrt { 2 } \text { }$  is an irrational number. (You may use the fact that } $\sqrt { 2 }$  is irrational.

Accepted Answer

@#LAT-DLM& Suppose not. That is, suppose that @#LAT-DLM& is

Question 16

State precisely (but concisely) what it means for a number r to be rational.

Accepted Answer

Some acceptable answers: 
a. A real numb

Question 17

Fill in the blanks of the following proof by contradiction that $7 + 4 \sqrt { 2 }$ is an irrational number. (You may use the fact that $\sqrt { 2 }$ is irrational.)
Proof: Suppose not. That is, suppose that $7 + 4 \sqrt { 2 }$ is (i). By definition of rational, $7 + 4 \sqrt { 2 } =$ $\frac { a } { b }$, where (ii). Multiplying both sides by $b$ gives
$$7 b + 4 b \sqrt { 2 } = a ,$$
so if we subtract $7 b$ from both sides we have
$$4 b \sqrt { 2 } = \underline { \text { (iii) } } .$$
Dividing both sides by $4 b$ gives
$$\sqrt { 2 } = \text { (iv). }$$
But then $\sqrt { 2 }$ would be a rational number because (v). This contradicts our knowledge that $\sqrt { 2 }$ is irrational. Hence (vi).

Accepted Answer

(i). rational
(ii). @#LAT-DLM& and @#LAT-DLM& are integers a

Question 18

Prove the following statement directly from the definition of divisibility. Do not use any other facts previously proved in class or in the text or in the exercises.For all integers $a$, and $b$, if $a$ divides $b$ then $a ^ { 3 }$ divides $b ^ { 3 }$.

Accepted Answer

@#LAT-DLM& (Version 1): Suppose @#LAT-DLM& and @#LAT-DLM& are integers

Question 19

Consider the following statement: $\text { Statement A: } \forall \text { integers } m \text { and } n \text {, if } 2 m + n \text { is odd then } m \text { and } n \text { are both odd. }$ 
(a) Write a negation for Statement A.
(b) Disprove Statement A. That is, show that Statement A is false.

Accepted Answer

a. @#LAT-DLM& integers @#LAT-DLM& and @#LAT-DLM& such that @#LAT-DLM& is odd and

Question 20

Consider the following statement: For all integers n, if n3 is even then n is even.
(a) Prove the statement either by contradiction or by contraposition. Clearly indicate which method you are using.
(b) If you used proof by contradiction in part (a), write what you would "suppose" and what you would "show" to prove the statement by contraposition. If you used proof by contraposition. in part (a), write what you would "suppose" and what you would "show" to prove the statement by contradiction.

Accepted Answer

Solution 1:
a. Proof (by contradiction):

Use the Euclidean algorithm to ﬁnd the greatest common divisor of 284 and 168. Show your work.

State precisely (but concisely) what it means for an integer n to be odd.

Prove the following statement: The sum of any two consecutive integers can be written in the form 4n + 1 for some integer n.

Prove the following statement: There is no smallest positive rational number.

$\text { If } m \text { and } n \text { are integers, is } 6 m ^ { 2 } + 34 n - 18 \text { an even integer?}$ Justify your answer

Is 56.745 a rational number? Justify your answer.

True or false? For any irrational number r, r2 is irrational. Justify your answer.

Show that the following statement is false: The product of any two irrational numbers is irrational.

State precisely (but concisely) what it means for an integer n to be divisible by an integer d.

Does 12 divide 72? Justify your answer.

Prove the following statement by contradiction: For all real numbers r and s, if r is rational and s is irrational, then r + 2s is irrational.

Prove by contradiction that $4 + 3 \sqrt { 2 } \text { }$ is an irrational number. (You may use the fact that } $\sqrt { 2 }$ is irrational.

State precisely (but concisely) what it means for a number r to be rational.

Prove the following statement directly from the definition of divisibility. Do not use any other facts previously proved in class or in the text or in the exercises.For all integers $a$ , and $b$ , if $a$ divides $b$ then $a ^ { 3 }$ divides $b ^ { 3 }$ .

Consider the following statement: $\text { Statement A: } \forall \text { integers } m \text { and } n \text {, if } 2 m + n \text { is odd then } m \text { and } n \text { are both odd. }$ (a) Write a negation for Statement A. (b) Disprove Statement A. That is, show that Statement A is false.

Speaking Mathematically

The Logic of Compound Statements

The Logic of Quantified Statements

Sequences, Mathematical Induction, and Recursion

Set Theory

Functions

Relations

Counting and Probability

Graphs and Trees

Analyzing Algorithm Efficiency

Regular Expressions and Finite State Automata

Filters

Exam 4: Elementary Number Theory and Methods of Proof

Use the Euclidean algorithm to ﬁnd the greatest common divisor of 284 and 168. Show your work.

State precisely (but concisely) what it means for an integer n to be odd.

Prove the following statement: The sum of any two consecutive integers can be written in the form 4n + 1 for some integer n.

Prove the following statement: There is no smallest positive rational number.

If m and n are integers, is 6m2+34n−18 an even integer?\text { If } m \text { and } n \text { are integers, is } 6 m ^ { 2 } + 34 n - 18 \text { an even integer?} If m and n are integers, is 6m2+34n−18 an even integer? Justify your answer

Is 56.745 a rational number? Justify your answer.

True or false? For any irrational number r, r2 is irrational. Justify your answer.

Show that the following statement is false: The product of any two irrational numbers is irrational.

State precisely (but concisely) what it means for an integer n to be divisible by an integer d.

Does 12 divide 72? Justify your answer.

Prove the following statement by contradiction: For all real numbers r and s, if r is rational and s is irrational, then r + 2s is irrational.

Prove by contradiction that 4+32 4 + 3 \sqrt { 2 } \text { }4+32​ is an irrational number. (You may use the fact that } 2\sqrt { 2 }2​ is irrational.

State precisely (but concisely) what it means for a number r to be rational.

Prove the following statement directly from the definition of divisibility. Do not use any other facts previously proved in class or in the text or in the exercises.For all integers aaa , and bbb , if aaa divides bbb then a3a ^ { 3 }a3 divides b3b ^ { 3 }b3 .

Speaking Mathematically

The Logic of Compound Statements

The Logic of Quantified Statements

Sequences, Mathematical Induction, and Recursion

Set Theory

Functions

Relations

Counting and Probability

Graphs and Trees

Analyzing Algorithm Efficiency

Regular Expressions and Finite State Automata

Filters

$\text { If } m \text { and } n \text { are integers, is } 6 m ^ { 2 } + 34 n - 18 \text { an even integer?}$ Justify your answer

Prove by contradiction that $4 + 3 \sqrt { 2 } \text { }$ is an irrational number. (You may use the fact that } $\sqrt { 2 }$ is irrational.

Prove the following statement directly from the definition of divisibility. Do not use any other facts previously proved in class or in the text or in the exercises.For all integers $a$ , and $b$ , if $a$ divides $b$ then $a ^ { 3 }$ divides $b ^ { 3 }$ .