Modular Arithmetic
Congruences, Fermat's little theorem, Chinese remainder theorem, and number bases
Key Concepts
- Congruence a ≡ b (mod m) means m divides (a − b)
- You can add and multiply congruences term by term
- Fermat's little theorem simplifies large powers modulo a prime
- The Chinese Remainder Theorem combines congruences with coprime moduli
Important Formulae
| Fermat's little theorem | a^(p−1) ≡ 1 (mod p), p prime, gcd(a,p)=1 |
| Wilson's theorem | (p−1)! ≡ −1 (mod p) |
| Euler's theorem | a^φ(n) ≡ 1 (mod n), gcd(a,n)=1 |
Quick Tips
- For last-digit problems, work modulo 10.
- Reduce large exponents using Fermat's or Euler's theorem before computing.
Sample Practice Questions
-
What is the remainder when 2^100 is divided by 3?
Show answer
Answer: 1
-
What is the last digit of 7^2024?
Show answer
Answer: 1
-
The sum 1 + 2 + 4 + 8 + ... + 2^n mod 3 cycles as:
Show answer
Answer: 1, 0, 1, 0, ...
-
If gcd(a, m) = 1, a has a multiplicative inverse mod m. This inverse is:
Show answer
Answer: Unique mod m
Practice Questions
Practise PRMO questions on Modular Arithmetic. Answers are revealed after each question.
Start Practice →Frequently Asked Questions
What are the key concepts in Modular Arithmetic for PRMO?
Congruence a ≡ b (mod m) means m divides (a − b); You can add and multiply congruences term by term; Fermat's little theorem simplifies large powers modulo a prime; The Chinese Remainder Theorem combines congruences with coprime moduli.
Which formulae are important for Modular Arithmetic in PRMO?
Fermat's little theorem: a^(p−1) ≡ 1 (mod p), p prime, gcd(a,p)=1; Wilson's theorem: (p−1)! ≡ −1 (mod p); Euler's theorem: a^φ(n) ≡ 1 (mod n), gcd(a,n)=1.
How can I practise PRMO Modular Arithmetic questions for free?
Practise free PRMO Modular Arithmetic questions with instant answers and explanations on Safe Learning for Kids — no sign-up required.