Home » Integers

Tag: Integers

Prove some statements about even and odd integers

We define even and odd as follows: an integer n is even if n = 2m for some integer m, and n is odd if n+1 is even. An immediate consequence of the definition, which we will feel free to use, is that an integer n is odd if and only if n = 2k+1 for some integer k.

  1. Prove than an integer cannot be both even and odd.
  2. Prove that every integer is either even or odd.
  3. Prove that the set of even integers is closed under sums and products. What can be said about sums and products of odd integers?
  4. Prove that if n^2 is even, n must be even as well. Prove also that for integers a and b, if a^2 = 2b^2, then both a and b must be even.
  5. Prove that every rational number can be written as the ratio of integers a and b at least one of which is odd.

  1. Proof. Suppose otherwise, that there is some n \in \mathbb{Z} that is both even and odd. Then, there exist a,b \in \mathbb{Z} such that n = 2a and n = 2b-1 (since n is odd, n+1 is even, so n+1 = 2b). Hence,

        \[ 2a = 2b-1 \implies 2(b-a) = 1 \implies b-a = \frac{1}{2}. \]

    But \frac{1}{2} \notin \mathbb{Z}, contradicting the fact that the integers are closed under addition (and subtraction). \qquad \blacksquare

  2. Proof. Let n be an arbitrary integer. Then, \frac{n}{2} is a real number, so by I.3.12, Exercise #4 we know there exists m \in \mathbb{Z} such that

        \[  m \leq \frac{n}{2} < m+1 \quad \implies \quad 2m \leq n < 2m+2. \]

    If 2m = n, then n is even and we are done.
    Otherwise, if 2m \neq n, then we have

        \[ 2m < n < 2m+2. \]

    But this implies n = 2m + 1 since 2m+1 is the only integer in the interval. Thus, n is odd.
    Hence, every integer is either even or odd. \qquad \blacksquare

  3. Proof. Let m,n be even integers. Then, there exist integers j and k such that m = 2j, n = 2k. Then,

        \begin{align*}   m+n &= 2j+2k & m\cdot n &= (2j) \cdot (2k) \\   &= 2(j+k) & &= 2(2jk) \\   &= 2a & & = 2b \end{align*}

    where a and b are integers. Hence, m+n and m \cdot n are both even. \qquad \blacksquare

    Next, we claim the sum of two odd integers is even, and the product of two odd integers is odd.
    Proof. Let m,n be odd integers. Then there exist integers j and k such that m = 2j+1 and n = 2k+1. Then,

        \begin{align*}   m + n &= 2j+1 + 2k +1 & m \cdot n &= (2j+1)(2k+1) \\   &= 2j+2k+2 & &= 4jk + 2j + 2k + 1 \\   &= 2(j+k+1) & & = 2(2jk + j + k) + 1 \end{align*}

    Hence, m+n = 2a for some integer a and mn = 2b + 1 for some integer b. Therefore, m+n is even and mn is odd, as claimed. \qquad \blacksquare

  4. Proof. Let n \in \mathbb{Z} with n^2 even. Since n^2 = n \cdot n and we know from part (b) that n must be either even or odd and from part (a) that it cannot be both. By part (c) the product of two even integers even, while the product of two odd integers is odd; hence, we must have n even (otherwise n \cdot n would be the product of two odd integers and would have to be odd).

    Next, if a and b are integers with a^2 = 2b^2, then a^2 is even by definition (since it equals 2j for some integer j). So, by the above we know a is even, say a = 2k. Then a^2 = (2k)^2 = 4k^2 = 2(2k^2). But then we have,

        \[ 2b^2 = 2(2k^2) \quad \implies \quad b^2 = 2k^2 \]

    and by the same reasoning that lead to a even, we also have b must be even. Thus, both a and b are even. \qquad \blacksquare

  5. Proof. Let r be a rational number with r = \frac{a}{b}. If a and b are both even, then we have

        \[ a = 2c \text{ and } b = 2d \qquad \implies \quad \frac{a}{b} = \frac{2c}{2d} = \frac{c}{d}, \]

    with c < a, and d < b. Now, if c and d are both even, repeat the process. This will give a strictly decreasing sequence of positive integers, so the process must terminate by the well-ordering principle (see I.4.3, p. 34 in Apostol, Calculus, Volume I ). Thus, we must have some integers r and s, not both even with n = \frac{a}{b} = \frac{r}{s}. This was the requested property. \qquad \blacksquare