Number Theory Lab

Mathematical Principles & Theorems

Investigates core theorems in arithmetic and algebraic number theory: (1) Euclidean algorithm: \(\gcd(a, b) = \gcd(b, a \bmod b)\); (2) Extended Euclidean algorithm computes Bézout coefficients \(x, y\) such that \(ax + by = \gcd(a, b)\); (3) Modular multiplicative inverse \(a^{-1} \pmod m\) exists iff \(\gcd(a, m) = 1\); (4) Euler's totient \(\phi(n) = n\prod_{p|n}(1-1/p)\) and Euler's Theorem \(a^{\phi(n)} \equiv 1 \pmod n\); (5) Chinese Remainder Theorem (CRT) unique solution modulo \(\prod m_i\).

Operating Instructions

• Enter integer operands \(a, b\) and modulus \(m\) in the parameter inputs.
• Select number theory module: GCD / Extended Euclidean, Modular Inverse, Euler Totient, or CRT Solver.
• Click Compute to obtain exact integer solutions and step-by-step Euclidean division lattices.
• Review prime power factorizations and modular congruence proofs.