# Applications of Congruence (in Number Theory)

We discuss two applications of congruence problems. How to develop a divisibility test, emphasizing theory as well as usability. We then discuss the infamous Days of the Week problem.

## Applications of Congruence – Divisibility Tests

Our first application of congruence is a collection of theorems which help determine divisibility of an integer with another. Divisibility tests for 2, 3, 5, 7, 9, 11, and 13 are given. The divisibility tests for 7, 11, and 13 are nearly the same; and thus lead to a handy way of determining divisibility by 7, 11 and 13 simultaneously. The divisibility tests for powers of 2 and powers of 5 are also nearly the same and importantly, these tests are not recursive. The divisibility tests for 3 and 9 are the same standard tests that are known since childhood. It is possible, through a careful study of the following examples and proofs, to be able to conjecture and prove your own divisibility test.

### Divisibility Test for Powers of 2

Theorem. Let $n=a_ka_{k-1} \cdots a_1 a_0$ be the $k+1$ digits of a positive integer $n$. Then $n$ is divisible by $2^j$ precisely when the integer made up of the last $j$ digits of $n$ is divisible by $2^j.$

Proof. Since $10 \equiv 0 \pmod{2}$ it follows $10^j \equiv 0 \pmod{2^j}$ for any given positive integer $j$. Thus, for $0\leq j\leq k$ \begin{align*} n & = a_k10^k+\cdots +a_j10^j+ a_{j-1}10^{j-1}+\cdots +a_0 \\ & \equiv a_{j-1} \cdots a_2 a_1a_0 \pmod{2^j} \end{align*} or equivalently, $n=2^jm+\left(a_{j-1} \cdots a_0 \right)$ for some integer $m.$ Therefore the highest power $j$ of $2$ that divides $n$ must divide the last $j$ digits of $n.$

Example. For example, since $2\vert 8,$ $4\vert 68,$ $8\vert 368,$ $16\vert 6368,$ $32\vert 46368,$ and $64\vert 946368,$ but $128n\mid 6946368$ we see the highest power of 2 that divides $6946368$ is 6.

### Divisibility Test for Powers of 3

Theorem. Let $n=a_ka_{k-1}\cdots a_1a_0$ be the $k+1$ digits of a positive integer $n$. Then $n$ is divisible by 3 exactly when $a_k+a_{k-1}+\cdots +a_1+a_0$ is divisible by $3.$

Proof. Since $10 \equiv 1 \pmod{3}$ we have, $n=\sum_{j=0}^k a_j10^j \equiv \sum_{j=0}^k a_j \pmod{3}.$ Therefore for some integer $m,$ $n=3m+\sum_{j=0}^k a_j$ and so $n$ is divisible by $3$ precisely when $\sum_{j=0}^k a_j$ is divisible by 3.

Example. Since the sum of the digits of $16946300068$ is $43$ and 43 is not divisible by 3 neither is $16946300068.$ Also notice the sum of the digits of $13230807$ is $24,$ 24 is divisible by 3, and thus so is $13230807.$

### Divisibility Test for Powers of 5

Everyone knows an application of congruence for divisibility by 5, just check the last digit. Since $10 – 2*5$ we have the analogous result for power of 5 as we did for powers of 2.

Theorem. Let $n=a_ka_{k-1}\cdots a_1a_0$ be the $k+1$ digits of a positive integer $n$. Then $n$ is divisible by $5^j$ exactly when the integer made up of the last $j$ digits of $n$ is divisible by $5^j.$

Proof. Since $10 \equiv 0 \pmod{5}$ it follows $10^j \equiv 0 \pmod{5^j}$ for any positive integer $j.$ Thus for $0leq jleq k,$ \begin{align*} n & =a_k10^k+\cdots +a_j10^j+a_{j-1}10^{j-1}+ \cdots +a_0 \\ & \equiv a_{j-1} \cdots a_2 a_1 a_0 \pmod{5^j} \end{align*} or equivalently, $n=5^jm+\left(a_{j-1} \cdots a_0 \right)$ for some integer $m.$ Therefore, the highest power $j$ of $5$ that divides $n$ must divide the last $j$ digits of $n.$

Example. For example, since $5\vert 5,$ $25\vert 25,$ $125\vert 125,$ $625\vert 8125,$ $3125\vert 78125$ but $15625n\mid 778125$ we see the highest power of 5 that divides $n$ is 5.

### Divisibility Test for 7

Theorem. Let $n=a_ka_{k-1} \cdots a_1a_0$ be the $k+1$ digits of a positive integer $n.$ Then $n$ is divisible by $7$ precisely when $a_2a_1a_0-a_5a_4a_3+a_8a_7a_6-\ldots$ is divisible by $7.$

Proof. Since $1000 \equiv -1 \pmod{7}$ we have, \begin{align*} n & =a_0+a_1 10+a_2 10^2+ \cdots +a_{k-2}10^{k-2}+a_{k-1}10^{k-1}+a_k 10^k \\ & = \left(a_0+10a_1+100a_2 \right)+1000\left(a_3+10a_4+100a_5 \right) \\ & \hspace{.75cm}+1000^2 \left(a_6+10a_7+100a_8 \right) +1000^3\left(a_9+10a_{10}+100a_{11} \right) + \cdots \\ & \equiv \left(a_0+10a_1+100a_2 \right)- \left(a_3 +10a_4+100a_5 \right) \\ & \hspace{.75cm} + \left(a_6 +10a_7+100a_8 \right)-\left(a_9 + 10a_{10} + 100a_{11} \right) + \cdots \pmod{7} \end{align*} Therefore for some integer $m,$ $n=7m+\sum_{j\in\{0,3,6, \cdots \}} (-1)^ja{j+2}a_{j+1}a_j$ and so $n$ is divisible by $7$ when the summation is divisible by 7.

Example. Notice $18902394819$ is divisible by 7 since $819-394+902-18=1309$ and $7|1309.$

### Divisibility Test for Powers of 9

Theorem. Let $n=a_k a_{k-1} \cdots a_1a_0$ be the $k+1$ digits of a positive integer $n.$ Then $n$ is divisible by 9 precisely when $a_k+a_{k-1}+ \cdots+a_1+a_0$ divisible by $9.$

Proof. Since $10 \equiv 1 \pmod{9}$ we have, $n=\sum_{j=0}^k a_j10^j \equiv \sum_{j=0}^k a_j \pmod{9}.$ Therefore for some integer $m,$ $n=9m+\sum_{j=0}^k a_j$ and so $n$ is divisible by $9$ precisely when $\sum_{j=0}^k a_j$ is divisible by 9.

Example. Since the sum of the digits of $169468$ is $34$ and 34 is not divisible by 9 neither is $169468.$ Since the sum of the digits of $1380716676$ is $45$ and 45 is divisible by 9 so is $1380716676.$

### Divisibility Tests for 11

Theorem. Let $n=a_ka_{k-1} \cdots a_1a_0$ be the $k+1$ digits of a positive integer $n.$ Then

(1) $n$ is divisible by 11 precisely when $a_0-a_1+ \cdots +(-1)^k a_k$ is divisible by $11$ and

(2) $n$ is divisible by $11$ precisely when $a_2 a_1 a_0 -a_5 a_4 a_3+a_8 a_7 a_6- \cdots$ is divisible by $11.$

Proof. Since $10 \equiv -1 \pmod{11}$ we have, $n=\sum_{j=0}^k a_j10^j \equiv \sum_{j=0}^k (-1)^ja_j \pmod{11}.$ Therefore for some integer $m$, $n=11m+\sum_{j=0}^k (-1)^ja_j$ and so $n$ is divisible by $11$ when $\sum_{j=0}^k (-1)^ja_j$ is divisible by 11. Since $1000 \equiv -1 \pmod{11}$ we have, \begin{align*} n & =a_0+a_1 10+a_2 10^2+ \cdots +a_{k-2}10^{k-2}+a_{k-1}10^{k-1}+a_k 10^k \\ & = \left(a_0+10a_1+100a_2 \right) + 1000 \left(a_3+10a_4+100a_5 \right) + 1000^2 \left(a_6+10a_7+100a_8 \right) \\ & \hspace{.75cm} +1000^3 \left(a_9+10a_{10}+100a_{11} \right) + \cdots \\ & \equiv \left(a_0+10a_1+100a_2 \right)- \left(a_3+10a_4+100a_5 \right) + \left(a_6+10a_7+100a_8 \right) \\ & \hspace{.75cm} – \left(a_9 + 10a_{10} + 100a_{11} \right) + \cdots \pmod{11} \end{align*} Therefore for some integer $m$, $n=11 m + \underset{j\in \{0,3,6, \cdots\}}{\overset{k}{\sum }}(-1)^ja_{j+2}a_{j+1}a_j$ and so $n$ is divisible by $11$ precisely when the summation is divisible by 11.

Example. Since $413-348+246-141+799-1=968$ and $11|968$ we see that $11$ divides $1799141246348413.$

### Divisibility Test for 13

The divisibility test for 13 is not as a well-known application of congruence as the previous results.

Theorem. Let $n=a_ka_{k-1} \cdots a_1a_0$ be the $k+1$ digits of a positive integer $n.$ Then $n$ is divisible by $13$ precisely when $a_2a_1a_0-a_5a_4a_3+a_8a_7a_6- \cdots$ divisible by $13.$

Proof. Since $1000 \equiv -1 \pmod{13}$ we have, \begin{align*} n & =a_0+a_1 10+a_2 10^2+ \cdots +a_{k-2}10^{k-2}+a_{k-1}10^{k-1}+a_k 10^k \\ & = \left(a_0 +10a_1 +100a_2 \right)+1000 \left(a_3 +10a_4+100a_5 \right) \\ & \hspace{.75cm} + 1000^2 \left(a_6 + 10a_7+100a_8 \right)+1000^3 \left(a_9+10a_{10} +100a_{11} \right) + \cdots \\ & \equiv \left(a_0+10a_1+100a_2 \right)- \left(a_3+10a_4 + 100a_5 \right) + \left (a_6+10a_7+100a_8\right) \\ & \hspace{.75cm} – \left(a_9 +10a_{10} +100a_{11} \right) + \cdots \pmod{13} \end{align*} Therefore for some integer $m,$ $n=13m+\underset{j\in \{0,3,6, \cdots\}}{\overset{k}{\sum }}(-1)^ja_{j+2}a_{j+1}a_j$ and so $n$ is divisible by $13$ precisely when the summation is divisible by 13.

Example. Notice $13$ divides 2,126,257,836,593,579 since $579-593+836-257+126-2=689$ and $13|689.$

## Applications of Congruence – Days of the Week

For our second application of congruence we will discuss how to find the day of the week for a given date.

### Using the Gregorian calendar

Let the days of the week be represented by the following numbers. \begin{equation*} \begin{array}{c|c|c|c|c|c|c} \text{Sunday} & \text{Monday} & \text{Tuesday} & \text{Wednesdays} & \text{Thursday} & \text{Friday} & \text{Saturday} \\ \hline 0 & 1 & 2 & 3 & 4 & 5 & 6 \end{array} \end{equation*} Also let the months of a year be represented by the numbers. \begin{equation*} \begin{array}{c|c|c|c|c|c|c|c|c|c|c|c} \text{Mar}. & \text{Apr}. & \text{May}. & \text{Jun}. & \text{Jul}. & \text{Aug}. & \text{Sep}. & \text{Oct}. & \text{Nov}. & \text{Dec}. & \text{Jan}. & \text{Feb}. \\ \hline 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \end{array} \end{equation*}

Using this convention we can express each date (after 1600) using the following variables. \begin{equation*} \begin{array}{c|c|c|c|c} \text{day of the month} & \text{month} & \text{year} & \text{century} & \text{particular year of the century} \\ \hline k & m & N & C & Y \end{array} \end{equation*} For example, for the date October 31, 1996, we have $k=31,$ $m=8,$ $N=1996,$ $C=19,$ and $Y=96.$ For the date, January 22, 1970, we have $k=22,$ $m=11,$ $N=1969,$ $C=19,$ and $Y=69.$ Also, for the date January 4, 1800, we have $k=4,$ $m=11,$ $N=1799,$ $C=17,$ and $Y=99.$

Using the Gregorian calendar and the above conventions is given by \begin{equation*} W \equiv k+[2.6m-0.2]-2C+Y+\left[\frac{Y}{4} \right] + \left[\frac{C}{4} \right] \pmod{7} \end{equation*} where $W$ is the day of the week of day $k$ of month $m$ of year $N$.

### Application of Congruence Examples – Days of the Week

Example. Determine the day of the week for the date: (David Hilbert‘s Birthday) January 23rd, 1862.

Solution. Since, $C=18,$ $Y=61,$ $m=11,$ and $k=23,$ we have, $$W \equiv 23+[2.6(11)-0.2]-2(18)+(61)+\left[\frac{(61)}{4} \right]+\left[\frac{(18)}{4} \right] \equiv 4 \pmod{7}.$$ Therefore, the day of the week is Thursday.

Example. Determine the day of the week for the date: (Georg Cantor‘s Birthday) March 3rd, 1845.

Solution. Since, $C=18,$ $Y=45,$ $m=1,$ and $k=3,$ we have, $$W \equiv 3+[2.6(1)-0.2]-2(18)+(45)+\left[\frac{(45)}{4} \right]+\left[\frac{(18)}{4}\right] \equiv 1 \pmod{7}.$$ Therefore, the day of the week is Monday.

Example. Determine the day of the week for the date: (Gertrude Mary Cox‘s Birthday) January 13th, 1900.

Solution. Since, $C=18,$ $Y=99,$ $m=11,$ and $k=13,$ we have, $$W \equiv 13+[2.6(11)-0.2]-2(18)+(99)+\left[\frac{(99)}{4}\right]+\left[\frac{(18)}{4}\right] \equiv 6 \pmod{7}.$$ Therefore, the day of the week is Saturday.

Example. Determine the day of the week for the date: (Albert Einstein‘s Birthday) March 14th, 1879.

Solution. Since, $C=18,$ $Y=79,$ $m=1,$ and $k=14,$ we have, $$W \equiv 14+[2.6(1)-0.2]-2(18)+(79)+\left[\frac{(79)}{4}\right]+\left[\frac{(18)}{4}\right] \equiv 5 \pmod{7}.$$ Therefore, the day of the week is Friday.

Example. Determine the day of the week for the date: (Johann Carl Friedrich Gauss‘s Birthday) April 30th, 1777.

Solution. Since, $C=17,$ $Y=77,$ $m=2,$ and $k=30,$ we have, $$W \equiv 30+[2.6(2)-0.2]-2(17)+(77)+\left[\frac{(77)}{4}\right]+\left[\frac{(17)}{4} \right] \equiv 3 \pmod{7}.$$ Therefore, the day of the week is Wednesday.

## Exercises on Applications of Congruence

Use the applications of congruence theorems above to solve the following exercises.

Exercise. Determine the highest power of $2$ that divides each of the following integers.

(1) 201984

(2) 1423408

(3) 89375744

(4) 41578912246000

Exercise. Determine the highest power of $5$ that divides each of the following integers.

(1) 112250

(2) 4860625

(3) 235555790

(4) 48126953125

Exercise. Determine which of the following integers is divisible by 3 and and also divisible by 9.

(1) 18381

(2) 6541351

(3) 67431097375

(4) 78918239735

Exercise. Use a congruence modulo 9 to find the missing digit, indicated by a question mark: $(89878)(58965)=5299?56270.$

Exercise. An old receipt has faded. It reads 88 chickens at a total of  x 4.2 y ,$where$x$and$y$are unreadable digits. How much did each the chicken cost? Exercise. Develop a test for divisibility by 37, based on the fact that$10^3 \equiv 1 \pmod{37}.$Use this to check$443692$and$11092785\$ for divisibility by 37.

Exercise. Use divisibility tests to write each of the following integers in its unique factorization form.

(1) 199760091031436820164280

(2) 36283732818351978960000

(3) 367059167270265157051864500

(4) 898920409641465690739260000

### Exercises on Days of the Week

Exercise. Use an application of congruence to find the day of the week for each of the following.

(1) November 19, 1863 (Lincoln’s Gettysburg Address)

(2) April 18, 1906 (San Franciso’s Address)

(4) July 4, 1776 (U.S. Declaration of Independence.)

(5) November 24, 1859 (Charles Darwin published The Origin of Species)

(6) July 20, 1969 (First man on the moon)

(7) February 23, 1848 (Revolution in Paris)

Exercise. Determine the day of the week on which you were born.

Exercise. For the year 2010, determine (a) the calendar dates on which Mondays will occur in March and (b) the months in which the thirteenth will fall on a Friday.

Exercise. Find the years in the decade 2000 to 20009 when November 29 is on a Saturday.

Exercise. Show that every year in the Gregorian calendar includes at least one Friday the 13th.

Exercise. Determine a divisibility test for 41 and use it to determine if 41 divides 98,992,255,736,508,865,900.