Skip to main content
\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Mathematics LibreTexts

3.3: Divisibility rules revisited

  • Page ID
    7628
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    Thinking out Loud

    Can any integer \(n\) be written as a sum of distinct powers of \(2\)?

    Example \(\PageIndex{1}\):

    Express \(2019\) as a sum of distinct powers of \(2\)?

    Note that, \(10 \equiv 1 ( mod 3), 10 \equiv 1 ( mod 9),\) and \(10 \equiv (-1)( mod 11),\).

    Let \(x \in \mathbb{Z_+}\).

    Then \[ x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0,\]

    which implies

    \[x= 10( d_n10^{n-1} +d_{n-1}10^{n-2}+ \cdots+ d_2 10+d_1)+d_0.\]

    Thus we can express \(x\) as \(10 a+b\), where \(b=d_0\) is the ones digit of \(x\), and \(a= d_n10^{n-1} +d_{n-1}10^{n-2}+ \cdots+ d_2 10+d_1\).

    Divisibility by \(2=2^1:\)

    Let \( x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0\in \mathbb{Z_+}\), then \(2 \mid x\) iff \(2 \mid d_0\). In other words, \(2\) divides an integer iff the ones digit of the integer is either \(0, 2, 4, 6,\) or \( 8\). That is. \(x \equiv 0 (mod 2) \) iff \(d_0 \equiv 0 (mod 2)\).

    Proof:

    Since \( 10 \equiv 0 (mod 2) \) and  \(x=10 a+b\), \(x \equiv 0 (mod 2) \) iff \(d_0 \equiv 0 (mod 2)\).\(\Box\)

    Divisibility by \(5:\)

    Let \( x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0\in \mathbb{Z_+}\), then \(5 \mid x\) iff \(5 \mid b\). In other words, \(5\) divides an integer iff the ones digit of the integer is either \(0,\) or \( 5\). 

    That is. \(x \equiv 0 (mod 5) \) iff \(d_0 \equiv 0 (mod 5)\).

    Proof:

    Since \( 10 \equiv 0 (mod 5) \) and  \(x=10 a+b\), \(x \equiv 0 (mod 5) \) iff \(d_0 \equiv 0 (mod 5)\).\(\Box\)

    Divisibility by \(10:\)

    Let \( x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0\in \mathbb{Z_+}\), then \(10 \mid x\) iff \(10 \mid b\). In other words, \(10\) divides an integer iff the ones digit of the integer is \(0,\).

    That is. \(x \equiv 0 (mod 10) \) iff \(d_0 \equiv 0 (mod 10)\).

    Proof:

    Since \( 10 \equiv 0 (mod 10) \) and  \(x=10 a+b\), \(x \equiv 0 (mod 10) \) iff \(d_0 \equiv 0 (mod 10)\).\(\Box\)

    Divisibility by \(4=2^2:\)

    Let \( x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0\in \mathbb{Z_+}\), then \(4 \mid x\) iff \( 4 \mid d_1d_0\). That is. \(x \equiv 0 (mod 4) \) iff \(d_1d_0 \equiv 0 (mod 4)\).

    Proof:

    Let \(x\) be an integer. Then

    \( x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0\), which implies

    \(x= 100( d_n10^{n-2} +d_{n-1}10^{n-3}+ \cdots+ d_2)+ 10d_1+d_0\)=100( d_n10^{n-2} +d_{n-1}10^{n-3}+ \cdots+ d_2)+ d_1d_0\).

    Since \( 100 \equiv 0 (mod 4)\) , \(x=100 a+ d_1d_0\), \(x \equiv 0 (mod 4) \) iff \(d_1d_0 \equiv 0 (mod 4)\).\(\Box\)

    Divisibility by \(8=2^3:\)

    Let \( x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0\in \mathbb{Z_+}\), then \(8 \mid x\) iff \( 8 \mid d_2d_1d_0\). That is. \(x \equiv 0 (mod 8) \) iff \(d_2d_1d_0 \equiv 0 (mod 10)\).

    Proof:

    Let \(x\) be an integer. Then

    \( x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0\), which implies

    \(x= 10^3( d_n10^{n-3} +d_{n-1}10^{n-4}+ \cdots+ d_3)+ 100d_2+10d_1+d_0\)=10^3( d_n10^{n-3} +d_{n-1}10^{n-4}+ \cdots+ d_3)+ d_2d_1d_0\).

    Since \( 1000 \equiv 0 (mod 8)\) , \(x=1000 a+ d_2d_1d_0\), \(x \equiv 0 (mod 8) \) iff \(d_2d_1d_0 \equiv 0 (mod 8)\).\(\Box\)

    A similar argument can be made for divisibility by \(2^n\), for any positive integer \(n\). The following reluts follows from the fact that,

    \( x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0 =  d_n(10^n-1) +d_{n-1}(10^{n-1}-1)+ \cdots+ d_2 (10^2-1)+d_1(10^1-1)+ (d_n+d_{n-1}+ \cdots+ d_1+ d_0)\). 

    Divisibility by \(3:\)

    Let \( x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0\in \mathbb{Z_+}\), then \(3 \mid x\) iff \(3\) divides sum of its digits.

    Proof:

    Let \(x\) be an integer. Then

    \( x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0\), which implies \(x=  d_n(10^n-1) +d_{n-1}(10^{n-1}-1)+ \cdots+ d_2 (10^2-1)+d_1(10^1-1)+ (d_n+d_{n-1}+ \cdots+ d_1+ d_0)\).

    Divisibility by \(9=3^2:\)

    Let \( x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0\in \mathbb{Z_+}\), then \(9 \mid x\) iff \(9\) divides sum of its digits.

    Proof:

    Let \(x\) be an integer. Then

    \( x= d_n10^n +d_{n-1}10^{n-1}+ \cdots+ d_2 10^2+d_110^1+d_0\), which implies \(x=  d_n(10^n-1) +d_{n-1}(10^{n-1}-1)+ \cdots+ d_2 (10^2-1)+d_1(10^1-1)+ (d_n+d_{n-1}+ \cdots+ d_1+ d_0)\).

    Divisibility by \(7:\)

    \(7 \mid x\) iff \(7\) divides the absolute difference between \(a-2b\), where \(x=10 a+b\), where \(b=d_0\) is the ones digit of \(x\), and \(a= d_n10^{n-1} +d_{n-1}10^{n-2}+ \cdots+ d_2 10+d_1\).

    Proof:

    Divisibility by \(11:\)

    \(11 \mid x\) iff \(11\) divides the absolute difference between alternate sum.

    Proof: