≡

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

  1. The number of solutions to x² ≡ 1 (mod p) for odd prime p is:

    • 0
    • 1
    • 2
    • p-1
    Show answer

    Answer: 2

  2. Euler's theorem: if gcd(a, n) = 1, then a^φ(n) ≡ ? (mod n)

    • 0
    • 1
    • a
    • n - 1
    Show answer

    Answer: 1

  3. Convert 255 to hexadecimal.

    • EF
    • FE
    • FF
    • F0
    Show answer

    Answer: FF

  4. The Chinese Remainder Theorem guarantees a unique solution modulo:

    • Sum of the moduli
    • Product of the moduli
    • lcm of the moduli (when moduli are pairwise coprime)
    • GCD of the moduli
    Show answer

    Answer: lcm of the moduli (when moduli are pairwise coprime)

Practise more questions →
Practice Questions

Practise PRMO questions on Modular Arithmetic. Answers are revealed after each question.

Start Practice →
Number Theory