First, solve the first two congruences:
["# Solving the First Two Congruences: Mastering the Basics of Modular Arithmetic", "In the world of number theory, solving congruences is a fundamental skill with wide-ranging applications in cryptography, computer science, and algorithm design. Whether you're working on cryptographic protocols or solving classic math problems, understanding how to solve simultaneous congruences—especially the first two—is both powerful and essential. This article walks you through solving the first two congruences using the Chinese Remainder Theorem (CRT) and basic modular arithmetic, giving you the tools to unlock deeper mathematical reasoning.", "## What Are Congruences?", "A congruence is an equation that describes a relationship between two numbers with respect to a modulus. Formally, we write:", "[ x \equiv a \pmod{m} ]", "This statement means that when ( x ) is divided by ( m ), the remainder is ( a ). Equivalently, ( m ) divides ( x - a ).", "Solving congruences involves finding all integers ( x ) that satisfy one or more such equations—especially when those equations share the same modulus or can be combined.", "## The First Step: Solving the First Congruence", "Let’s suppose our first congruence is:", "[ x \equiv a \pmod{m} ]", "This means all solutions are of the form:", "[ x = a + km ]", "for some integer ( k ). No algebraic simplification is needed here—this is the general solution. You can plug in any integer ( k ) to generate values of ( x ) that satisfy the congruence.", "For example, if ( x \equiv 2 \pmod{5} ), solutions include:\n[ x = 2,\ 7,\ 12,\ 17,\ 22,\ \dots ]", "## Step Two: Introducing the Second Congruence", "Now suppose we are given a second congruence:", "[ x \equiv b \pmod{n} ]", "Our goal is to find a common solution that satisfies both congruences:", "[ x \equiv a \pmod{m} ]\n[ x \equiv b \pmod{n} ]", "This is where the Chinese Remainder Theorem (CRT) becomes invaluable—provided ( m ) and ( n ) are coprime (i.e., ( \gcd(m, n) = 1 )). If they are not coprime, the system may have no solution or multiple solutions, which we’ll touch on shortly.", "Assuming ( \gcd(m, n) = 1 ), CRT guarantees a unique solution modulo ( mn ).", "## Using the Chinese Remainder Theorem", "We seek ( x ) such that:", "1. ( x \equiv a \pmod{m} )\n2. ( x \equiv b \pmod{n} )", "We construct the solution by finding integers ( k ) and ( l ) such that:", "[ x = a + km = b + ln ]", "Rewriting,\n[ km - ln = b - a ]", "This is a linear Diophantine equation in ( k ) and ( l ). Since ( m ) and ( n ) are coprime, integer solutions exist. We use modular inverses to solve for integers.", "A practical method involves finding a number ( t ) satisfying:\n[ t \equiv a \pmod{m} ]\n[ t \equiv b \pmod{n} ]", "One technique is to:\n- Solve ( t = a + km ) for some ( k ), then substitute into the second congruence:\n[ a + km \equiv b \pmod{n} ]\n[ km \equiv b - a \pmod{n} ]\n[ km \equiv d \pmod{n} \quad \ ext{where } d = b - a ]", "Since ( \gcd(m, n) = 1 ), ( m ) has a multiplicative inverse modulo ( n ). Let ( m^{-1} ) be the inverse of ( m ) mod ( n ), so:\n[ k \equiv d \cdot m^{-1} \pmod{n} ]", "Thus,\n[ k = d m^{-1} + tn \quad \ ext{for some integer } t ]", "Substitute back:\n[ x = a + m k = a + m(d m^{-1} + tn) = a + m d m^{-1} + m t n ]", "But since ( m d m^{-1} \equiv d \pmod{n} ), and noting that the solution is periodic modulo ( mn ), the unique solution modulo ( mn ) is:\n[ x \equiv a \cdot n \cdot (m^{-1} \bmod n) + b \cdot m \cdot (n^{-1} \bmod n) \pmod{mn} ]", "However, in most cases, it's simpler to compute the solution using:", "[ x \equiv a \cdot n \cdot y + b \cdot m \cdot z \pmod{mn} ]", "where ( y \equiv m^{-1} \pmod{n} ), ( z \equiv n^{-1} \pmod{m} )—but this becomes messy without explicit inverses.", "An easier computational approach:\n1. Find integers ( u ) and ( v ) such that ( m u + n v = 1 ) (by Extended Euclidean Algorithm).\n2. Then the simultaneous solution is:\n[ x \equiv a n u + b m v \pmod{mn} ]", "This formula guarantees a solution modulo ( mn ) when ( \gcd(m, n) = 1 ).", "## Practical Example", "Let’s solve:\n[ x \equiv 2 \pmod{5} ]\n[ x \equiv 3 \pmod{7} ]", "Step 1: Solve first congruence.\n[ x = 2 + 5k \quad \ ext{for any integer } k ]", "Step 2: Substitute into second:\n[ 2 + 5k \equiv 3 \pmod{7} ]\n[ 5k \equiv 1 \pmod{7} ]", "Find ( 5^{-1} \mod 7 ): try values:\n( 5 \cdot 3 = 15 \equiv 1 \pmod{7} ), so inverse is 3.", "Thus,\n[ k \equiv 3 \cdot 1 \equiv 3 \pmod{7} ]\n[ k = 3 + 7m ]", "Now substitute back:\n[ x = 2 + 5(3 + 7m) = 2 + 15 + 35m = 17 + 35m ]", "So the solution is:\n[ x \equiv 17 \pmod{35} ]", "## When ( \gcd(m, n) <br/>\ne 1 )?", "If ( m ) and ( n ) are not coprime, the system may have no solution or multiple solutions. For example:\n[ x \equiv 1 \pmod{4} ]\n[ x \equiv 3 \pmod{6} ]", "Here, ( \gcd(4,6)=2 ). Check consistency:\nLeft side: ( x \equiv 1 \pmod{4} \Rightarrow x \equiv 1, 5 \pmod{8} ) (not mod 4 only) — but numerically, values of ( x \equiv 3 \pmod{6} ) are 3, 9, 15, 21,…\nCheck 3 mod 4 = 3 ≠ 1 → no solution.", "But if ( x \equiv 1 \pmod{4} ) and ( x \equiv 1 \pmod{6} ), then ( x \equiv 1 \pmod{\ ext{lcm}(4,6)=12} ) works.", "So, when ( m \mid (b - a) ) and ( n \mid (b - a) ), or more generally, when the differences satisfy congruence conditions modulo the GCD, solutions may exist. Otherwise, no solution.", "## Why This Matters", "Solving the first two congruences using CRT is foundational in:\n- Cryptography: RSA relies on modular exponentiation and solving congruences in composite moduli.\n- Algorithm design: Hashing, pseudorandom number generation, and distributed computing use modular arithmetic extensively.\n- Everyday computation: Error-checking codes, calendar systems, and scheduling often depend on modular reasoning.", "## Conclusion", "Solving the first two congruences is a cornerstone of modular arithmetic. By combining the general solution of the first congruence with the Chinese Remainder Theorem (when applicable), you unlock a powerful method for finding simultaneous solutions. Whether you're a student, a developer, or a cryptographer, mastering this technique opens doors to deeper"]
