n^2 - 1 \equiv 0 \pmod{15} \implies (n-1)(n+1) \equiv 0 \pmod{15}

["Understanding the Modular Equation: n² – 1 ≡ 0 mod 15 Implies (n – 1)(n + 1) ≡ 0 mod 15", "The equation ( n^2 - 1 \equiv 0 \pmod{15} ) is a classic example in modular arithmetic that reveals deep insights into number theory. At first glance, it may seem like a simple quadratic congruence, but its implications extend into divisibility, prime factorization, and modular structure—especially when analyzed as ( (n - 1)(n + 1) \equiv 0 \pmod{15} ). In this article, we’ll explore how this congruence behaves, why the factorization matters, and how it connects to broader principles in number theory.", "---", "### What Does ( n^2 - 1 \equiv 0 \pmod{15} ) Mean?", "The expression ( n^2 - 1 \equiv 0 \pmod{15} ) means that ( n^2 - 1 ) is divisible by 15. Since ( 15 = 3 \ imes 5 ), a number divisible by 15 must also be divisible by both 3 and 5 (because 3 and 5 are coprime). So, solving the congruence is equivalent to solving the system:", "[\nn^2 \equiv 1 \pmod{3} \quad \ ext{and} \quad n^2 \equiv 1 \pmod{5}\n]", "This connection to prime moduli is a cornerstone of the Chinese Remainder Theorem, which allows us to reduce composite congruences into simpler components.", "---", "### Factoring the Congruence: ( (n - 1)(n + 1) \equiv 0 \pmod{15} )", "The expression ( n^2 - 1 ) factors neatly as:", "[\nn^2 - 1 = (n - 1)(n + 1)\n]", "So, ( n^2 - 1 \equiv 0 \pmod{15} ) becomes:", "[\n(n - 1)(n + 1) \equiv 0 \pmod{15}\n]", "This factorization transforms the problem into analyzing when the product ( (n - 1)(n + 1) ) is divisible by 15. In modular arithmetic, this means the product must be divisible by both 3 and 5.", "To satisfy ( (n - 1)(n + 1) \equiv 0 \pmod{15} ), at least one of the following must be true:", "- ( 3 \mid (n - 1) ) and ( 5 \mid (n + 1) ),\n- ( 5 \mid (n - 1) ) and ( 3 \mid (n + 1) ),\n- or both factors share divisibility between 3 and 5 such that the product covers both.", "We now explore these cases in depth.", "---", "### Step 1: Analyze Divisibility by 3 and 5", "Modulo 3:\nWe solve ( n^2 \equiv 1 \pmod{3} ). The quadratic residues modulo 3 are:", "- ( 0^2 \equiv 0 ),\n- ( 1^2 \equiv 1 ),\n- ( 2^2 \equiv 4 \equiv 1 \pmod{3} ).", "So ( n \equiv 1 \pmod{3} ) or ( n \equiv 2 \pmod{3} ). Thus, ( n <br/>\not\equiv 0 \pmod{3} ).", "Modulo 5:\nSimilarly, solve ( n^2 \equiv 1 \pmod{5} ). The quadratic residues modulo 5 are:", "- ( 0^2 \equiv 0 ),\n- ( 1^2 \equiv 1 ),\n- ( 2^2 \equiv 4 ),\n- ( 3^2 \equiv 9 \equiv 4 ),\n- ( 4^2 \equiv 16 \equiv 1 ).", "So ( n \equiv 1 \pmod{5} ) or ( n \equiv 4 \pmod{5} ), i.e., ( n \equiv \pm1 \pmod{5} ).", "Therefore, to satisfy ( n^2 \equiv 1 \pmod{15} ), ( n ) must be odd (since not divisible by 3) and Congruent to ( \pm1 \pmod{5} ).", "---", "### Step 2: Use the Factorization to Solve More Efficiently", "Since ( (n - 1)(n + 1) \equiv 0 \pmod{15} ), we know the product must be divisible by both 3 and 5. We now find all integers ( n ) modulo 15 satisfying both conditions via casework.", "Note: Since the modulus is small (15), we can test residue classes mod 15.", "Try all ( n ) from 0 to 14 and compute ( (n - 1)(n + 1) \mod 15 ):", "| ( n ) | ( n-1 ) | ( n+1 ) | ( (n-1)(n+1) \mod 15 ) |\n|--------|---------|---------|--------------------------|\n| 0 | -2 | 1 | ( -2 \equiv 13 ) |\n| 1 | 0 | 2 | 0 |\n| 2 | 1 | 3 | 3 |\n| 3 | 2 | 4 | 8 |\n| 4 | 3 | 5 | 15 ≡ 0 |\n| 5 | 4 | 6 | 24 ≡ 9 |\n| 6 | 5 | 7 | 35 ≡ 5 |\n| 7 | 6 | 8 | 48 ≡ 3 |\n| 8 | 7 | 9 | 63 ≡ 3 |\n| 9 | 8 | 10 | 80 ≡ 5 |\n| 10 | 9 | 11 | 99 ≡ 9 |\n| 11 | 10 | 12 | 120 ≡ 0 |\n| 12 | 11 | 13 | 143 ≡ 8 |\n| 13 | 12 | 14 | 168 ≡ 3 |\n| 14 | 13 | 15≡0 | 0 |", "From the table, ( (n - 1)(n + 1) \equiv 0 \pmod{15} ) when ( n \equiv 1, 4, 11, 14 \pmod{15} ).", "These correspond to:", "- ( n \equiv 1 \pmod{3} ), ( n \equiv 1 \pmod{5} ) → ( n \equiv 1 \pmod{15} )\n- ( n \equiv 4 \pmod{5} ), ( n \equiv 1 \pmod{3} ): Solve:\n ( n \equiv 4 \pmod{5} ), ( n \equiv 1 \pmod{3} ) → ( n \equiv 4 \cdot 3 + 1 = 13 )? Wait: better:\n Try values: 4, 9, 14 → 14 ≡ 2 mod 3, 4 ≡ 1 mod 3 ⇒ ( n \equiv 4 \pmod{15} )? Check mod 3: ( 4 \equiv 1 ), mod 5: 4 → yes. But ( n = 14 ) gives (n−1)(n+1)=13×15≡0 mod 15. So ( n \equiv 14 \equiv -1 ).\nThus, solution list:\n( n \equiv 1, 4, 11, 14 \pmod{15} ) → which are ( n \equiv \pm1, \pm4 \pmod{15} )", "But wait: ( n = 11 ): ( 11 \equiv 2 \pmod{3} )? ( 11 \div 3 = 3 \ imes 3 = 9 ), remainder 2 → ( n \equiv 2 \pmod{3} )? But earlier we had ( n <br/>\not\equiv 0 \pmod{3} ), yes, but ( n \equiv 2 \pmod{3} ) is allowed since ( n^2 \equiv 4 \equiv 1 \pmod{3} ).", "So full solution set mod 15 is:\n[\nn \equiv 1, 4, 11, 14 \pmod{15}\n]", "These values correspond to ( n \equiv \pm1, \pm4 \pmod{15} ), confirming that:", "[\nn^2 \equiv 1 \pmod{15} \iff (n - 1)(n + 1) \equiv 0 \pmod{15}\n]", "because both factors cover the necessary divisibility via their product being divisible by 3 and 5.", "---", "### Why This Factorization Matters", "The transformation ( n^2 - 1 = (n - 1)(n + 1) ) simplifies the problem by revealing that the original congruence is equivalent to the product of two consecutive even or odd terms being divisible by 15. This decomposition:", "- Separates the logical conditions across prime factors,\n- Enables solution via the Chinese Remainder Theorem,\n- Demonstrates how algebraic identities link additive and multiplicative structure in modular arithmetic.", "---", "### Practical Applications", "Understanding such modular properties is vital in:", "- Cryptography, particularly in RSA and discrete logarithm problems where factoring and modular inverses matter,\n- Primality testing, where quadratic residues and divisibility patterns help verify primes,\n- Algorithm design, optimizing checks for modular conditions in computational number theory.", "---", "### Conclusion", "The congruence ( n^"]