Solution:** We are tasked with finding the smallest positive integer \( n \) such that \( n^2 \equiv 76 \pmod{100} \).

["Understanding the Smallest Positive Integer ( n ) for Which ( n^2 \equiv 76 \pmod{100} )", "Finding the smallest positive integer ( n ) such that ( n^2 \equiv 76 \pmod{100} ) involves solving a modular square congruence—a problem with deep roots in number theory and practical applications in cryptography and modular arithmetic. This article explores how to systematically determine such an ( n ), the mathematical principles behind it, and the significance of the result.", "---", "### What Does ( n^2 \equiv 76 \pmod{100} ) Mean?", "The equation ( n^2 \equiv 76 \pmod{100} ) asks: Which integer ( n ), when squared, leaves a remainder of 76 when divided by 100? This means the last two digits of ( n^2 ) must be 76.", "Rather than testing every integer randomly, we apply modular arithmetic techniques to narrow down possible candidates efficiently.", "---", "### Strategy: Solving ( n^2 \mod 100 = 76 )", "Since 100 = 4 × 25 and (\gcd(4,25)=1), we can use the Chinese Remainder Theorem (CRT). This means solving the system:", "[\n\begin{align}\nn^2 &\equiv 76 \pmod{4}, \\nn^2 &\equiv 76 \pmod{25}.\n\end{align}\n]", "Then combine solutions logically.", "---", "### Step 1: Solve ( n^2 \equiv 76 \pmod{4} )", "Note ( 76 \mod 4 = 0 ), so:", "[\nn^2 \equiv 0 \pmod{4}\n]", "Perfect squares mod 4 are only ( 0 ) or ( 1 ):", "- ( 0^2 \equiv 0 ), ( 1^2 \equiv 1 ), ( 2^2 \equiv 0 ), ( 3^2 \equiv 1 )", "Thus, ( n^2 \equiv 0 \pmod{4} ) implies ( n \equiv 0 ) or ( 2 \pmod{2} ), i.e., ( n ) must be even.", "---", "### Step 2: Solve ( n^2 \equiv 76 \pmod{25} )", "Now compute ( 76 \mod 25 = 1 ), so:", "[\nn^2 \equiv 1 \pmod{25}\n]", "Solutions to ( x^2 \equiv 1 \pmod{25} ) are values of ( x ) such that ( x \equiv \pm 1 \pmod{25} ), but because of modulus structure, we find all solutions explicitly.", "We solve ( n^2 \equiv 1 \pmod{25} \Rightarrow n^2 - 1 \equiv 0 \pmod{25} \Rightarrow (n-1)(n+1) \equiv 0 \pmod{25} )", "Thus, 25 divides ( (n-1)(n+1) ). Since 25 divides the product, possibilities include:", "- ( n \equiv 1 \pmod{25} )\n- ( n \equiv -1 \equiv 24 \pmod{25} )\n- Or one factor divisible by 5 and the other by 5 (but not both by 25), since 25 = 5².", "Let’s test whether 5-smooth solutions exist. Try small values near 1 and 24:", "Try ( n \equiv 1, 24, 26 (\equiv -19), 49, \ldots )", "But better: since ( n^2 \equiv 1 \pmod{25} ), all integer solutions are:", "[\nn \equiv \pm1, \pm24 \pmod{25}\n]", "Check:\n- ( 1^2 = 1 \mod 25 )\n- ( 24^2 = 576 \mod 25 = 576 - 550 = 26 \equiv 1 )? Wait: 576 ÷ 25 = 23×25 = 575 → 576 ≡ 1 ✅\n- Try ( n = 26 ): 26 mod 25 = 1 → same\n- Try ( n = 49 ): 49 − 50 = -1 → 49 ≡ −1 → (−1)² = 1 ✅\n- Try intermediate: solve directly.", "Actually, the complete solution set mod 25 is:", "[\nn \equiv 1, 24, 6, 19 \pmod{25}?\n]", "Wait — better: solve ( x^2 \equiv 1 \pmod{25} )", "We know that modulo prime power ( p^k ), the number of solutions to ( x^2 \equiv 1 ) is limited.", "Since 25 is ( 5^2 ), and 5 ≡ 1 mod 4, the equation ( x^2 \equiv 1 \pmod{5^2} ) has exactly two solutions: ( x \equiv \pm 1 \pmod{25} )", "So:", "[\nn \equiv 1 \pmod{25} \quad \ ext{or} \quad n \equiv 24 \pmod{25}\n]", "Thus, ( n \equiv \pm1 \pmod{25} )", "---", "### Step 3: Combine Using Chinese Remainder Theorem", "We now solve two systems:", "Case 1:\n( n \equiv 0 \pmod{2} ) (even),\n( n \equiv 1 \pmod{25} )", "Let ( n = 25k + 1 ). Require ( 25k + 1 \equiv 0 \pmod{2} \Rightarrow 25k \equiv 1 \pmod{2} \Rightarrow k \equiv 1 \pmod{2} )", "So ( k ) odd: ( k = 2m + 1 )", "Then ( n = 25(2m+1) + 1 = 50m + 26 )", "So ( n \equiv 26 \pmod{50} )", "Case 2:\n( n \equiv 0 \pmod{2} ),\n( n \equiv 24 \pmod{25} )", "Let ( n = 25k + 24 )", "Then ( 25k + 24 \equiv 0 \pmod{2} \Rightarrow 25k \equiv 0 \pmod{2} \Rightarrow k \equiv 0 \pmod{2} ) (since 25 odd)", "So ( k = 2m ), then ( n = 25(2m) + 24 = 50m + 24 )", "Thus ( n \equiv 24 \pmod{50} )", "So solutions mod 100 must satisfy either:", "[\nn \equiv 24, 26, 74, 76 \pmod{100}\n]", "Why 24, 26, 74, 76?", "We split mod 4 and mod 25 combinations:", "From earlier:\n- For ( n \equiv 1 \pmod{25} ) and even ⇒ possible values mod 100: try\n ( 25k + 1 ) even ⇒ ( k ) odd ⇒ ( k = 1,3,5,7,9 )\n → ( n = 26, 76, 126≡26, 176≡76, \ldots \Rightarrow \ ext{mod 100: } 26, 76 )", "- For ( n \equiv 24 \pmod{25} ) and even ⇒ 24 is even, next: 24 + 50 = 74 (since period 50)", "Thus, possible solutions mod 100 are:", "[\nn \equiv 24, 26, 74, 76 \pmod{100}\n]", "---", "### Step 4: Find the Smallest Positive Integer ( n )", "From candidates: 24, 26, 74, 76, the smallest positive is ( \boxed{24} )", "Check:", "[\n24^2 = 576\n]\n[\n576 \div 100 = 5 \ imes 100 = 500,\quad 576 - 500 = 76\n]\n✅ ( 24^2 \equiv 76 \pmod{100} )", "Confirm no smaller positive ( n ):\nTry ( n = 1 ) to ( 23 ): none satisfy ( n^2 \mod 100 = 76 ) (verified via direct squaring or modulus bounds).", "---", "### Why This Problem Matters", "This type of modular square search appears in:", "- Cryptography: Used in discrete logarithm problems and quadratic residues.\n- Computational Number Theory: Fundamental in understanding structure of integers under modular constraints.\n- Algorithm Design: Testing modular square roots is a classic problem in programming and math competitions.", "Thus, solving ( n^2 \equiv 76 \pmod{100} ) is not just an isolated exercise—it reveals deeper connections in mathematics and computation.", "---", "### Final Answer", "The smallest positive integer ( n ) such that ( n^2 \equiv 76 \pmod{100} ) is:", "[\n\boxed{24}\n]"]