We search for a solution to \(n^3 \equiv 13 \pmod{125}\). Try lifting via Henselâs Lemma or trial.
["Solving (n^3 \equiv 13 \pmod{125}): A Step-by-Step Search Using Hensel’s Lemma and Trial Search", "Finding solutions to modular cubic congruences like ( n^3 \equiv 13 \pmod{125} ) poses a challenging yet fascinating problem in number theory. Since 125 is ( 5^3 ), lifting solutions from modulo 5 to modulo 125 using tools such as Hensel’s Lemma and brute-force trial provides insight into how cubic residues behave across increasingly larger powers of primes.", "---", "### Why Solve (n^3 \equiv 13 \pmod{125})?", "Congruences of the form (n^k \equiv a \pmod{p^m}) appear in cryptography, algebraic number theory, and Diophantine equations. Here, we aim to solve the cubic congruence (n^3 \equiv 13 \pmod{125}). While direct methods fail often due to ring structure, combining modular tests with lifting procedures offers a path to solutions.", "---", "### Step 1: Check solve-ability modulo 5", "First, reduce the problem modulo 5. Solve:", "[\nn^3 \equiv 13 \pmod{5} \implies n^3 \equiv 3 \pmod{5}\n]", "Evaluate cubes modulo 5:", "- (0^3 \equiv 0)\n- (1^3 \equiv 1)\n- (2^3 = 8 \equiv 3)\n- (3^3 = 27 \equiv 2)\n- (4^3 = 64 \equiv 4)", "So, (n \equiv 2 \pmod{5}) is the only solution. This confirms existence of cube roots locally modulo 5, and we may proceed applying Hensel’s Lemma.", "---", "### Step 2: Apply Hensel’s Lemma to lift the solution to modulo 25", "Hensel’s Lemma applies when derivative conditions on the polynomial are non-singular.", "Let (f(n) = n^3 - 13), so (f'(n) = 3n^2).", "We lift (n_0 = 2) modulo 5. Compute (f(2) \equiv 8 - 13 = -5 \equiv 0 \pmod{5}), as expected.", "Check derivative:\n[\nf'(2) = 3 \cdot 2^2 = 12 \equiv 2 <br/>\not\equiv 0 \pmod{5}\n]", "Since (f'(2) <br/>\not\equiv 0 \pmod{5}), Hensel’s Lemma guarantees a unique lift of (n_0 = 2) modulo 25.", "Let (n = 2 + 5t). Plug into original congruence modulo 25:", "[\n(2 + 5t)^3 \equiv 13 \pmod{25}\n]", "Expand:", "[\n8 + 3 \cdot 4 \cdot 5t + 3 \cdot 2 \cdot 25t^2 + 125t^3 \equiv 8 + 60t \pmod{25}\n]", "Since (125t^3 \equiv 0 \pmod{25}), and (60t \equiv 10t \pmod{25}), so:", "[\n8 + 10t \equiv 13 \pmod{25} \implies 10t \equiv 5 \pmod{25}\n]", "Divide by 5: (2t \equiv 1 \pmod{5}), so (t \equiv 3 \pmod{5}) (since (2 \cdot 3 = 6 \equiv 1)).", "Thus, (t = 3 + 5s), and the lift is:", "[\nn \equiv 2 + 5 \cdot 3 = 17 \pmod{25}\n]", "Check: (17^3 = 4913), and (4913 \mod 25 = 4913 - 196 \cdot 25 = 4913 - 4900 = 13). Correct.", "---", "### Step 3: Lift solution to modulo 125 using Hensel’s Lemma again", "Now lift from (n \equiv 17 \pmod{25}) to (n \equiv ? \pmod{125}).", "Let (n = 17 + 25s). Plug into (n^3 \equiv 13 \pmod{125}):", "Compute ( (17 + 25s)^3 \mod 125 )", "Use binomial expansion (keeping terms modulo 125):", "[\n(17 + 25s)^3 = 17^3 + 3 \cdot 17^2 \cdot 25s + 3 \cdot 17 \cdot (25s)^2 + (25s)^3\n]", "Modulo 125, terms with (25^2 = 625 \equiv 0 \pmod{125}), so higher powers vanish.", "Thus,", "[\nn^3 \equiv 17^3 + 3 \cdot 289 \cdot 25s \pmod{125}\n]", "First, compute (17^3 = 4913), and (4913 \mod 125):", "- (125 \cdot 39 = 4875), so (4913 - 4875 = 38)", "So (17^3 \equiv 38 \pmod{125})", "Now, compute (3 \cdot 289 \cdot 25s = 3 \cdot 25 \cdot 289 s = 75 \cdot 289 s)", "But modulo 125: note (75 \cdot 289 s \mod 125)", "First reduce (289 \mod 5) (since 125 divisible by 5, but better to reduce coefficients mod 5 for scaling):", "Actually, compute:", "[\n3 \cdot 289 \cdot 25 s = 75 \cdot 289 s\n]", "Now (75 \cdot 289 s \mod 125)", "Note (75 = 25 \cdot 3), and (289 \mod 125): (125 \cdot 2 = 250), (289 - 250 = 39), so (289 \equiv 39 \pmod{125})", "So:", "[\n75 \cdot 289 s \equiv 75 \cdot 39 s = 2925 s \pmod{125}\n]", "Now compute (2925 \mod 125):", "(125 \cdot 23 = 2875), so (2925 - 2875 = 50), thus:", "[\n2925s \equiv 50s \pmod{125}\n]", "Hence:", "[\nn^3 \equiv 38 + 50s \pmod{125}\n]", "Set equal to 13:", "[\n38 + 50s \equiv 13 \pmod{125} \implies 50s \equiv -25 \equiv 100 \pmod{125}\n]", "So solve:\n[\n50s \equiv 100 \pmod{125}\n]", "Divide entire congruence by 25:", "[\n2s \equiv 4 \pmod{5} \implies s \equiv 2 \pmod{5}\n]", "Thus, (s = 2 + 5t), so:", "[\nn = 17 + 25s = 17 + 25(2 + 5t) = 17 + 50 + 125t = 67 + 125t\n]", "Therefore, modulo 125,", "[\nn \equiv 67 \pmod{125}\n]", "---", "### Verification", "Compute (67^3 \mod 125):", "First, (67^2 = 4489); (4489 \mod 125):", "(125 \cdot 35 = 4375), (4489 - 4375 = 114)", "So (67^2 \equiv 114), then:", "(67^3 = 67 \cdot 114 = 7638)", "Now (7638 \mod 125):", "(125 \cdot 61 = 7625), so (7638 - 7625 = 13)", "Hence, (67^3 \equiv 13 \pmod{125}) — the solution is confirmed.", "---", "### Alternative: Brute Force Trial (Optional Cross-Check)", "While Hensel provides efficiency, brute force over a residue class modulo 125 offers insight. Since (n \equiv 67 \pmod{125}) is the only solution among (n = 0,1,\dots,124), and trial confirms (67^3 \equiv 13), no other solutions exist. But Hensel’s lifting remains the systematic way for larger moduli not instantly solvable by trial.", "---", "### Conclusion", "Solving (n^3 \equiv 13 \pmod{125}) benefits greatly from Hensel’s Lemma, which lifts solutions from smaller prime powers by lifting weighted step-by-step. Starting at (n \equiv 2 \pmod{5}), lifting to modulo 25, and then to 125, yields a unique solution (n \equiv 67 \pmod{125}). Combining modular lifting with verification ensures robustness and illuminates deep structures in algebraic congruences.", "This method exemplifies the power of hybrid analytic and computational approaches in solving Diophantine problems in modular arithmetic — especially when full factorization or direct exponentiation is impractical.", "---", "Keywords:\n(n^3 \equiv 13 \pmod{125}), Hensel’s Lemma, modular cube roots, lifting solution, 5-adic analysis, number theory, Diophantine equations modulo powers, trial and error, congruences in cryptography."]
