Survey

* Your assessment is very important for improving the workof artificial intelligence, which forms the content of this project

Survey

Document related concepts

no text concepts found

Transcript

Theorem: Let x and y be integers. (𝑥 + 1) ∗ 𝑦 2 is even if and only if 𝑥 is odd or 𝑦 is even. Proof: Assume that x and y are integers. First we will prove that if (𝑥 + 1) ∗ 𝑦 2 is even, then 𝑥 is odd or 𝑦 is even. We will prove this by proving its contrapositive. The contrapositive states that if x is even and y is odd, then (𝑥 + 1) ∗ 𝑦 2 is odd. So, assume that x is even and y is odd. This means there exist integers m and n such that, 𝑥 = 2𝑚 and 𝑦 = 2𝑛 + 1. By substitution, (𝑥 + 1)𝑦 2 = (2𝑚 + 1)(2𝑛 + 1)2 = (2𝑚 + 1)(4𝑛2 + 4𝑛 + 1) = 8𝑚𝑛2 + 8𝑚𝑛 + 2𝑚 + 4𝑛2 + 4𝑛 + 1 = 2(4𝑚𝑛2 + 4𝑚𝑛 + 𝑚 + 2𝑛2 + 2𝑛) + 1. Note that (4𝑚𝑛2 + 4𝑚𝑛 + 𝑚 + 2𝑛2 + 2𝑛) is an integer and thus, (𝑥 + 1)𝑦 2 is an odd integer. Therefore, if (𝑥 + 1)𝑦 2 is even, then x is odd or y is even. Now we will prove that if x is odd or y is even, then (𝑥 + 1)𝑦 2 is even. We will prove this using cases. For the first case, assume that x is odd. This means there exists some integer m such that 𝑥 = 2𝑚 + 1. By substitution, (𝑥 + 1)𝑦 2 = (2𝑚 + 1 + 1)𝑦 2 = 2𝑚𝑦 2 + 2𝑦 2 = 2(𝑚𝑦 2 + 𝑦 2 ). Note that 𝑚𝑦 2 + 𝑦 2 is an integer and thus, (𝑥 + 1)𝑦 2 is even. For the next case we will assume that y is even. This means there exists some integer n such that, 𝑦 = 2𝑛. By substitution, (𝑥 + 1)𝑦 2 = (𝑥 + 1)(2𝑛)2 = (𝑥 + 1)(4𝑛2 ) = 4𝑥𝑛2 + 4𝑛2 = 2(2𝑥𝑛2 + 2𝑛2 ). Note that 2𝑥𝑛2 + 2𝑛2 is an integer and thus (𝑥 + 1)𝑦 2 is even. Therefore, (𝑥 + 1)𝑦 2 is even if and only if x is odd or y is even, for all integers x and y. QED. Proposition: For all integers a and b, (a + b)3 a3 + b3 (mod 3). Proof: Let a and b be integers. There exists an integer g such that (𝑎3 + 𝑏 3 ) + 3𝑔 = (𝑎 + 𝑏)3 , by the definition of cogruence = (𝑎2 + 2𝑎𝑏 + 𝑏 2 )(𝑎 + 𝑏) = 𝑎3 + 𝑏 3 + 2𝑎2 𝑏 + 2𝑎𝑏 2 + 𝑎𝑏 2 + 𝑎2 𝑏. By simplifying the other side of the equation we get 3𝑔 = (𝑎 + 𝑏)3 − (𝑎3 + 𝑏 3 ) = 2𝑎2 𝑏 + 2𝑎𝑏 2 + 𝑎𝑏 2 + 𝑎2 𝑏 = 𝑎2 (2𝑏 + 𝑏) + 𝑏 2 (2𝑎 + 𝑎) = 𝑎2 𝑏(2 + 1) + 𝑏 2 𝑎(2 + 1) = 3(𝑎2 𝑏) + 3(𝑏 2 𝑎). Let 𝑠 = 𝑎2 𝑏 and 𝑦 = 𝑏 2 𝑎, and note that s and y are integers by closure. Using substitution we obtain, 3𝑔 = 3𝑠 + 3𝑦. We know that any number multiplied by itself must be divisible by itself, so the equation above follows (a + b)3 a3 + b3 (mod 3). Thus, we have proven that for all integers a and b, (a + b)3 a3 + b3 (mod 3). Theorem. For all real numbers x and y, |𝑥 − 𝑦| = |𝑦 − 𝑥|. Proof: Suppose x and y are real numbers. Let 𝑎 = 𝑥 − 𝑦. We will prove by cases. Case 1: Suppose 𝑎 ≥ 0. By the definition of absolute value, |𝑎| = 𝑎, so |𝑥 − 𝑦| = 𝑥 − 𝑦. Also, |−𝑎| = −(−𝑎) = 𝑎, so |𝑦 − 𝑥| = 𝑥 − 𝑦. Thus |𝑎| = |−𝑎| and |𝑥 − 𝑦| = |𝑦 − 𝑥|. Case 2: Suppose 𝑎 < 0. By the definition of absolute value, |𝑎| = −𝑎, so |𝑥 − 𝑦| = 𝑦 − 𝑥. Also, |−𝑎| = −𝑎 since 𝑎 < 0, so |𝑦 − 𝑥| = 𝑦 − 𝑥. Thus |𝑎| = |−𝑎| and |𝑥 − 𝑦| = |𝑦 − 𝑥|. So |𝑥 − 𝑦| = |𝑦 − 𝑥| for all real numbers x and y. Prove: Let a and b be integers with 𝑎 ≠ 0. If a does not divide b, then the equation 𝑎𝑥 3 + 𝑏𝑥 + (𝑏 + 𝑎) = 0 does not have a solution that is a natural number. Proof: Let a and b be integers with 𝑎 ≠ 0. We will show this by proving the contrapositive. Contrapositive: If the equation 𝑎𝑥 3 + 𝑏𝑥 + (𝑏 + 𝑎) = 0 has a natural number solution, then a divides b. Let x be a natural number solution of 𝑎𝑥 3 + 𝑏𝑥 + (𝑏 + 𝑎) = 0. By rearranging the equation, we obtain 𝑎𝑥 3 + 𝑏𝑥 + (𝑏 + 𝑎) = 0 𝑏𝑥 + 𝑏 = −𝑎𝑥 3 − 𝑎 𝑏(𝑥 + 1) = 𝑎(−𝑥 3 − 1) −𝑥 3 −1 𝑏 = 𝑎( 𝑥+1 ). Since 𝑛 ∈ ℕ, 𝑥 + 1 ≠ 0 so we can divide both sides by 𝑥 + 1 to obtain 𝑏 = 𝑎(−𝑥 2 + 𝑥 − 1). Note that (−𝑥 2 + 𝑥 − 1) ∈ ℤ by closure. Thus, a divides b by the definition of divides. So, we have shown that the contrapositive is true. Thus, if a does not divide b, then the equation 𝑎𝑥 3 + 𝑏𝑥 + (𝑏 + 𝑎) = 0 does not have a solution that is a natural number. ■

Related documents