Example Problems Regarding Congruences

Before we look at some questions regarding congruences, let's first recall some properties of congruences:

• 1) $a \equiv b \pmod {m} \implies m \: \mid \: (a - b)$.

• 2) If $a \equiv b \pmod {m}$, then $a = b + km$ for some k.

• 3) Every integer is congruent (mod m) to one of $0, 1, 2, ..., m - 1$.

• 4) $a \equiv 0 \pmod {m} \implies m \: \mid \: a$.

• 5) $a \equiv a \pmod {m}$ (Reflexive Property).

• 6) If $a \equiv b \pmod {m}$, then $b \equiv a \pmod {m}$ (Symmetric Property).

• 7) If $a \equiv b \pmod {m}$ and $b \equiv c \pmod {m}$, then $a \equiv c \pmod {m}$ (Transitive Property).

• 8) If $a \equiv b \pmod {m}$ and $c \equiv d \pmod {m}$, then $a + c \equiv b + d \pmod {m}$.

• 9) If $a \equiv b \pmod {m}$ and $c \equiv d \pmod {m}$, then $ac \equiv bd \pmod {m}$.

• 10) If $ac \equiv bc \pmod {m}$, and $(c, m) = 1$, then $a \equiv b \pmod {m}$.

• 11) If $ac \equiv bc \pmod {m}$, and $(c, m) = d$, then $a \equiv b \pmod {m/d}$.

Additionally, we will note that if we restrict an integer $n ≠ bk$, then this is the same thing as saying that n is not a multiple of b (which will appear in later questions).

Example 1

Are there any integers in the form 7 + 9n that are a sum of three squares?

Suppose that we let $k = 7 + 9n$. Hence $k \equiv 7 \pmod {9}$. Additionally, suppose that k is a sum of three squares, that is $k = a^2 + b^2 + c^2$. It follows that if this statement is true, then:

(1)

\begin{align} a^2 + b^2 + c^2 \equiv 7 \pmod {9} \end{align}

Now we have that:

12 ≡ 1 (mod 9)

22 ≡ 4 (mod 9)

32 ≡ 0 (mod 9)

42 ≡7 (mod 9)

52 ≡ 7 (mod 9)

62 ≡ 0 (mod 9)

72 ≡ 4 (mod 9)

82 ≡1 (mod 9)

Hence all squares are either 0, 1, 4, or 7 (mod 9). So if we have a sum where two squares a congruent to 0 (mod 9) and one square is congruent to 7 (mod 9), then we have an integer k that satisfies this property. For example, $k = 3^2 + 6^2 + 4^2 = 61$. Hence there exists integers in the form 7 + 9n that satisfy this property.

Example 2

Are there any integers in the form 5 + 6n that are a sum of 4 squares?

We can solve this problem in the same manner as example 2. Suppose that k = 5 + 6n. Then $k \equiv 5 \pmod {6}$. Additionally, suppose that k is the sum of 4 squares, that is $k = a^2 + b^2 + c^2 + d^2$. Then we need to see if the following congruence holds:

(2)

\begin{align} a^2 + b^2 + c^2 + d^2 \equiv 5 \pmod {6} \end{align}

12 ≡ 1 (mod 6)

22 ≡ 4 (mod 6)

32 ≡ 3 (mod 6)

42 ≡ 4 (mod 6)

52 ≡ 1 (mod 6)

Hence, we need to see if there if there are four squares whose sum is congruence to 5 (mod 6). This can happen when we select one square that is congruent to 1, two squares that are congruent to 3, and one square that is congruent to 4 (mod 6). For example, let's choose 1, 3, 4, and 9. We thus get that $k = 1^2 + 3^2 + 4^2 + 9^2 = 107$. Hence there are integers in the form of 5 + 6n that are the sum of 4 squares.

Example 3

For n > 1, and n ≠ 7k, is it possible for $n^2 \equiv n^3 \pmod {7}$?

Since n ≠ 7k, then n is not a multiple of 7. Hence $(n, 7) = 1$. Hence it follows that we can divide both sides of the congruence by n², that is we must evaluate the congruence $1 \equiv n \pmod {7}$ or more appropriately $n \equiv 1 \pmod {7}$.

Of course this is possible when n = 1 + 7k for k ≥ 1. Hence it is possible that $n^2 \equiv n^3 \pmod {7}$, for example when n = 8 since $64 \equiv 512 \pmod {7}$.

Example 4

Is it possible for $n^2 + 1 \equiv n + 2 \pmod {5}$ for all n ≠ 3 + 5k.

We note that this congruence is the same as $n + 2 \equiv n^2 + 1 \pmod {5}$ which is the same as the congruence $n + 2 \equiv n^2 - 4 \pmod{5}$ or rather $n + 2 \equiv (n + 2)(n - 2) \pmod {5}$. Since n ≠ 3 + 5k, then $((n + 2), 5) = 1$, and hence it follows that $1 \equiv n - 2 \pmod {5}$ or rather $n \equiv 3 \pmod {5}$, which happens when n = 3. Hence it is possible that $n^2 + 1 \equiv n + 2 \pmod {5}$ for all n ≠ 3 + 5k. For example, $10 \equiv 5 \pmod {5}$.

Example 5

Is it possible for n ≠ 10k, and n > 1 that both $n^2$ and $n^3$ have the same last digit?

Note that we can determine the "last digit" of an integer by evaluating it modulo 10. Hence we want to know if $n^2 \equiv n^3 (mod 10)$ for any n ≠ 10k and n > 1. Now suppose that $(n, 10) = 1$. Hence it follows that $n \equiv 1 \pmod {10}$. Can we find such n with this property? In fact, we can. Let n = 11. It thus follows that $11^2 \equiv 11^3 \pmod {10}$. We note that 11² = 111, and the last digit is 1. Additionally, we know that 11³ = 1331, and the last digit is also 1. 11 ≠ 10k, and 11 > 1, hence it is possible that both n² and n² have the same last digit.

We should note that we supposed that $(n, 10) = 1$ only to simplify the congruence. Since we have found a solution, we have answered the question. However, there might solutions to our problem when $(n, 10) ≠ 1$, however, we will not overcomplicate this problem.

Example 6

For what primes p does $1815 \equiv 1542 \pmod {p}$?

By the definition of a congruence, we get that $p \: \mid \: (1815 - 1542)$, or rather $p \: \mid \: 273$. Since p is a prime, we will only look at prime divisors. The prime power decomposition of $273 = 3 \cdot 7 \cdot 13$. Hence the possible values of p are 3, 7, and 13.