Exercises - Divisibility

$\require{AMSsymbols}$

  1. What can you conclude if $a$ and $b$ are nonzero integers such that $a \mid b$ and $b \mid a$?

  2. Are there integers $a$, $b$, and $c$ such that $a \mid bc$, but $a \nmid b$ and $a \nmid c$? What can you say about the nature of such integers $a$ if they exist?

  3. Show that if $a$, $b$, and $c \neq 0$ are integers, then $a \mid b$ if and only if $ac \mid bc$

  4. Show that if $a$ and $b$ are integers such that $a \mid b$, then $a^n \mid b^n$ for every positive integer $n$  

    If $a$ and $b$ are integers such that $a \mid b$, then $b = ak_1$ for some integer $k_1$. Now, raising both sides to the $n^\textrm{th}$ power, we have $$\begin{align}b^n &= (ak_1)^n\\ &= a^n {k_1}^n\end{align}$$ However, ${k_1}^n$ must be an integer due to the closure of the integers under multiplication. So, defining $k_2 = {k_1}^n$, we see that $b^n = a^n k_2$ for some integer $k_2$. Hence, $a^n \mid b^n$.

  5. Show that if $a \mid b$ and $a \mid c$, then $a \mid (bx + cy) \quad \forall x,y \in \mathbb{Z}$

  6. An "even" number is a number of the form $2n$, where $n$ is an integer. An "odd" number is one of the form $2n+1$, where $n$ is an integer. Show that the sum of two even or two odd numbers is even, the sum of an odd and an even integer is odd, and the product of two odd numbers is odd.  

    Part I.
    Let $a$ and $b$ be even numbers. As such, $a=2n_1$ and $b=2n_2$ for some integers $n_1$ and $n_2$. Now consider their sum: $$\begin{align}a+b &= 2n_1 + 2n_2 \\&= 2 (n_1 + n_2)\end{align}$$ We know that $(n_1 + n_2)$ must be an integer due to the closure of the integers under addition. So, defining $n_3 = n_1 + n_2$, we see that the sum $a+b$ can be written as $2n_3$ for some integer $n_3$, making it an even number. Hence, the sum of two even numbers is even.

    Part II.
    Now let $a$ and $b$ be odd numbers. As such, $a=2n_1+1$ and $b=2n_2+1$ for some integers $n_1$ and $n_2$. Now consider their sum: $$\begin{align}a+b &= (2n_1 + 1) + (2n_2 + 1) \\ &= 2n_1 + 2n_2 + 2\\ &= 2(n_1 + n_2 + 1)\end{align}$$ We know that $(n_1 + n_2 + 1)$ must be an integer due to the closure of the integers under addition. So defining $n_3 = n_1 + n_2 + 1$, we see that the sum $a+b$ can be written as $2n_3$ for some integer $n_3$, making it an even number. Hence, the sum of two odd numbers is even.

    Part III.
    Now let $a$ be odd and $b$ be even. As such, $a=2n_1+1$ and $b=2n_2$ for some integers $n_1$ and $n_2$. Now consider their sum: $$\begin{align}a+b &= (2n_1 + 1)+ 2n_2 \\ &= 2n_1 + 2n_2 + 1\\ &= 2(n_1 + n_2) + 1\end{align}$$ We know that $(n_1 + n_2)$ must be an integer due to the closure of the integers under addition. So defining $n_3 = n_1 + n_2$, we see that the sum $a+b$ can be written as $2n_3+1$ for some integer $n_3$, making it an odd number. Hence, the sum of an even and an odd integer is odd.

    Part IV.
    Now let $a$ and $b$ be odd numbers. As such, $a=2n_1 + 1$ and $b=2n_2+1$ for some integers $n_1$ and $n_2$. Now consider their product: $$\begin{align} ab &= (2n_1 + 1)(2n_2 + 1) \\ &= 4n_1 n_2 + 2n_1 + 2n_2 + 1 \\ &= 2(2n_1 n_2 + n_1 + n_2) + 1\end{align}$$ We know that $(2n_1 n_2 + n_1 + n_2)$ must be an integer due to the closure of the integers under addition and multiplication. So defining $n_3 = (2n_1 + n_1 + n_2)$, we see that the product $ab$ can be written as $2n_3+1$ for some integer $n_3$, making it an odd number. Hence, the product of two odd numbers is odd.

  7. Prove that the product of two integers of the form $4k+1$ is again of this form, while the product of two integers of the form $4k+3$ is of the form $4k+1$.  

    Part I.
    Suppose $a = 4k_1+1$ and $b=4k_2+1$ for some integers $k_1$ and $k_2$. Consider their product: $$\begin{align}ab &= (4k_1+1)(4k_2+1)\\ &= 16k_1 k_2 + 4k_1 + 4k_2 + 1\\ &= 4(4k_1 k_2 + k_1 + k_2) + 1\end{align}$$ We know that $(4k_1 k_2 + k_1 + k_2)$ must be an integer due to the closure of the integers under addition and multiplication. So defining $k_3 = (4k_1 k_2 + k_1 + k_2)$, we see that the product $ab$ can be written as $4k_3 + 1$ for some integer $k_3$. Thus, the product of two integers of the form $4k+1$ is again of this form.

    Part II.
    Suppose $a = 4k_1+3$ and $b=4k_2+3$ for some integers $k_1$ and $k_2$. Consider their product: $$\begin{align}ab &= (4k_1+3)(4k_2+3)\\ &= 16k_1 k_2 + 12k_1 + 12k_2 + 9\\ &= 16k_1 k_2 + 12k_1 + 12k_2 + 8 + 1\\ &= 4(4k_1 k_2 + 3k_1 + 3k_2 + 2) + 1\end{align}$$ We know that $(4k_1 k_2 + 3k_1 + 3k_2 + 2)$ must be an integer due to the closure of the integers under addition and multiplication. So defining $k_3 = 4k_1 k_2 + 3k_1 + 3k_2 + 2$, we see that the product $ab$ can be written as $4k_3+1$ for some integer $k_3$. Thus, the product of two integers of the form $4k+3$ is of the form $4k+1$.

  8. Prove that no integer in the following sequence is a perfect square: $$11, 111, 1111, 11111, \ldots$$

  9. Show that the square of every odd integer is of the form $8n+1$ and the fourth power of every odd integer is of the form $16k+1$    

    Part I.
    Let $a$ be an odd integer. Then $a=2k_1+1$ for some integer $k_1$. Consider the square of $a$: $$\begin{align}a^2 &= (2k_1 + 1)^2\\ &= 4{k_1}^2 + 4k_1 + 1\\ &= 4({k_1}^2 + k_1) + 1\end{align}$$ So, certainly the square of an odd integer is of the form $4k+1$, but we hoped this to be of the form $8k+1$. If we can argue that $({k_1}^2 + k_1)$ must be even, that would give us the additional factor of two that we need.

    Notice, $k_1$ must either be even or odd.

    In the first case, when $k_1$ is even, notice that ${k_1}^2$ must also be even, making ${k_1}^2+k_1$ the sum of two even numbers, which must be even.

    In the second case, when $k_1$ is odd, notice that ${k_1}^2$ must also be odd, making ${k_1}^2+k_1$ the sum of two odd numbers, which must be even.

    In both cases, ${k_1}^2+k_1$ is even, and hence, we can find some integer $k_2$ so that ${k_1}^2+k_1 = 2k_2$.

    Now, picking up where we left off above, we have: $$\begin{align}a^2 &= 4({k_1}^2 + k_1) + 1\\ &= 4(2k_2)+1\\ &= 8k_2 + 1\end{align}$$ Thus, the square of every odd integer is of the form $8k+1$.

    Part II.
    Now consider the fourth power of this odd integer $a$. Note, we have already determined above that $a^2 =8k_2+1$ for some integer $k_2$. So, $$\begin{align}a^4 &= (a^2)^2\\ &= (8k_2 + 1)^2\\ &= 64{k_2}^2 + 16k_2 + 1\\ &= 16(4{k_2}^2 + k_2) + 1\end{align}$$ We know that $(4{k_2}^2 + k_2)$ must be an integer due to the closure of the integers under addition and multiplication. So, defining $k_3 = 4{k_2}^2 + k_2$, we see that $a^4$ can be written as $16k_3 + 1$. Thus, the fourth power of every odd integer is of the form $16k+1$.

  10. Show that the product of two integers of the form $6k+5$ is of the form $6k+1$.  

    Suppose $a=6k_1+5$ and $b=6k_2+5$ for some integers $k_1$ and $k_2$. Consider their product, $ab$: $$\begin{align}ab &= (6k_1+5)(6k_2+5)\\ &= 36k_1 k_2 + 30k_1 + 30k_2 + 25\\ &= 36k_1 k_2 + 30k_1 + 30k_2 + 24 + 1\\ &= 6(6k_1 k_2 + 5k_1 + 5k_2 + 4) + 1\end{align}$$ We know that $(6k_1 k_2 + 5k_1 + 5k_2 + 4)$ must be an integer due to the closure of integers under addition and multiplication. So, defining $k_3 = 6k_1 k_2 + 5k_1 + 5k_2 + 4$, we see that $ab$ can be written as $6k_3+1$. Thus, the product of two integers of the form $6k+5$ is of the form $6k+1$.

  11. Show that if $a$ is an integer, then 3 divides $a^3-a$.  

    Consider the factorization below: $$\begin{align}a^3-a &= a(a^2-1)\\ &= a(a+1)(a-1)\\ &= (a-1) \cdot a \cdot (a+1)\end{align}$$ Note, when written in this last form, it is easy to see that when $a$ is an integer, $a^3-a$ is the product of three consecutive integers. One of these three integers must be divisible by 3, which then makes their product divisible by 3. More precisely:

    • If $a$ divided by 3 leaves a remainder of 0, then $3 \mid a$.
    • If $a$ divided by 3 leaves a remainder of 1, then $3 \mid a - 1$.
    • If $a$ divided by 3 leaves a remainder of 2, then $3 \mid a + 1$.

    These are the only possible remainders that can be left upon division by 3. As such, regardless of the value of the integer $a$, 3 always divides one of the factors in $a(a-1)(a+1)$, and hence, $3 \mid a^3 - a$ for any integer $a$.

  12. Prove that the product of any three consecutive integers is divisible by 6.  

    Consider three consecutive integers: $n$, $n+1$, and $n+2$. We wish to show that their product, $n(n+1)(n+2)$ is divisible by 6. Suppose we break this task into two pieces. It would be sufficient to show that their product is both even and divisible by 3.

    To show that $n(n+1)(n+2)$ is even, note that $n$ itself must be even or odd.

    • If $n$ is even, then $n(n+1)(n+2)$ is the product of two even numbers and an odd number, which must then be even.
    • If $n$ is odd, then $n(n+1)(n+2)$ is the product of two odd numbers and an even number, which again, must be even.

    Thus, regardless of the integer $n$ chosen, $n(n+1)(n+2)$ must be even.

    It remains to show that $n(n+1)(n+2)$ is divisible by 3.

    Consider the possible remainders that can be left when $n$ is divided by 3:

    • If $n$ divided by 3 leaves a remainder of 0, then $3 \mid n$.
    • If $n$ divided by 3 leaves a remainder of 1, then $3 \mid n+2$.
    • If $n$ divided by 3 leaves a remainder of 2, then $3 \mid n+1$.

    In each case, some factor of $n(n+1)(n+2)$ is divisible by 3. As such, regardless of the integer $n$ chosen, $n(n+1)(n+2)$ is divisible by 3.

    We have shown that $n(n+1)(n+2)$ is both even and divisible by 3. Thus, the product of any three consecutive integers is divisible by 6.

  13. Show that if $a$ and $b$ are both odd, then 8 divides $a^2-b^2$.  

    If $a$ and $b$ are both odd, than we can find integers $k_1$ and $k_2$, such that $a = 2k_1 + 1$ and $b = 2k_2 + 1$. As such,

    $$\begin{array}{rcl} a^2 - b^2 &=& (a+b)(a-b)\\\\ &=& ((2k_1 + 1) + (2k_2 + 1))((2k_1 + 1) - (2k_2 + 1))\\\\ &=& (2k_1 + 2k_2 + 2)(2k_1 - 2k_2)\\\\ &=& 4(k_1 + k_2 + 1)(k_1 - k_2) \end{array}$$

    We have established that $4 \mid a^2 - b^2$. We need to find one more factor of $2$ -- that is to say, it remains to show $2 \mid (k_1 + k_2 + 1)(k_1 - k_2)$.

    We argue by cases: If $k_1$ and $k_2$ are both even or both odd, then $(k_1 - k_2)$ will be even. Alternatively, if one is even and the other odd, then $(k_1 + k_2 + 1)$ will be even. In either case, the product $(k_1 + k_2 + 1)(k_1 - k_2)$ must then be even and equal to some $2k_3$ for some integer $k_3$.

    Thus, $a^2 - b^2 = 8k_3$ for some integer $k_3$ -- and consequently, $8 \mid a^2 - b^2$.

    QED.

  14. Show that if $a$ is odd, then 12 divides $a^2 + (a+2)^2 + (a+4)^2 + 1$.  

    We argue directly. If $a$ is odd, then we can find an integer $k$ such that $a = 2k+1$. Consequently,

    $$\begin{array}{rcl} a^2 + (a+2)^2 + (a+4)^2 + 1 &=& (2k+1)^2 + (2k+3)^2 + (2k+5)^2 + 1\\\\ &=& (4k^2 + 4k + 1) + (4k^2 + 12k + 9) + (4k^2 + 20k + 25) + 1\\\\ &=& 12k^2 + 36k + 36\\\\ &=& 12(k^2 + 3k + 3) \end{array}$$

    Observing that $k^2 + 3k + 3$ must be an integer by closure, we have $12 \mid a^2 + (a+2)^2 + (a+4)^2 + 1$.

    QED.

  15. Prove each of the following for a given positive integer $n$:

    1. $5 \mid n$ if and only if the last digit of $n$ is a $0$ or $5$
    2. $9 \mid n$ if and only if the sum of the digits of $n$ is divisible by $9$
    3. $3 \mid n$ if and only if the sum of the digits of $n$ is divisible by $3$

     

    Suppose $n$ has digits $d_n d_{n-1} \cdots d_2 d_1 d_0$.

    1. If we wish to show that $5 \mid n$ if and only if the last digit of $n$ is a $0$ or $5$:

      $$\begin{array}{rcl} n &=& 10^n d_n + 10^{n-1} d_{n-1} + \cdots + 10^2 d_2 + 10 d_1 + d_0\\\\ &=& 10(10^{n-1} d_n + 10^{n-2} d_{n-1} + \cdots + 10 d_2 + d_1) + d_0 \end{array}$$

      Looking at the first term, it is clear that $5$ divides $10(10^{n-1} d_n + 10^{n-2} d_{n-1} + \cdots + 10 d_2 + d_1)$ since $5 \mid 10$. Consequently, $5 \mid n$ if and only if $5$ divides the last term (i.e., $5 \mid d_0$).

      Since a digit (like $d_0$) can only take on the integer values from $0$ to $9$, that leaves only two possibilities. $5 \mid n$ if and only if $d_0$ (the last digit) is a $0$ or a $5$, which is what we hoped to show.

    2. If we wish to show $9 \mid n$ if and only if the sum of the digits of $n$ is divisible by $9$, we again start with

      $$n = 10^n d_n + 10^{n-1} d_{n-1} + \cdots + 10^2 d_2 + 10 d_1 + d_0$$

      The sum of the digits of $n$ is $(d_n + d_{n-1} + \cdots d_2 + d_1 + d_0)$, so let us separate out this piece, and see what is left:

      $$n = (\underbrace{999\cdots9}_{n \textrm{ nines}} d_n + \underbrace{99\cdots9}_{n-1 \textrm{ nines}} d_{n-1} + \cdots + 99 d_2 + 9 d_1) + (d_n + d_{n-1} + \cdots d_2 + d_1 + d_0)$$

      Clearly, $9$ divides the first expression in parentheses -- so if it is to divide the entire expression (and hence $n$), it must also divide the second expression in parentheses, $(d_n + d_{n-1} + \cdots d_2 + d_1 + d_0)$. The reverse holds as well, if $9$ divides the second expression, it will divide the sum of the two expressions, being a common factor. Consequently, $9 \mid n$ if and only if the sum of the digits of $n$ is divisible by $9$, which is what we hoped to show.

    3. This argument is almost identical to the one used in part (b), except that we pull out a factor of $3$...

  16. To find the alternating sum of the digits of a positive integer, we start with zero, and then add the first digit, subtract the second, add the third, subtract the fourth, and so on, alternating between adding and subtracting until we terminate with the last digit of the number. For example, alternating sum of the digits of $12345$ is $1 - 2 + 3 - 4 + 5$. Likewise, the alternating sum of the digits of $9876$ is $9 - 8 + 7 - 6$. Show that a positive integer is divisible by $11$ if and only if its alternating sum is divisible by $11$.

  17. 🔎 Let $a$, $b$, $c$, $d$ be integers. Prove that $12 \mid (a-b)(a-c)(a-d)(b-c)(b-d)(c-d)$

  18. 🔎 Pick 3 digits in some order and form the 6-digit number made by writing them in this same order twice. Prove the result is always divisible by $7$.