# Application of Congruences

## Divisibility Tests
Let n $b$e a positive integer. We can express it in base-10 with $k+1$ digits as follows:

$$
n = (a_k a_{k-1} \dots a_1 a_0)_{10} = a_k \cdot 10^k + a_{k-1} \cdot 10^{k-1} + \cdots + a_1 \cdot 10 + a_0
$$

with $0 \leq a_i \leq 9$. These tests rely on the modular behavior of powers of $10$.

### Divisibility by Powers of 2 and 5
Since $10^r \equiv 0 \pmod{2^r}$ and $10^r \equiv 0 \pmod{5^r}$, divisibility is determined entirely by the last $r$ digits.

:::danger
**Rule for Power of 2 and 5**
An integer $n$ is divisible by $2^r$ (or $5^r$) if and only if the number formed by the last $r$ digits is divisible by $2^r$ (or $5^r$).
\begin{align}
2^r \mid n &\iff 2^r \mid (a_{r-1} a_{r-2} \dots a_0)_{10} \\
5^r \mid n &\iff 5^r \mid (a_{r-1} a_{r-2} \dots a_0)_{10}
\end{align}
:::

:::warning
**Example** Consider $n = 32,688,048$.

* $2 \mid n$ because $2\mid 8$ (the last digit).
* $4 \mid n$ because $4\mid 48$ (the last 2 digits).
* $8 \mid n$ because $8\mid 048$ (the last 3 digits).
* $16 \mid n$ because $16\mid 8048$ (the last 4 digits).
* $32 \not\mid n$ because $32\not\mid 88048$.
:::

:::warning
**Example** Consider $n = 155,375$.

* $5 \mid n$ because $5 \mid 5$.
* $25 \mid n$ because $25 \mid 75$.
* $125 \mid n$ because $125 \mid 375$.
* $625 \not\mid n$ because $625 \not\mid 5375$.
:::

### Divisibility by 3 and 9
The rules for 3 and 9 arise from the property that $10 \equiv 1 \pmod{3}$ and $10 \equiv 1 \pmod{9}$.

:::danger
**Rule for 3 and 9**
Since $10 \equiv 1 \pmod{3}$ and $10 \equiv 1 \pmod{9}$, an integer $n$ is congruent to the sum of its digits modulo $3$ and $9$:
$$
n \equiv a_k + a_{k-1} + \cdots + a_1 + a_0 \pmod{3}, \quad \pmod{9}
$$

Therefore,
\begin{align}
3\mid n &\iff 3\mid (a_k + a_{k-1} + \cdots + a_0) \\
9\mid n &\iff 9\mid (a_k + a_{k-1} + \cdots + a_0)
\end{align}
:::

:::warning
**Example** Consider $n = 4,127,835$.
* The sum of the digits is $4 + 1 + 2 + 7 + 8 + 3 + 5 = 30$.
* Since $3 \mid 30$, we have $3 \mid n$.
* Since $9\not\mid 30$, we have $9\not\mid n$
:::

### Divisibility by 11
The rule for 11 uses the property that $10 \equiv -1 \pmod{11}$.

:::danger
**Rule for 11**
Since $10^i \equiv (-1)^i \pmod{11}$, an integer $n$ is congruent to the alternating sum of its digits:
$$
n \equiv a_0 - a_1 + a_2 - a_3 + \dots + (-1)^{k}a_k \pmod{11}
$$

Therefore,
$$
11 \mid n \iff 11 \mid (\text{Alternating sum of its digits})
$$
:::

:::warning
**Example** Consider $n = 723,160,823$.

* The alternating sum (starting from the right) is $$3−2+8−0+6−1+3−2+7=22$$
* Since $11 \mid1$, we have $11 \mid n$.
:::

### Divisibility by 7, 11, and 13
The rule for these three primes is based on the fact that $7 \times 11 \times 13=1001$, so $1000 \equiv −1 \pmod{1001}$.

:::danger
**Rule for 7, 11, and 13**
For an integer $n$, group the digits into blocks of three starting from the right. The integer $n$ is congruent to the alternating sum of these 3-digit blocks:
$$
n \equiv (a_2 a_1 a_0)_{10} - (a_5 a_4 a_3)_{10} + (a_8 a_7 a_6)_{10} - \dots \pmod{1001}
$$

Therefore, for $x=7,11$, or $13$:
$$
x\mid n \iff x\mid (\text{Alternating sum of 3-digit blocks})
$$
:::

:::warning
**Example** Consider $n = 59,358,208$.

* The 3-digit blocks from right to left are $208$, $358$, $59$.
* The alternating sum is $208−358+59=−91$.
* Since $7 \mid −91$, we have $7 \mid n$.
* Since $11\not\mid -91$, we have $11 \not\mid n$.
* Since $13∣−91$, we have $13 \mid n$.
:::

### General Divisibility in Arbitrary Bases
The base-10 rules can be generalized to any base b. Let $n = (a_k a_{k-1} \dots a_0)_b$, where $0 \leq a_i \leq b-1$.

:::danger
**Theorem**
1. If $d\mid b$, then $$d^r\mid n \iff d^r\mid (a_{r-1} a_{r-2} \dots a_0)_b$$
2. If $d\mid (b-1)$, then $$d\mid n \iff d\mid (a_k + a_{k-1} + \dots + a_0)$$
3. If $d\mid (b+1)$, then $$d\mid n \iff d\mid \left( (-1)^k a_k + (-1)^{k-1} a_{k-1} + \dots -a_1 + a_0\right)$$
:::

:::success
**Exercise**
1. Determine the highest power of 2 that divides each of the following positive integers.
- a) 201,984
- b) 1,423,408
- c) 89,375,744
- d) 41,578,912,246
2. Which of the following integers are divisible by 3? Of those that are, which are divisible by 9?
- a) 18,381
- b) 65,412,351
- c) 987,654,321
- d) 78,918,239,735
3. Which of the following integers are divisible by 2?
- a) $(1210122)_3$
- b) $(211102101)_3$
- c) $(1112201112)_3$
- d) $(10122222011101)_3$
4. Use a congruence modulo 9 to find the missing digit, indicated by a question mark: $$89,878\times58,965 = 5299?56270$$
5. Suppose that $n = 917,4X8,835$, where $X$ is a missing digit. Find all possible values of $X$ so that $n$ is divisible by each of these integers:
- a) 2
- b) 3
- c) 5
- d) 9
- e) 11
- f) 25
:::

## Encoding Messages (Cryptography)
Modular arithmetic is fundamental to cryptography, particularly in methods like the *Caesar cipher* and more complex *affine ciphers*. This process involves replacing each letter with a corresponding number, performing a mathematical operation (a linear congruence), and then converting the resulting number back into a letter.

The standard English alphabet has 26 letters (A to Z). We assign a number to each letter, typically $A=0, B=1, \dots, Z=25$.

:::info
**Definition (The Affine Cipher)** An affine cipher uses a transformation of the form:
$$
y \equiv ax+b \pmod{m}
$$

where:
* $x$ is the numerical value of the original (plaintext) letter.
* $y$ is the numerical value of the encoded (ciphertext) letter.
* $m$ is the size of the alphabet, which is 26.
* $a$ and $b$ are the keys, chosen such that $\textrm{gcd}(a,m)=1$. The condition $\textrm{gcd}(a,26)=1$ ensures that the transformation can be uniquely reversed (decoded).
:::

:::warning
**Encoding Example**
Using $m=26$ and the keys $a=3$ and $b=11$, we encode the word **WIN**:

| Letter | Plaintext Value (x) | Calculation ($3x+11 \pmod{26}$) | Ciphertext Value (y) |
| :---: | :---: | :--- | :---: |
| **W** | 22 | $22 \cdot 3+11=77 \equiv 25$ | 25 |
| **I** | 8 | $8 \cdot 3+11=35 \equiv 9$ | 9 |
| **N** | 13 | $13 \cdot 3+11=50 \equiv 24$ | 24 |

The word WIN is replaced by the numbers **25, 9, 4**. This sequence of numbers can be read as a single number in base-26, $\overline{25,9,24}_{26}$, which corresponds to the integer
$$
25 \cdot 26^2 + 9 \cdot 26 + 24 = 17,158
$$
:::