matura.mkCongruences
Modular arithmetic, remainders of powers, last digits and Fermat's little theorem. 6 problems with step-by-step solutions.
Solve each problem in your notebook first, then open the solution.
Problem 1 Congruences
a) Find all \(m > 1\) with \(29 \equiv 5 \pmod m\).
b) Today is Monday. What day will it be in 100 days?
c) Calculate in clock (mod 12) arithmetic: \(9 + 7\), \(5 - 9\), \(4\cdot 7\).
Show solution
a) \(m\) divides \(29 - 5 = 24\): \(m \in \{2, 3, 4, 6, 8, 12, 24\}\).
b) \(100 = 14\cdot 7 + 2\): two days after Monday is Wednesday.
c) \(16 \equiv 4\); \(-4 \equiv 8\); \(28 \equiv 4\).
Problem 2 Remainders of powers
a) Find the remainder when \(17^{40}\) is divided by 8.
b) Find the remainder when \(3^{100}\) is divided by 7.
c) Find the remainder when \(5^{23} + 4^{15}\) is divided by 9.
Show solution
a) \(17 \equiv 1 \pmod 8\), so \(17^{40} \equiv 1\).
b) \(3^6 \equiv 1 \pmod 7\), \(100 = 6\cdot 16 + 4\): \(3^4 = 81 \equiv 4\).
c) \(5^6 \equiv 1 \pmod 9\) and \(5^{23} = 5^{18}\cdot 5^5 \equiv 5^5 = 3125 \equiv 2\). \(4^3 = 64 \equiv 1\), so \(4^{15} \equiv 1\). Sum: 3.
Problem 3 Last digit
Find the last digit of a) \(7^{2025}\) b) \(13^{48}\) c) \(2^{2026} + 3^{2026}\).
Show solution
The last digit is the remainder mod 10.
a) Last digits of \(7^n\) repeat 7, 9, 3, 1 (period 4). \(2025 \equiv 1 \pmod 4\): 7.
b) \(3^n\): 3, 9, 7, 1. \(48 \equiv 0\): 1.
c) \(2026 \equiv 2 \pmod 4\): \(2^n\) ends in 4, \(3^n\) ends in 9. \(4 + 9 = 13\): 3.
Problem 4 Solving congruences
a) Solve \(x + 4 \equiv 1 \pmod 6\).
b) Find the smallest two-digit number with \(3x - 2 \equiv 4 \pmod 9\).
c) Prove that \(10^n - 1\) is divisible by 9 for all \(n \in \mathbb{N}\).
Show solution
a) \(x \equiv -3 \equiv 3 \pmod 6\): \(x = 6k + 3\).
b) \(3x \equiv 6 \pmod 9\) means \(9 \mid 3(x - 2)\), i.e. \(x \equiv 2 \pmod 3\). The smallest two-digit: 11.
c) \(10 \equiv 1 \pmod 9\), so \(10^n \equiv 1\) and \(10^n - 1 \equiv 0\).
Problem 5 Fermat's little theorem
If \(p\) is prime and \(p \nmid a\), then \(a^{p - 1} \equiv 1 \pmod p\).
a) Find the remainder when \(6^{50}\) is divided by 11.
b) Find the remainder when \(2^{40}\) is divided by 13.
c) Show that \(5^{30} - 1\) is divisible by 31.
Show solution
a) \(6^{10} \equiv 1 \pmod{11}\), so \(6^{50} \equiv 1\).
b) \(2^{12} \equiv 1 \pmod{13}\), \(40 = 36 + 4\): \(2^4 = 16 \equiv 3\).
c) 31 is prime and does not divide 5: \(5^{30} \equiv 1 \pmod{31}\).
Problem 6 Sum of powers
Find the remainder when \(1^5 + 2^5 + \dots + 10^5\) is divided by 11.
Show solution
Mod 11, \(11 - k \equiv -k\), and the fifth power is odd: \((11 - k)^5 \equiv -k^5\). Pair \(1\) with \(10\), \(2\) with \(9\), …, \(5\) with \(6\): each pair gives 0. Remainder 0.