$$\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 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 3.3: Divisibility rules revisited

• • Contributed by Pamini Thangarajah
• Professor (Mathematics & Computing) at Mount Royal University
$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\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 \|}$$ $$\newcommand{\inner}{\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 \|}$$ $$\newcommand{\inner}{\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: