Binary operations and modular arithmetic are powerful tools of discrete mathematics, widely used in number theory, cryptography, and computer science. On the YÖS exam, these topics test your ability to work with algebraic structures and perform computations modulo a given number.
Definition: A binary operation on a set $A$ is a function $*: A \times A \to A$ that assigns to each ordered pair $(a, b)$ of elements of $A$ exactly one element $c = a * b$ of $A$.
Notation: $a * b$ or $a \circ b$ or any other symbol
Important property: The result of the operation always belongs to the set $A$ (closure).
Example 1: Addition on the set of natural numbers: $+: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$- $3 + 5 = 8$ (the result is in $\mathbb{N}$)
Example 2: Multiplication on the set of integers: $\cdot: \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}$- $(-2) \cdot 3 = -6$ (the result is in $\mathbb{Z}$)
Example 3: Subtraction on the set of natural numbers: $-: \mathbb{N} \times \mathbb{N} \to \mathbb{Z}$- This is NOT a binary operation on $\mathbb{N}$, since $3 - 5 = -2 \notin \mathbb{N}$
Example 4: Maximum on the set of integers: $\max(a, b)$- $\max(3, 7) = 7$ (binary operation)
Union of sets: $\cup: \mathcal{P}(A) \times \mathcal{P}(A) \to \mathcal{P}(A)$
Intersection of sets: $\cap: \mathcal{P}(A) \times \mathcal{P}(A) \to \mathcal{P}(A)$
String concatenation: On the set of all strings, the operation of joining two strings into one
Definition: A set $A$ is closed under the operation $*$ if for any $a, b \in A$ we have $a * b \in A$.
Example 5:- The set of even integers is closed under addition: $(2k_1) + (2k_2) = 2(k_1 + k_2)$ — an even number- The set of integers is closed under multiplication
Counterexample:- The set of natural numbers is NOT closed under subtraction: $3 - 5 = -2 \notin \mathbb{N}$
Definition: An operation $*$ is called commutative if for all $a, b \in A$ we have:$$a * b = b * a$$
Examples of commutative operations:- Addition on $\mathbb{R}$: $a + b = b + a$- Multiplication on $\mathbb{R}$: $a \cdot b = b \cdot a$- Maximum: $\max(a, b) = \max(b, a)$
Examples of non-commutative operations:- Subtraction on $\mathbb{Z}$: $5 - 3 = 2$, but $3 - 5 = -2 \neq 2$- Division on $\mathbb{Q} \setminus \{0\}$: $8 / 4 = 2$, but $4 / 8 = 0.5 \neq 2$
Definition: An operation $*$ is called associative if for all $a, b, c \in A$ we have:$$(a * b) * c = a * (b * c)$$
Examples of associative operations:- Addition on $\mathbb{R}$: $(a + b) + c = a + (b + c)$- Multiplication on $\mathbb{R}$: $(a \cdot b) \cdot c = a \cdot (b \cdot c)$
Examples of non-associative operations:- Subtraction on $\mathbb{Z}$: $(10 - 5) - 2 = 3$, but $10 - (5 - 2) = 7 \neq 3$- Division on $\mathbb{Q} \setminus \{0\}$: $(16 / 4) / 2 = 2$, but $16 / (4 / 2) = 8 \neq 2$- Exponentiation: $(2^2)^3 = 64$, but $2^{2^3} = 256 \neq 64$
Definition: We say that the operation $*$ is distributive over the operation $\circ$ if:$$a * (b \circ c) = (a * b) \circ (a * c)$$
Example 6: Multiplication is distributive over addition:$$a \cdot (b + c) = a \cdot b + a \cdot c$$
Definition: An element $e \in A$ is called the identity (or neutral) element with respect to the operation $*$ if for all $a \in A$ we have:$$a * e = e * a = a$$
Examples of identity elements:- For addition on $\mathbb{R}$: the identity element is $e = 0$, since $a + 0 = 0 + a = a$- For multiplication on $\mathbb{R}$: the identity element is $e = 1$, since $a \cdot 1 = 1 \cdot a = a$
Important property: The identity element, if it exists, is unique.
Proof: Suppose there are two identity elements $e_1$ and $e_2$. Then:$$e_1 = e_1 * e_2 = e_2$$
Definition: For an element $a \in A$, an element $a^{-1} \in A$ is called the inverse element if:$$a * a^{-1} = a^{-1} * a = e$$
where $e$ is the identity element of the operation $*$.
Examples of inverse elements:
For addition on $\mathbb{R}$ (where $e = 0$):- The inverse of 5 is $5^{-1} = -5$, since $5 + (-5) = 0$- The inverse of $-3$ is $(-3)^{-1} = 3$, since $(-3) + 3 = 0$
For multiplication on $\mathbb{R} \setminus \{0\}$ (where $e = 1$):- The inverse of 4 is $4^{-1} = \frac{1}{4}$, since $4 \cdot \frac{1}{4} = 1$- The inverse of $\frac{2}{3}$ is $(\frac{2}{3})^{-1} = \frac{3}{2}$, since $\frac{2}{3} \cdot \frac{3}{2} = 1$
The inverse element does not exist for every element of the set.
Example 7: On the set of natural numbers $\mathbb{N}$ with the operation of addition:- Identity element: $e = 0$ (if 0 is considered a natural number)- The inverse of 5 does not exist in $\mathbb{N}$, since $5 + a = 0$ requires $a = -5 \notin \mathbb{N}$
Definition: A Cayley table (or operation table) is a table that shows the results of an operation for all pairs of elements of a finite set.
Consider the operation on the set $\{0, 1, 2, 3\}$ that performs addition modulo 4 (the remainder upon division by 4):
| $+_4$ | 0 | 1 | 2 | 3 ||-------|---|---|---|---|| 0 | 0 | 1 | 2 | 3 || 1 | 1 | 2 | 3 | 0 || 2 | 2 | 3 | 0 | 1 || 3 | 3 | 0 | 1 | 2 |
For example: $3 +_4 2 = 5 \mod 4 = 1$
The Cayley table allows you to:- Easily find the result of an operation- Check commutativity (the table is symmetric about the diagonal)- Find the identity element (the row/column with the original elements)- Find inverse elements
Definition: Two integers $a$ and $b$ are called congruent modulo $n$ (denoted $a \equiv b \pmod{n}$) if their difference is divisible by $n$:$$a \equiv b \pmod{n} \Leftrightarrow n | (a - b)$$
Equivalently: $a$ and $b$ give the same remainder upon division by $n$.
Examples:- $17 \equiv 5 \pmod{12}$, since $17 - 5 = 12$, which is divisible by 12- $-3 \equiv 7 \pmod{10}$, since $-3 - 7 = -10$, which is divisible by 10- $25 \equiv 1 \pmod{4}$, since both give remainder 1 upon division by 4
Definition: The residue class of a number $a$ modulo $n$ is the set of all integers congruent to $a$ modulo $n$.
Notation: $[a]_n$ or $\bar{a}$
Formally: $[a]_n = \{x \in \mathbb{Z} \mid a \equiv x \pmod{n}\}$
Example 8: The residue class of 2 modulo 5:$$[2]_5 = \{..., -8, -3, 2, 7, 12, 17, ...\}$$
These are all numbers of the form $2 + 5k$, where $k \in \mathbb{Z}$.
Definition: A complete residue system modulo $n$ is a set of $n$ integers, one from each residue class.
Examples:- For $n = 5$: $\{0, 1, 2, 3, 4\}$ or $\{-2, -1, 0, 1, 2\}$ (one must choose 5 numbers from different classes)
Definition: The remainder upon division of a number $a$ by a number $n$ (denoted $a \mod n$) is the number $r$ such that:$$a = q \cdot n + r, \text{ where } 0 \leq r < n$$
where $q$ is the integer quotient of $a$ divided by $n$.
Examples:- $17 \mod 5 = 2$, since $17 = 3 \cdot 5 + 2$- $-7 \mod 3 = 2$, since $-7 = (-3) \cdot 3 + 2$ (the remainder is always non-negative)- $25 \mod 5 = 0$, since $25 = 5 \cdot 5 + 0$
Connection with the $\equiv$ symbol:$$a \equiv b \pmod{n} \Leftrightarrow a \mod n = b \mod n$$
$$a \equiv a \pmod{n}$$
Proof: $a - a = 0$, which is divisible by $n$.
If $a \equiv b \pmod{n}$, then $b \equiv a \pmod{n}$
Proof: $a - b = -(b - a)$, and if $n | (a - b)$, then $n | (b - a)$.
If $a \equiv b \pmod{n}$ and $b \equiv c \pmod{n}$, then $a \equiv c \pmod{n}$
Proof:$$a - c = (a - b) + (b - c)$$If $n | (a - b)$ and $n | (b - c)$, then $n | (a - c)$.
If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$, then $a + c \equiv b + d \pmod{n}$
Example 9: $17 \equiv 5 \pmod{12}$ and $20 \equiv 8 \pmod{12}$$$17 + 20 = 37 \equiv 1 \pmod{12}$$$$5 + 8 = 13 \equiv 1 \pmod{12}$$ ✓
If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$, then $a \cdot c \equiv b \cdot d \pmod{n}$
Example 10: $17 \equiv 5 \pmod{12}$ and $3 \equiv 3 \pmod{12}$$$17 \cdot 3 = 51 \equiv 3 \pmod{12}$$$$5 \cdot 3 = 15 \equiv 3 \pmod{12}$$ ✓
If $a \equiv b \pmod{n}$, then $ka \equiv kb \pmod{n}$ for any integer $k$
$$(a + b) \mod n = ((a \mod n) + (b \mod n)) \mod n$$
Example 11: Find $(45 + 38) \mod 13$.
Solution:$$45 \mod 13 = 6 \text{ (since } 45 = 3 \cdot 13 + 6)$$$$38 \mod 13 = 12 \text{ (since } 38 = 2 \cdot 13 + 12)$$$$(45 + 38) \mod 13 = (6 + 12) \mod 13 = 18 \mod 13 = 5$$
Verification: $83 = 6 \cdot 13 + 5$, so $83 \mod 13 = 5$ ✓
$$(a - b) \mod n = ((a \mod n) - (b \mod n) + n) \mod n$$
(We add $n$ to avoid negative remainders)
Example 12: Find $(23 - 45) \mod 13$.
Solution:$$23 \mod 13 = 10$$$$45 \mod 13 = 6$$$$(23 - 45) \mod 13 = (10 - 6 + 13) \mod 13 = 17 \mod 13 = 4$$
Verification: $-22 = -2 \cdot 13 + 4$, so $-22 \mod 13 = 4$ ✓
$$(a \cdot b) \mod n = ((a \mod n) \cdot (b \mod n)) \mod n$$
Example 13: Find $(47 \cdot 53) \mod 17$.
Solution:$$47 \mod 17 = 13 \text{ (since } 47 = 2 \cdot 17 + 13)$$$$53 \mod 17 = 2 \text{ (since } 53 = 3 \cdot 17 + 2)$$$$(47 \cdot 53) \mod 17 = (13 \cdot 2) \mod 17 = 26 \mod 17 = 9$$
Verification: $47 \cdot 53 = 2491 = 146 \cdot 17 + 9$, so $2491 \mod 17 = 9$ ✓
$$(a^k) \mod n = ((a \mod n)^k) \mod n$$
For large powers, fast exponentiation methods are used.
Example 14: Find $2^{10} \mod 7$.
Solution:
Method 1 (direct computation):$$2^{10} = 1024 = 146 \cdot 7 + 2$$$$2^{10} \mod 7 = 2$$
Method 2 (step-by-step computation):- $2^1 \equiv 2 \pmod{7}$- $2^2 \equiv 4 \pmod{7}$- $2^3 \equiv 8 \equiv 1 \pmod{7}$
Since $2^3 \equiv 1 \pmod{7}$ and $10 = 3 \cdot 3 + 1$:$$2^{10} = 2^{9+1} = (2^3)^3 \cdot 2 \equiv 1^3 \cdot 2 \equiv 2 \pmod{7}$$
The last digit of a number is the remainder upon division by 10, i.e., $a \mod 10$.
Example 15: Find the last digit of the number $7^{100}$.
Let us find the pattern in the last digits of the powers of 7:- $7^1 = 7$ (last digit 7)- $7^2 = 49$ (last digit 9)- $7^3 = 343$ (last digit 3)- $7^4 = 2401$ (last digit 1)- $7^5 = 16807$ (last digit 7)
We see that the last digits repeat with period 4: 7, 9, 3, 1, 7, 9, 3, 1, ...
$100 = 25 \cdot 4$, so $7^{100}$ has the same last digit as $7^4$.
Answer: the last digit of $7^{100}$ is 1
Alternative solution: Using modular arithmetic:$$7^4 \equiv 1 \pmod{10}$$$$7^{100} = (7^4)^{25} \equiv 1^{25} \equiv 1 \pmod{10}$$
Last digit: 1
On the set $A = \{1, 3, 5, 7, 9\}$ the operation of multiplication modulo 10 is defined. Is $A$ closed under this operation?
Let us check all pairs:- $1 \cdot 1 = 1 \equiv 1 \pmod{10}$ ✓- $1 \cdot 3 = 3 \equiv 3 \pmod{10}$ ✓- $3 \cdot 3 = 9 \equiv 9 \pmod{10}$ ✓- $3 \cdot 5 = 15 \equiv 5 \pmod{10}$ ✓- $3 \cdot 7 = 21 \equiv 1 \pmod{10}$ ✓- $3 \cdot 9 = 27 \equiv 7 \pmod{10}$ ✓- $5 \cdot 5 = 25 \equiv 5 \pmod{10}$ ✓- $5 \cdot 7 = 35 \equiv 5 \pmod{10}$ ✓- $5 \cdot 9 = 45 \equiv 5 \pmod{10}$ ✓- $7 \cdot 7 = 49 \equiv 9 \pmod{10}$ ✓- $7 \cdot 9 = 63 \equiv 3 \pmod{10}$ ✓- $9 \cdot 9 = 81 \equiv 1 \pmod{10}$ ✓
All results are in $A$, so yes, the set $A$ is closed.
On the set $\{0, 1, 2\}$ the operation $*$ is defined by the table:
| $*$ | 0 | 1 | 2 ||-----|---|---|---|| 0 | 0 | 1 | 2 || 1 | 1 | 1 | 2 || 2 | 2 | 2 | 2 |
a) Is the operation commutative?b) Find the identity element (if it exists)
a) The table is not symmetric about the diagonal: for example, $0 * 1 = 1$, but $1 * 0 = 1$ (they match). Let us check all:- $0 * 1 = 1$ and $1 * 0 = 1$ ✓- $0 * 2 = 2$ and $2 * 0 = 2$ ✓- $1 * 2 = 2$ and $2 * 1 = 2$ ✓
The operation is commutative ✓
b) The identity element $e$ must satisfy $a * e = e * a = a$ for all $a$:- For the element 0: we need $0 * e = 0$. This holds for all $e$, but we also need $1 * e = 1$. We see: $1 * 0 = 1$, $1 * 1 = 1$, $1 * 2 = 2$. If $e = 0$, then $1 * 0 = 1$ ✓, and $2 * 0 = 2$ ✓, $0 * 2 = 2$ ✓. Let us check $e = 0$ completely: - $0 * 0 = 0$ ✓, $1 * 0 = 1$ ✓, $2 * 0 = 2$ ✓ - $0 * 0 = 0$ ✓, $0 * 1 = 1$ ✓, $0 * 2 = 2$ ✓
Identity element: $e = 0$
What remainder do the numbers $3^5 \cdot 4^2 + 15$ give upon division by 7?
$$3^5 \cdot 4^2 + 15 \equiv ? \pmod{7}$$
Let us compute each term:- $3^5 \pmod{7}$: - $3^1 \equiv 3 \pmod{7}$ - $3^2 \equiv 9 \equiv 2 \pmod{7}$ - $3^3 \equiv 3 \cdot 2 \equiv 6 \pmod{7}$ - $3^4 \equiv 3 \cdot 6 \equiv 18 \equiv 4 \pmod{7}$ - $3^5 \equiv 3 \cdot 4 \equiv 12 \equiv 5 \pmod{7}$
Answer: remainder 4
Find the last digit of the number $2^{2024}$.
The last digit is the remainder upon division by 10.
Let us find the period for the last digits of powers of 2:- $2^1 = 2$- $2^2 = 4$- $2^3 = 8$- $2^4 = 16$ (last digit 6)- $2^5 = 32$ (last digit 2)
We see that the last digits repeat with period 4: 2, 4, 8, 6, 2, 4, 8, 6, ...
$2024 = 506 \cdot 4$, so $2^{2024}$ has the same last digit as $2^4$.
Answer: the last digit of $2^{2024}$ is 6
Find a number that gives remainder 3 upon division by 5 and remainder 4 upon division by 7.
We need to find $x$ such that:$$x \equiv 3 \pmod{5}$$$$x \equiv 4 \pmod{7}$$
From the first condition: $x = 5k + 3$ for some integer $k$.
Substitute into the second condition:$$5k + 3 \equiv 4 \pmod{7}$$$$5k \equiv 1 \pmod{7}$$
Let us find the inverse of 5 modulo 7. Check:- $5 \cdot 1 = 5 \equiv 5 \pmod{7}$- $5 \cdot 2 = 10 \equiv 3 \pmod{7}$- $5 \cdot 3 = 15 \equiv 1 \pmod{7}$ ✓
Inverse of 5: $5^{-1} \equiv 3 \pmod{7}$
$$k \equiv 3 \cdot 1 \equiv 3 \pmod{7}$$
Therefore $k = 7m + 3$ for some integer $m$.
$$x = 5(7m + 3) + 3 = 35m + 15 + 3 = 35m + 18$$
The smallest positive solution: $x = 18$
Verification:- $18 = 3 \cdot 5 + 3$ ✓- $18 = 2 \cdot 7 + 4$ ✓
Answer: $x = 18$ (or any number of the form $18 + 35n$, where $n$ is an integer)
### Mistake 1: Forgetting closure when defining an operationIncorrect: Subtraction is a binary operation on $\mathbb{N}$.Correct: Subtraction is NOT a binary operation on $\mathbb{N}$, since $3 - 5 = -2 \notin \mathbb{N}$.
### Mistake 2: Confusing $\mod$ and $\equiv$Incorrect: $17 \mod 5 \equiv 2$ (mixing an operation and a relation)Correct: $17 \mod 5 = 2$ (the result of the operation) or $17 \equiv 2 \pmod{5}$ (the relation)
### Mistake 3: Forgetting to add $n$ in subtraction moduloIncorrect: $(3 - 7) \mod 5 = -4 \mod 5 = -4$Correct: $(3 - 7) \mod 5 = (-4 + 5) \mod 5 = 1$
### Mistake 4: Incorrect application of the properties of modular arithmeticIncorrect: $(a + b) \mod n = (a \mod n) + (b \mod n)$ (sometimes greater than $n$)Correct: $(a + b) \mod n = ((a \mod n) + (b \mod n)) \mod n$
### Mistake 5: Forgetting about commutativity when using the Cayley tableIncorrect: Assuming an operation is commutative without checking.Correct: Check that the table is symmetric about the diagonal.
### Mistake 6: Incorrect definition of the identity elementIncorrect: $e$ is identity if $a * e = a$ (forgot $e * a = a$)Correct: $e$ is identity if $a * e = e * a = a$ for all $a$.
### Tip 1: Visualizing Cayley tablesWhen working with Cayley tables:- Highlight the row and column of the identity element (they contain all elements of the set)- Check the symmetry of the table (commutativity)
### Tip 2: Using periodicity in exponentiation moduloFind when the powers repeat:$$a^k \equiv a^{k \mod \phi(n)} \pmod{n}$$where $\phi(n)$ is Euler's totient function
### Tip 3: Checking remainders by hand for small moduliFor moduli up to 10 it is often possible to perform computations by hand and verify the result.
### Tip 4: Using associativity to simplify computationsAssociativity implies that the order of grouping does not matter:$$(2 \cdot 3) \cdot 4 = 2 \cdot (3 \cdot 4)$$
### Tip 5: Checking inverse elementsTo check whether $b$ is the inverse of $a$, compute $a * b$ and verify that it equals the identity element.
### Tip 6: Organized computation for Cayley tablesWhen filling out a Cayley table:1. First fill the row and column of the identity element2. Then use symmetry (if the operation is commutative)3. Fill in the remaining cells
### Tip 7: Attention to cyclic groupsIf $a^k \equiv 1 \pmod{n}$ for small $k$, use this to simplify large powers.
### Tip 8: Transforming into a more convenient formOften one can rewrite an expression in a more convenient form:$$2^{10} = 2^8 \cdot 2^2 = 256 \cdot 4$$
### Tip 9: Checking associativity on examplesIf you are unsure about associativity, check on specific examples:$$(a * b) * c \stackrel{?}{=} a * (b * c)$$
### Tip 10: Practice with specific moduliLearn the "good" moduli for particular operations:- Modulus 2 (parity)- Modulus 10 (last digit)- Modulus 9 (digit sum)
---
Conclusion
Operations and modular arithmetic are powerful tools for solving problems in discrete mathematics. Understanding these concepts facilitates computations and helps identify patterns in numerical sequences.
All course topics · Practice problems
Please enable JavaScript to use the practice app.