Modular Arithmetic Calculator

Two integers are congruent modulo $n$ if they differ by a multiple of $n$. We write $a \equiv b \pmod{n}$ when $n \mid (a - b)$.

The four basic operations carry through: addition, subtraction, and multiplication all respect congruences. Fast exponentiation uses binary squaring to compute $a^b \bmod n$ in $O(\log b)$ steps.

The modular inverse of $a$ modulo $n$ is the value $a^{-1}$ such that $a \cdot a^{-1} \equiv 1 \pmod{n}$. It exists if and only if $\gcd(a, n) = 1$.

The extended Euclidean algorithm finds integers $x, y$ such that $ax + ny = \gcd(a,n) = 1$, giving $x$ as the inverse. This runs in $O(\log n)$ time.

If $m_1, m_2, \ldots, m_k$ are pairwise coprime, then the system of congruences $x \equiv r_i \pmod{m_i}$ has a unique solution modulo $M = m_1 m_2 \cdots m_k$.

The solution is built iteratively: merge two congruences at a time using the extended Euclidean algorithm, doubling the modulus at each step.

Modular arithmetic underpins modern cryptography. In RSA, encryption is $c \equiv m^e \pmod{n}$ and decryption uses $m \equiv c^d \pmod{n}$, where $n = pq$ is a product of large primes.

Euler's totient $\varphi(n)$ counts integers coprime to $n$. For RSA: $\varphi(pq) = (p-1)(q-1)$. The key insight is Euler's theorem: $a^{\varphi(n)} \equiv 1 \pmod{n}$ for $\gcd(a,n)=1$.

Caesar and affine ciphers use $\mathbb{Z}_{26}$ (mod 26). The CRT helps reconstruct large integers from their residues, used in efficient multi-prime RSA.