Skip to content

Number Theory Practice (Interactive)

Intuition

The mathematics of whole numbers: Number theory studies the properties of integers, prime numbers, divisibility, modular arithmetic. It is the oldest branch of mathematics, and surprisingly, it is the foundation of modern cryptography (RSA, Diffie-Hellman).

Why it matters: Number theory underpins internet security, your online banking, HTTPS connections, and digital signatures all rely on the difficulty of factoring large numbers or solving discrete logarithm problems.

The key insight: Primes are the “atoms” of arithmetic, every integer factors uniquely into primes (Fundamental Theorem of Arithmetic). This uniqueness is what makes factoring hard and cryptography secure.

University Mathematics, Number Theory Practice

10 auto-graded practice problems at medium to hard difficulty. Select an answer, submit, and review the explanation.

Divisibility and Primes

Modular Arithmetic and Quadratic Reciprocity

Diophantine Equations and Advanced Topics

Common Mistakes

Applying Fermat’s little theorem without checking the primality condition: Fermat’s little theorem ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p} requires pp to be prime and gcd⁡(a,p)=1\gcd(a, p) = 1. If pp is composite (e.g., 2340≡1(mod341)2^{340} \equiv 1 \pmod{341} even though 341 = 11 × 31), the theorem does not apply. Use Euler’s theorem aϕ(n)≡1(modn)a^{\phi(n)} \equiv 1 \pmod{n} for composite moduli.

Confusing complete and reduced residue systems: A complete residue system modulo mm contains one representative from each equivalence class (e.g., {0,1,2,3,4}\{0, 1, 2, 3, 4\} mod 5). A reduced residue system contains only those coprime to mm (e.g., {1,2,3,4}\{1, 2, 3, 4\} mod 5). The size of a reduced system is ϕ(m)\phi(m), not mm.

Misapplying the Chinese Remainder Theorem to non-coprime moduli: CRT requires the moduli to be pairwise coprime. For x≡2(mod4)x \equiv 2 \pmod{4} and x≡1(mod6)x \equiv 1 \pmod{6}, you cannot directly combine them because gcd⁡(4,6)=2≠1\gcd(4, 6) = 2 \neq 1. Check consistency first: 2≡1(mod2)2 \equiv 1 \pmod{2} must hold, which it does not, so no solution exists.

Cross-References

  • Site Home: Main landing page for Mathematics notes.
  • Linear Algebra: Vector spaces, matrices, and linear transformations.
  • Real Analysis: Rigorous treatment of real numbers and calculus.
  • Practice: Practice problems for revision.