Modular Arithmetic
Given \( x, y, m \in \mathbb{Z} \) and \( m > 1 \), the relation defined by
\[
\beta = \{ (x, y) : m \mid (x – y) \}
\]
\[
\beta = \{ (x,y) : \text{the difference } x – y \text{ is exactly divisible by } m \}
\]
is an equivalence relation.
Since \( x – y \) is exactly divisible by \( m \) in the relation \(\beta\), for some \( k \in \mathbb{Z} \), we have
\[
x – y = m \cdot k \Rightarrow x = mk + y
\]
Here, because \( (x, y) \in \beta \) and \( \beta \) is an equivalence relation, \( x \) is congruent to \( y \).
Thus, for \( \forall x \in \mathbb{Z} \), the integer \( x \) is congruent to the remainder \( y \) obtained when \( x \) is divided by \( m \).
This congruence is expressed as
\[
x \equiv y \pmod{m}
\]
and is read as “\( x \) is congruent to \( y \) modulo \( m \)“.
Note:
\[
x \equiv y \pmod{m} \iff x = mk + y \iff \frac{x – y}{m} = k, \quad k \in \mathbb{Z}
\]
Example:
Let us find \( x \) given that \( 120 \equiv x \pmod{7} \).
\[
120 \equiv x \pmod{7} \Rightarrow 120 \div 7
\]
\[
120= 17 \cdot 7 + 1 , \quad \text{quotient: } 17, \quad \text{remainder: } 1
\]
\[
\Rightarrow x = 1
\]
\[
\text{giving } 120 \equiv 1 \pmod{7}
\]
\[
x = 1 + 7k, \quad k \in \mathbb{Z}
\]
\[
\text{Hence, we find } x \in \{ \dots, -6, 1, 8, \dots \}.
\]
Examples:
\(
\bullet
\)
\[
\begin{array}{r|l}
48 & 5 \\
45 & \rule{15mm}{0.3mm} \\
-\rule{15mm}{0.2mm} & 9 \\
3 &
\end{array}
\quad \Rightarrow \quad 48 \equiv 3 \pmod{5}
\]
\(
\bullet
\)
\[
\begin{array}{r|l}
48 & 5 \\
35 & \rule{15mm}{0.3mm} \\
-\rule{15mm}{0.2mm} & 7 \\
13 &
\end{array}
\quad \Rightarrow \quad 48 \equiv 13 \pmod{5}
\]
\(
\bullet
\)
\[
\begin{array}{r|l}
48 & 5 \\
50 & \rule{15mm}{0.3mm} \\
-\rule{15mm}{0.2mm} & 10 \\
-2 &
\end{array}
\quad \Rightarrow \quad 48 \equiv -2 \pmod{5}
\]
Examples:
\(
\bullet \quad 25 \equiv 4 \pmod{7} \quad \Rightarrow \quad \frac{25 – 4}{7} = 3, \quad 3 \in \mathbb{Z}
\)
\(
\bullet \quad 25 \equiv 39 \pmod{7} \quad \Rightarrow \quad \frac{25 – 39}{7} = -2, \quad -2 \in \mathbb{Z}
\)
\(
\bullet \quad 25 \equiv 11 \pmod{7} \quad \Rightarrow \quad \frac{25 – 11}{7} = 2, \quad 2 \in \mathbb{Z}
\)
Example:
Let us determine the possible values of \( x \) satisfying
\[
7x + 19 \equiv x – 2 \pmod{x}
\]
\[
\frac{7x + 19 – (x – 2)}{x} = k \quad \Rightarrow \quad \frac{6x + 21}{x} = k
\]
\[
\Rightarrow 6 + \frac{21}{x} = k
\]
Since \( x > 1 \), \( x \in \mathbb{Z} \), and \( k \in \mathbb{Z} \), the set of all possible values for \( x \) is
\[
\{ 3, 7, 21 \}
\]
QUESTION 1
Given that
\[
x^2 + 7x \equiv 15 \pmod{x}
\]
how many possible values can \( x \) take?
\[
\text{A) 1} \quad \text{B) 2} \quad \text{C) 3} \quad \text{D) 4} \quad \text{E) 5}
\]
Solution:
\[
x^2 + 7x \equiv 15 \pmod{x} \Rightarrow \frac{x^2 + 7x – 15}{x} = k
\]
\[
\Rightarrow x + 7 – \frac{15}{x} = k
\]
Since \( x > 1 \), \( x \in \mathbb{Z} \), and \( k \in \mathbb{Z} \), the set of possible values for \( x \) is:
\[
\{ 3, 5, 15 \}
\]
\(\textbf{Answer: C} \)
QUESTION 2
If \( x^3 + x \equiv 2x^2 + 2 \pmod{(x^3 + x)} \), what is the sum of all possible values of \( x \)?
\[
\text{A) 3} \quad \text{B) 4} \quad \text{C) 5} \quad \text{D) 6} \quad \text{E) 7}
\]
Solution:
\[
x^3 + x \equiv 2x^2 + 2 \pmod{(x^3 + x)}
\]
\[
\Rightarrow \frac{x^3 + x – (2x^2 + 2)}{x^3 + x} = k
\]
\[
\Rightarrow \frac{(x^2 + 1)(x – 2)}{x (x^2 + 1)} = k
\]
\[
\Rightarrow \frac{x – 2}{x} = k \Rightarrow 1 – \frac{2}{x} = k
\]
Since \( x^3 + x > 1 \), \( x \in \mathbb{Z} \), and \( k \in \mathbb{Z} \), the possible values for \( x \) are \( x_1 = 1, x_2 = 2 \).
\[
\Rightarrow x_1 + x_2 = 3
\]
\(\textbf{Answer: A} \)
Residue Classes:
We know that the equivalence relation defined on the set of integers by
\[
\beta = \{ (x, y) \mid \text{the difference } x – y \text{ is exactly divisible by } m \}
\]
partitions the set of integers into equivalence classes. These equivalence classes are denoted by
\[
\overline{0}, \overline{1}, \overline{2}, \dots, \overline{m-1}
\]
The set consisting of these equivalence classes is called the set of residue classes modulo \( m \) and is denoted by \( \mathbb{Z}/m \). Thus,
\[
\mathbb{Z} / m = \{ \overline{0}, \overline{1}, \overline{2}, \dots, \overline{m-1} \}
\]
Example:
For \( m = 5 \), let us determine the equivalence classes of the equivalence relation \( \beta = \{ (x, y) : 5 \mid (x – y) \} \).
The set of residue classes is
\[
\mathbb{Z} / 5 = \{ \overline{0}, \overline{1}, \overline{2}, \overline{3}, \overline{4} \}
\]
The individual equivalence classes are given by:
\[
\overline{0} = \{ \dots, -15, -10, -5, 0, 5, 10, 15, \dots \}
\]
\[
\overline{1} = \{ \dots, -14, -9, -4, 1, 6, 11, 16, \dots \}
\]
\[
\overline{2} = \{ \dots, -13, -8, -3, 2, 7, 12, 17, \dots \}
\]
\[
\overline{3} = \{ \dots, -12, -7, -2, 3, 8, 13, 18, \dots \}
\]
\[
\overline{4} = \{ \dots, -11, -6, -1, 4, 9, 14, 19, \dots \}
\]
In \( \mathbb{Z} / 5 \), any two elements belonging to the same equivalence class are congruent to each other modulo 5.
For instance, taking \( -11, 9 \in \overline{4} \):
\[
5 \mid (-11 – 9) \Rightarrow 5 \mid (-20) \Rightarrow -11 \equiv 9 \pmod{5}
\]
Furthermore, the remainder obtained when any number in a particular equivalence class is divided by 5 is precisely the canonical representative of that class.
For example, taking \( -11, 14, 19 \in \overline{4} \):
\[
\begin{array}{r|l}
-11 & 5 \\
-15 & \rule{15mm}{0.3mm} \\
-\rule{15mm}{0.3mm} & -3 \\
4 &
\end{array}
\quad \quad
\begin{array}{r|l}
14& 5 \\
10& \rule{15mm}{0.3mm} \\
-\rule{15mm}{0.3mm} & 2 \\
4 &
\end{array}
\quad \quad
\begin{array}{r|l}
19& 5 \\
15& \rule{15mm}{0.3mm} \\
-\rule{15mm}{0.3mm} & 3 \\
4 &
\end{array}
\]
Note:
The canonical representatives of the residue classes in \( \mathbb{Z} / m \) are \( 0, 1, 2, 3, \dots, m – 1 \).
Properties:
For \( x, y, a, b, m \in \mathbb{Z} \) and \( m > 1 \):
1) Let \( x \equiv y \pmod{m} \) and \( a \equiv b \pmod{m} \).
Congruences sharing the same modulus can be added, subtracted, or multiplied term by term. However, they cannot generally be divided.
\[
\begin{aligned}
x + a &\equiv y + b \pmod{m} \\
x – a &\equiv y – b \pmod{m} \\
x \cdot a &\equiv y \cdot b \pmod{m}
\end{aligned}
\]
Examples:
We are given \( 7 \equiv 19 \pmod{6} \) and \( 20 \equiv 2 \pmod{6} \).
\( \bullet \quad 7 + 20 \equiv 19 + 2 \pmod{6} \Rightarrow 27 \equiv 21 \pmod{6} \)
\( \bullet \quad 7 – 20 \equiv 19 – 2 \pmod{6} \Rightarrow -13 \equiv 17 \pmod{6} \)
\( \bullet \quad 7 \cdot 20 \equiv 19 \cdot 2 \pmod{6} \Rightarrow 140 \equiv 38 \pmod{6} \)
Corollary:
For \( \bar{p}, \bar{q} \in \mathbb{Z}/m \):
\[ \bar{p} + \bar{q} = \overline { p \;+ \; q } \]
\[ \bar{p} \cdot \bar{q} = \overline{p \;\cdot\; q} \]
Examples:
In \( \mathbb{Z}/5 \):
\[
\bar{3} + \bar{4} \equiv \overline{3 + 4 } \equiv 2
\]
\[
\bar{3} \cdot \bar{4} \equiv \overline{3 \cdot 4 } \equiv 2
\]
\[
\bar{1} +\bar{ 2 }+ \bar{3 } \equiv \overline{ 1 + 2 + 3 } \equiv 1
\]
2) An integer \( c \in \mathbb{Z} \) can be added to or subtracted from both sides of a congruence.
\[
x \equiv y \pmod{m} \Rightarrow x + c \equiv y + c \pmod{m}
\]
\[
\Rightarrow x – c \equiv y – c \pmod{m}
\]
Examples:
\( \bullet \quad 27 \equiv 3 \pmod{8} \Rightarrow 27 + 5 \equiv 3 + 5 \pmod{8} \Rightarrow 32 \equiv 8 \pmod{8}
\)
\( \bullet \quad 27 \equiv 3 \pmod{8} \Rightarrow 27 – 3 \equiv 3 – 3 \pmod{8} \Rightarrow 24 \equiv 0 \pmod{8} \)
3) Both sides of a congruence can be multiplied by an integer \( c \in \mathbb{Z} \).
\[
x \equiv y \pmod{m} \Rightarrow x \cdot c \equiv y \cdot c \pmod{m}
\]
Example:
\( \bullet \quad 25 \equiv 1 \pmod{4} \Rightarrow 25 \cdot 3 \equiv 1 \cdot 3 \pmod{4} \Rightarrow 75 \equiv 3 \pmod{4} \)
4) Dividing both sides of a congruence by an integer \( c \in \mathbb{Z} \):
a) Both sides of a congruence can be divided by \( c \) if \( c \) is coprime to the modulus \( m \).
\[x \equiv y \pmod{m} \Rightarrow \frac{x}{c} \equiv \frac{y}{c} \pmod{m} \]
Examples:
\( \bullet \quad \) \[\Rightarrow 66 \equiv 3 \pmod{7} \Rightarrow \frac{66}{-3} \equiv \frac{3}{-3} \pmod{7} \Rightarrow -22 \equiv -1 \pmod{7} \]
\( \bullet \quad \) \[
\Rightarrow 58 \equiv 22 \pmod{9} \Rightarrow \frac{58}{2} \equiv \frac{22}{2} \pmod{9} \Rightarrow 29 \equiv 11 \pmod{9}
\]
\( \bullet \quad 40 \equiv 10 \pmod{6} \) In this congruence, we cannot simplify both sides by dividing by 10. This is because the divisor 10 and the modulus (6) are not coprime (\(\gcd(10,6) = 2 \neq 1\)). That is, in this case:
\[
\frac{40}{10} \not\equiv \frac{10}{10} \pmod{6}
\]
\[
\Rightarrow 4 \not\equiv 1 \pmod{6}
\]
b) If \( c \) is a common divisor of \( x, y \), and the modulus \( m \), then:
\[
x \equiv y \pmod{m} \Rightarrow \frac{x}{c} \equiv \frac{y}{c} \pmod{\frac{m}{c}}
\]
Example:
\( \bullet \quad 40 \equiv 10 \pmod{6} \Rightarrow \frac{40}{2} \equiv \frac{10}{2} \pmod{\frac{6}{2}} \Rightarrow 20 \equiv 5 \pmod{3}
\)
Since 20 and 3 are coprime, and 5 and 3 are coprime, we can further divide by 5:
\[
\frac{20}{5} \equiv \frac{5}{5} \pmod{3}
\]
\[
\Rightarrow 4 \equiv 1 \pmod{3}
\]
5) Both sides of a congruence can be raised to a positive integer power \( n \in \mathbb{Z}^+ \).
\[
x \equiv y \pmod{m} \Rightarrow x^n \equiv y^n \pmod{m}
\]
Example:
\[
96 \equiv 5 \pmod{7} \Rightarrow (96)^{10} \equiv 5^{10} \pmod{7}
\]
Note:
When performing algebraic operations in \( \mathbb{Z}/m \), any term \( a \) can be replaced by \( a + mk \) where \( k \in \mathbb{Z} \) (excluding exponents). In other words, integer multiples of the modulus can be added to or subtracted from any term.
Examples:
In \( \mathbb{Z} / 5 \):
\( \bullet \quad 3 \cdot 4 + 3^4 + 4^3 \cdot 3 = 2 + 1 + 4 \cdot 3 = 2 + 1 + 2 = 0 \)
\( \bullet \quad (2x + 3) \cdot (x + 4) = 2x^2 + 2 \cdot 4x + 3x + 3 \cdot 4 = 2x^2 + (3 + 3)x + 2\)
\[
\quad = 2x^2 + x + 2
\]
\( \bullet \quad f(x) = 3x + 4 \Rightarrow (f \circ f)(x) = f(f(x)) \)
\[
\quad = 3 \cdot (3x + 4) + 4 = 3 \cdot 3x + 3 \cdot 4 + 4
\]
\[
\quad = 4x + 2 + 4
\]
\[
\quad = 4x + 1
\]
Example:
Let us find the additive and multiplicative inverses of 3 in \( \mathbb{Z} / 7 \).
Let \( x \) be the additive inverse of 3, and \( y \) be its multiplicative inverse.
\[
3 + x = 0
\]
\[
\Rightarrow 3 + 4 + x = 0 + 4
\]
\[
\Rightarrow x = 4
\]
\[
3 \cdot y = 1 \Rightarrow 5 \cdot 3y = 5 \cdot 1
\]
\[
\Rightarrow 1 \cdot y = 5
\]
\[
\Rightarrow y = 5
\]
Note:
In \( \mathbb{Z}/m \), let the additive inverse of an element \( x \) be denoted by \( -x \), and its multiplicative inverse (if it exists) be denoted by \( x^{-1} = \frac{1}{x} \). Accordingly, for any two elements \( x, y \), we define division as:
\[
\frac{y}{x} = y \cdot \frac{1}{x}
\]
Example:
In \( \mathbb{Z} / 5 \), let us evaluate the expression:
\[
A = \left( \frac{3}{2} \right)^3 + \left( \frac{1}{3} \right)^5 + (-4)^{100}
\]
\[
A = \left( \frac{3}{2} \right)^3 + \left( \frac{1}{3} \right)^5 + (-4)^{100}
\]
\[
= (3 \cdot 2^{-1})^3 + (3^{-1})^5 + (-4)^{100}
\]
Here,
\( \bullet \quad 2^{-1} = x \) where \( x \) is the multiplicative inverse of 2.
\( \bullet \quad 3^{-1} = y \) where \( y \) is the multiplicative inverse of 3.
\( \bullet \quad -4 = z \) where \( z \) is the additive inverse of 4.
Thus,
\[
2x = 1 \Rightarrow 3 \cdot 2x = 3 \cdot 1
\]
\[
\Rightarrow x = 3
\]
\[
3y = 1 \Rightarrow 2 \cdot 3y = 2 \cdot 1 \Rightarrow y = 2
\]
\[
4 + z = 0 \Rightarrow z = 1
\]
Substituting these values back into the expression:
\[
A = (3 \cdot 3)^3 + 2^5 + 1^{100}
\]
\[
= 4^3 + 2 + 1
\]
\[
= 4 + 2 + 1 = 2
\]
Example:
Let us solve the previous example using an alternative approach. When working in \( \mathbb{Z} / 5 \), we can directly add or subtract multiples of 5 to the terms of the fractions to make them divisible.
\[
\text{In } \mathbb{Z} / 5 \text{,}
\]
\[
A = \left( \frac{3}{2} \right)^3 + \left( \frac{1}{3} \right)^5 + (-4)^{100}
\]
\[
= \left( \frac{3 + 5}{2} \right)^3 + \left( \frac{1 + 5}{3} \right)^5 + (-4 + 5)^{100}
\]
\[
= 4^3 + 2^5 + 1^{100}
\]
\[
= 4 + 2 + 1 = 2
\]
Example:
\[
\text{In } \mathbb{Z} / 7 \text{,}
\]
\[
\text{let us evaluate the expression: } (-5)^5 + (5^{-1})^3 + \left( \frac{1}{2} \right)^4
\]
\[
(-5)^5 + (5^{-1})^3 + \left( \frac{1}{2} \right)^4
\]
\[
= (-5 + 7)^5 + \left( \frac{1}{5} \right)^3 + \left( \frac{1+7}{2} \right)^4
\]
\[
= 2^5 + \left( \frac{1 + 7 + 7}{5} \right)^3 + 4^4
\]
\[
= 4 + 3^3 + 4
\]
\[
= 4 + 6 + 4 = 0
\]
Note:
In \( \mathbb{Z}/m \), the solution to the equation \( x^n = a \) can be formally denoted as
\[
x = \sqrt[n]{a}
\]
Example:
\[
\text{In } \mathbb{Z} / 7 \text{,}
\]
\[ \quad \sqrt{2}, \quad \sqrt{1} \quad \text{and } \quad \sqrt[3]{6} \quad \] let us compute these modular roots.
\( \bullet \quad \sqrt{2} = \sqrt{2 + 7} = 3, \quad \text{or } \sqrt{2} = \sqrt{2 + 2 \cdot 7} = 4 \)
\( \bullet \quad \sqrt{1} = 1, \quad \text{or } \sqrt{1} = \sqrt{1 + 5 \cdot 7} = 6 \)
\( \bullet \quad \sqrt[3]{6} = \sqrt[3]{6 + 3 \cdot 7} = 3, \quad \text{or } \sqrt[3]{6} = \sqrt[3]{6 – 7} = -1 = 6 \)
\[ \text{and } \sqrt[3]{6} = \sqrt[3]{6 – 2 \cdot 7} = \sqrt[3]{-8} = -2 = 5 \]
Alternatively, the roots \( \sqrt{1} \) and \( \sqrt{2} \) can be determined by inspecting the modular multiplication table for \( \mathbb{Z} / 7 \). The perfect squares appear on the main diagonal.
\[
\begin{array}{c|ccccccc}
\cdot & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\
\hline
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & \fbox{1} & 2 & 3 & 4 & 5 & 6 \\
2 & 0 & 2 & 4 & 6 & 1 & 3 & 5 \\
3 & 0 & 3 & 6 & \fbox{2} & 5 & 1 & 4 \\
4 & 0 & 4 & 1 & 5 & \fbox{2} & 6 & 3 \\
5 & 0 & 5 & 3 & 1 & 6 & 4 & 2 \\
6 & 0 & 6 & 5 & 4 & 3 & 2 & \fbox{1} \\
\end{array}
\]
\[
\sqrt{2} = \sqrt{3 \cdot 3} = 3
\]
\[
\sqrt{2} = \sqrt{4 \cdot 4 } = 4
\]
\[
\sqrt{1} = \sqrt{1 \cdot 1 } = 1
\]
\[
\sqrt{1} = \sqrt{6 \cdot 6 } = 6
\]
Example:
\[
\text{In } \mathbb{Z} / 6 \text{,}
\]
\[
\text{given } f(x) = 5x + 4 \text{, let us find its inverse function } f^{-1}(x).
\]
\[
y = f(x) = 5x + 4 \Rightarrow y + 2 = 5x + 4 + 2
\]
\[
\Rightarrow y + 2 = 5x
\]
\[
\Rightarrow 5(y + 2) = 5 \cdot 5x
\]
\[ 5y + 5 \cdot 2 = x \Rightarrow 5y + 4 = x = f^{-1}(y) \]
\[ \text{Thus, we find } f^{-1}(x) = 5x + 4. \]
Note:
Consider the linear congruence \( ax + b = 0 \) in \( \mathbb{Z}/m \).
Let \( d = \gcd(m, a) \). If \( d \) divides \( b \) (i.e., \( \frac{b}{d} = k \) for some \( k \in \mathbb{Z} \)), then the solution set is non-empty. The number of distinct solutions modulo \( m \) is exactly equal to \( d \).
Example:
\[
\text{In } \mathbb{Z} / 7 \text{,}
\]
\[
\text{let us solve the equation } 5x + 4 = 0.
\]
\[
5x + 4 = 0 \Rightarrow 5x + 4 + 3 = 0 + 3
\]
\[
\Rightarrow 5x = 3 \Rightarrow 3 \cdot 5x = 3 \cdot 3 \Rightarrow x = 2
\]
Example:
\[ \text{In } \mathbb{Z} / 6 \text{,} \]
\[
\text{let us find the two smallest positive values of } x \text{ satisfying } 2x = 2.
\]
\[
2x = 2 \pmod{6} \Rightarrow \frac{2x}{2} = \frac{2}{2} \pmod{\frac{6}{2}}
\]
\[
\Rightarrow x \equiv 1 \pmod{3}
\]
Hence, solving \( 2x = 2 \) in \( \mathbb{Z} / 6 \) reduces to solving \( x = 1 \) in \( \mathbb{Z} / 3 \).
The solutions within the modular range are:
\[
x_1 = 1 \quad \text{and} \quad x_2 = 1 + 3 = 4
\]
Example:
\[ \text{In } \mathbb{Z} / 5 \text{,} \]
\[
\text{let us find the solution set of the equation } x^2 + 4x = 2.
\]
\[
x^2 + 4x = 2 \Rightarrow x^2 + 4x + 3 = 2 + 3
\]
\[
\Rightarrow x^2 + 4x + 3 = 0
\]
\[
\Rightarrow (x + 1)(x + 3) = 0
\]
\[
\Rightarrow x + 1 = 0 \quad \text{or} \quad x + 3 = 0
\]
\[
\Rightarrow x = 4 \quad \text{or} \quad x = 2
\]
Thus, the solution set is:
\[
S = \{2, 4\}
\]
Example:
\[
\text{In } (\mathbb{Z} / 7)^2 \text{,}
\]
\[
\begin{cases}
x + 2y = 1 \\
2x + 3y = 6
\end{cases}
\]
let us find the value of \( y \) that satisfies this system of equations.
Multiplying the first equation by 5:
\[
x + 2y = 1 \Rightarrow 5(x + 2y) = 5 \cdot 1
\]
\[
\Rightarrow 5x + 3y = 5
\]
Now, adding it to the second equation:
\[
\begin{array}{rcl}
5x + 3y & = & 5 \\
+ \quad 2x + 3y & = & 6 \\
\hline
6y & = & 4
\end{array}
\]
\[
\Rightarrow 6 \cdot 6y = 6 \cdot 4
\]
\[
\Rightarrow y = 3
\]
Example:
\[
\text{Let us find } x \text{ if } 3^{27} \equiv x \pmod{5}.
\]
\[
3^1 \equiv 3 \pmod{5}
\]
\[
3^2 \equiv 4 \pmod{5}
\]
\[
3^3 \equiv 2 \pmod{5}
\]
\[
3^4 \equiv 1 \pmod{5} \Rightarrow (3^4)^6 \equiv 1^6 \pmod{5}
\]
\[
\Rightarrow 3^3 \cdot 3^{24} \equiv 3^3 \cdot 1 \pmod{5}
\]
Since \( 3^3 \equiv 2 \pmod{5} \):
\[
\Rightarrow 3^{27} \equiv 2 \pmod{5}
\]
\[
\text{Thus, we find } x = 2.
\]
Example:
Let us find the value \( x \), which represents the remainder when \( (1997)^{28} \) is divided by 7.
This can be modeled by the congruence:
\[
(1997)^{28} \equiv x \pmod{7}
\]
Since \( 1997 \equiv 2 \pmod{7} \), we have:
\[
(1997)^{28} \equiv 2^{28} \pmod{7} \Rightarrow 2^{28} \equiv x \pmod{7}
\]
Evaluating powers of 2:
\[
2^1 \equiv 2 \pmod{7}
\]
\[
2^2 \equiv 4 \pmod{7}
\]
\[
2^3 \equiv 1 \pmod{7}
\]
Using the cyclic property:
\[
(2^3)^9 \equiv 1^9 \pmod{7}
\]
\[
2 \cdot 2^{27} \equiv 2 \cdot 1 \pmod{7}
\]
\[
2^{28} \equiv 2 \pmod{7}
\]
\[
\text{Thus, we find } x = 2.
\]
QUESTION 3
If \( (1994)^{1996} \equiv x \pmod{5} \), what is the value of \( x \)?
\[
\text{A) 0} \quad \text{B) 1} \quad \text{C) 2} \quad \text{D) 3} \quad \text{E) 4}
\]
Solution:
\[
1994 \equiv -1 \pmod{5} \Rightarrow (1994)^{1996} \equiv (-1)^{1996} \pmod{5}
\]
\[
\Rightarrow (1994)^{1996} \equiv 1 \pmod{5}
\]
\[
\text{Therefore, } x = 1.
\]
\(\textbf{Answer: B} \)
QUESTION 4
\[
\text{If } (20)^{90} \equiv x \pmod{9} \text{, what is the value of } x \text{?}
\]
\[
\text{A) } 0 \quad \text{B) } 1 \quad \text{C) } 2 \quad \text{D) } 3 \quad \text{E) } 4
\]
Solution:
\[
20 \equiv 2 \pmod{9} \Rightarrow (20)^{90} \equiv 2^{90} \pmod{9}
\]
\[
2^1 \equiv 2 \pmod{9}
\]
\[
2^2 \equiv 4 \pmod{9}
\]
\[
2^3 \equiv -1 \pmod{9}
\]
\[
(2^3)^{30} \equiv (-1)^{30} \pmod{9}
\]
\[
2^{90} \equiv 1 \pmod{9}
\]
\[
\text{Therefore, } x = 1.
\]
\(\textbf{Answer: B} \)
QUESTION 5
\[
\text{What is the remainder when the product } 6^{25} \cdot 7^{13} \text{ is divided by 5?}
\]
\[
\text{A) } 0 \quad \text{B) } 1 \quad \text{C) } 2 \quad \text{D) } 3 \quad \text{E) } 4
\]
Solution:
\[
\text{We need to find } x \text{ in the congruence } 6^{25} \cdot 7^{13} \equiv x \pmod{5}.
\]
\[
6 \equiv 1 \pmod{5} \Rightarrow 6^{25} \equiv 1^{25} \pmod{5}
\]
\[
\Rightarrow 6^{25} \equiv 1 \pmod{5}
\]
\[
7 \equiv 2 \pmod{5} \Rightarrow 7^4 \equiv 2^4 \equiv 1 \pmod{5}
\]
\[
\Rightarrow (7^4)^3 \equiv 1^3 \pmod{5}
\]
\[
\Rightarrow 7 \cdot 7^{12} \equiv 7 \cdot 1 \pmod{5}
\]
\[
\Rightarrow 7^{13} \equiv 2 \pmod{5}
\]
\[
\text{Since } 6^{25} \equiv 1 \pmod{5} \text{ and } 7^{13} \equiv 2 \pmod{5}\text{:}
\]
\[
6^{25} \cdot 7^{13} \equiv 1 \cdot 2 \pmod{5}
\]
\[
\Rightarrow x = 2
\]
\(\textbf{Answer: C} \)
Note: (Fermat’s Little Theorem)
If \( m \) is a prime number and \( x \) is an integer not divisible by \( m \) (i.e., \( x \) and \( m \) are coprime), then:
\[
x^{m-1} \equiv 1 \pmod{m}
\]
Note that the value 1 can occasionally be achieved at an exponent smaller than \( m – 1 \).
Examples:
\[
2^{10} \equiv 1 \pmod{11}
\]
\[
6^{22} \equiv 1 \pmod{23}
\]
QUESTION 6
\[
\text{If } 7^{61} \equiv x \pmod{11} \text{, what is the value of } x \text{?}
\]
\[
\text{A) } 4 \quad \text{B) } 5 \quad \text{C) } 6 \quad \text{D) } 7 \quad \text{E) } 8
\]
Solution:
\[
\text{Since } m = 11 \text{ is prime, we have } m – 1 = 10\text{. By Fermat’s Little Theorem:}
\]
\[
7^{10} \equiv 1 \pmod{11}
\]
\[
(7^{10})^6 \equiv 1^6 \pmod{11}
\]
\[
7^{60} \equiv 1 \pmod{11}
\]
\[
7 \cdot 7^{60} \equiv 7 \cdot 1 \pmod{11}
\]
\[
7^{61} \equiv 7 \pmod{11} \implies x = 7
\]
\(\textbf{Answer: D} \)
QUESTION 7
\[
\text{If } 5^{120} \equiv x \pmod{13} \text{, what is the value of } x \text{?}
\]
\[
\text{A) } 1 \quad \text{B) } 5 \quad \text{C) } 7 \quad \text{D) } 9 \quad \text{E) } 11
\]
Solution:
\[
\text{Since } m = 13 \text{ is prime, we have } m – 1 = 12\text{. By Fermat’s Little Theorem:}
\]
\[
5^{12} \equiv 1 \pmod{13}
\]
\[
(5^{12})^{10} \equiv 1^{10} \pmod{13}
\]
\[
5^{120} \equiv 1 \pmod{13} \implies x = 1
\]
\(\textbf{Answer: A} \)
Note:
In the congruence \( x^n \equiv y \pmod{m} \), if \( x \) and \( m \) are not coprime, it is impossible to obtain 1 on the right-hand side. Instead, the sequence of powers will eventually yield 0 or enter a repeating cycle of numbers.
Example:
\[
(18)^{100} \equiv 0 \pmod{64}
\]
QUESTION 8
\[
\text{What is the remainder when } 2^{100} \text{ is divided by 6?}
\]
\[
\text{A) } 1 \quad \text{B) } 2 \quad \text{C) } 3 \quad \text{D) } 4 \quad \text{E) } 5
\]
Solution:
\[
\text{We must evaluate } x \text{ in the congruence } 2^{100} \equiv x \pmod{6}.
\]
Let us list the consecutive powers of 2 modulo 6:
\[
2^1 \equiv 2 \pmod{6}
\]
\[
2^2 \equiv 4 \pmod{6}
\]
\[
2^3 \equiv 2 \pmod{6}
\]
\[
2^4 \equiv 4 \pmod{6}
\]
\[
\vdots
\]
We observe a repeating pattern where odd powers are congruent to 2 and even powers are congruent to 4:
\[
2^{99} \equiv 2 \pmod{6}
\]
\[
2^{100} \equiv 4 \pmod{6} \implies x = 4
\]
\(\textbf{Answer: D} \)
Note: (Euler’s Totient Theorem)
In the congruence \( x^n \equiv y \pmod{m} \), if \( x \) and \( m \) are coprime, let the prime factorization of \( m \) be given by:
\[
m = a^p \cdot b^r \cdot c^s \cdots
\]
Euler’s totient function \( \phi(m) \) (denoted here as \( z \)) is defined as:
\[
z = \phi(m) = m \cdot \left( 1 – \frac{1}{a} \right) \cdot \left( 1 – \frac{1}{b} \right) \cdot \left( 1 – \frac{1}{c} \right) \cdots
\]
Then, it holds that:
\[
x^z \equiv 1 \pmod{m}
\]
QUESTION 9
What is the units digit of the number \( (1997)^{62} \)?
\[
\text{A) } 5 \quad \text{B) } 6 \quad \text{C) } 7 \quad \text{D) } 8 \quad \text{E) } 9
\]
Solution:
The units digit of any integer is equivalent to the remainder obtained when the number is divided by 10.
\[
\text{We need to find } x \text{ in the congruence } (1997)^{62} \equiv x \pmod{10}.
\]
Since \( 1997 \equiv 7 \pmod{10} \):
\[
(1997)^{62} \equiv 7^{62} \pmod{10} \Rightarrow 7^{62} \equiv x \pmod{10}
\]
Using Euler’s totient function for \( m = 10 = 2 \cdot 5 \):
\[
z = \phi(10) = 10 \cdot \left( 1 – \frac{1}{2} \right) \cdot \left( 1 – \frac{1}{5} \right) = 4
\]
By Euler’s theorem:
\[
7^4 \equiv 1 \pmod{10}
\]
\[
(7^4)^{15} \equiv 1^{15} \pmod{10} \implies 7^{60} \equiv 1 \pmod{10}
\]
Multiplying both sides by \( 7^2 \):
\[
7^2 \cdot 7^{60} \equiv 7^2 \cdot 1 \pmod{10}
\]
Since \( 7^2 = 49 \equiv 9 \pmod{10} \):
\[
\Rightarrow 7^{62} \equiv 9 \pmod{10}
\]
Thus, \( x = 9 \).
\(\textbf{Answer: E} \)
QUESTION 10
\[
\text{What is the number formed by the last two digits of } (21)^{202}\text{?}
\]
\[
\text{A) } 01 \quad \text{B) } 21 \quad \text{C) } 41 \quad \text{D) } 61 \quad \text{E) } 81
\]
Solution:
\[
\text{We are looking for } x \text{ in the congruence } (21)^{202} \equiv x \pmod{100}.
\]
Factorizing the modulus: \( m = 100 = 2^2 \cdot 5^2 \).
\[
\Rightarrow z = \phi(100) = 100 \cdot \left( 1 – \frac{1}{2} \right) \cdot \left( 1 – \frac{1}{5} \right) = 40
\]
By Euler’s theorem:
\[
(21)^{40} \equiv 1 \pmod{100}
\]
\[
((21)^{40})^5 \equiv 1^5 \pmod{100} \implies (21)^{200} \equiv 1 \pmod{100}
\]
Multiplying by \( (21)^2 \):
\[
(21)^2 \cdot (21)^{200} \equiv (21)^2 \cdot 1 \pmod{100}
\]
\[
(21)^{202} \equiv 441 \pmod{100}
\]
Since \( 441 \equiv 41 \pmod{100} \):
\[
(21)^{202} \equiv 41 \pmod{100} \implies x = 41
\]
\(\textbf{Answer: C} \)
QUESTION 11
\[
\text{If } 3^{27} + 4^{27} + 6^{27} + (12)^{27} \equiv x \pmod{5} \text{, what is the value of } x \text{?}
\]
\[
\text{A) } 0 \quad \text{B) } 1 \quad \text{C) } 2 \quad \text{D) } 3 \quad \text{E) } 4
\]
Solution:
Reducing the bases modulo 5:
\[
3 \equiv -2 \pmod{5}, \quad 6 \equiv 1 \pmod{5}
\]
\[
4 \equiv -1 \pmod{5}, \quad 12 \equiv 2 \pmod{5}
\]
Substituting these into the expression:
\[
3^{27} + 4^{27} + 6^{27} + (12)^{27} \equiv x \pmod{5}
\]
\[
\Rightarrow (-2)^{27} + (-1)^{27} + 1^{27} + 2^{27} \equiv x \pmod{5}
\]
Since \( (-2)^{27} = -(2^{27}) \) and \( (-1)^{27} = -1 \), the symmetric terms cancel out term by term:
\[
\Rightarrow 0 \equiv x \pmod{5} \implies x = 0
\]
\(\textbf{Answer: A} \)
← Previous Page | Next Page →