Mod 125:** Solve \( n^3 \equiv 1 \pmod{125} \)

["# Solve ( n^3 \equiv 1 \pmod{125} ): A Complete Guide to Cubic Solutions Modulo 125", "## Introduction", "The congruence ( n^3 \equiv 1 \pmod{125} ) is a classic problem in number theory and modular arithmetic. Solving this equation involves finding all integers ( n ) such that when cubed, the result leaves a remainder of 1 modulo ( 125 = 5^3 ). This problem not only deepens understanding of modular exponentiation but also has applications in cryptography, algebra, and computational number theory.", "In this article, we explore the structure, solutions, and method behind solving ( n^3 \equiv 1 \pmod{125} ), with detailed examples and step-by-step reasoning to make this challenging congruence approachable.", "---", "## Understanding the Problem", "We seek all integers ( n ) satisfying:\n[ n^3 \equiv 1 \pmod{125} ]\nwhich means ( 125 \mid (n^3 - 1) ), or equivalently:\n[ n^3 - 1 = (n - 1)(n^2 + n + 1) \equiv 0 \pmod{125} ]", "Since 125 is a power of a prime (( 5^3 )), solutions modulo 125 can be lifted from solutions modulo lower powers like 5, 25, and 125 via Hensel’s Lemma-style lifting or direct computation.", "---", "## Step 1: Solve ( n^3 \equiv 1 \pmod{5} )", "First, reduce modulo 5:", "[ n^3 \equiv 1 \pmod{5} ]", "Try all residues mod 5:", "- ( 0^3 = 0 <br/>\not\equiv 1 )\n- ( 1^3 = 1 \equiv 1 ) ✅\n- ( 2^3 = 8 \equiv 3 <br/>\not\equiv 1 )\n- ( 3^3 = 27 \equiv 2 <br/>\not\equiv 1 )\n- ( 4^3 = 64 \equiv 4 <br/>\not\equiv 1 )", "Only solution: ( n \equiv 1 \pmod{5} )", "So the only cube root of 1 mod 5 is ( n \equiv 1 ).", "---", "## Step 2: Lift to Modulo 25 Using Hensel’s Lemma or Direct Search", "We want solutions to ( n^3 \equiv 1 \pmod{25} ), starting from ( n \equiv 1 \pmod{5} ), so write:\n[ n = 1 + 5k ]\nand substitute into ( n^3 \equiv 1 \pmod{25} ):", "Compute ( (1 + 5k)^3 \mod 25 ):", "[\n(1 + 5k)^3 = 1 + 3(5k) + 3(5k)^2 + (5k)^3 = 1 + 15k + 75k^2 + 125k^3\n]", "Mod 25:\n- ( 75k^2 \equiv 0 )\n- ( 125k^3 \equiv 0 )\nSo:\n[ n^3 \equiv 1 + 15k \pmod{25} ]", "Set equal to 1:\n[ 1 + 15k \equiv 1 \pmod{25} \Rightarrow 15k \equiv 0 \pmod{25} ]", "Solve:\n[ 15k \equiv 0 \pmod{25} ]", "Divide both sides by ( \gcd(15, 25) = 5 ):\n[ 3k \equiv 0 \pmod{5} \Rightarrow k \equiv 0 \pmod{5} ]", "So ( k = 5m ), and thus:\n[ n = 1 + 5k = 1 + 5(5m) = 1 + 25m \Rightarrow n \equiv 1 \pmod{25} ]", "So modulo 25, only solution is ( n \equiv 1 \pmod{25} )", "Wait — is this the only solution?", "Let’s verify directly: try all ( n \equiv 1, 6, 11, 16, 21 \pmod{25} ) (numbers ≡ 1 mod 5):", "- ( 1^3 = 1 \equiv 1 ) ✅\n- ( 6^3 = 216 \mod 25 = 216 - 8×25 = 216 - 200 = 16 <br/>\not\equiv 1 )\n- ( 11^3 = 1331; 1331 \div 25 = 53×25 = 1325 → 1331 - 1325 = 6 <br/>\not\equiv 1 )\n- ( 16^3 = 4096; 4096 \mod 25: 4096 - 163×25 = 4096 - 4075 = 21 <br/>\not\equiv 1 )\n- ( 21^3 = 9261; 9261 \mod 25: 9261 - 370×25 = 9261 - 9250 = 11 <br/>\not\equiv 1 )", "Only ( n \equiv 1 \pmod{25} ) satisfies ( n^3 \equiv 1 \pmod{25} )", "Conclusion: only residue mod 25 is ( n \equiv 1 \pmod{25} )", "---", "## Step 3: Lift to Modulo 125", "Now solve ( n^3 \equiv 1 \pmod{125} ) starting from ( n \equiv 1 \pmod{25} ), so write:\n[ n = 1 + 25k ]\nand substitute into ( n^3 \equiv 1 \pmod{125} )", "Compute ( (1 + 25k)^3 \mod 125 ):", "[\n(1 + 25k)^3 = 1 + 3(25k) + 3(25k)^2 + (25k)^3 = 1 + 75k + 3 \cdot 625k^2 + 15625k^3\n]", "Mod 125:\n- ( 625k^2 \equiv 0 ) since 625 = 5×125\n- ( 15625k^3 \equiv 0 )\nSo:\n[ n^3 \equiv 1 + 75k \pmod{125} ]", "Set equal to 1 mod 125:\n[ 1 + 75k \equiv 1 \pmod{125} \Rightarrow 75k \equiv 0 \pmod{125} ]", "Now solve:\n[ 75k \equiv 0 \pmod{125} ]", "Divide through by ( \gcd(75, 125) = 25 ):\n[ 3k \equiv 0 \pmod{5} \Rightarrow k \equiv 0 \pmod{5} ]", "So ( k = 5m ), and thus:\n[ n = 1 + 25k = 1 + 25(5m) = 1 + 125m \Rightarrow n \equiv 1 \pmod{125} ]", "Is this the only solution?", "Check if any other solutions exist modulo 125 by testing all ( n \equiv 1 \pmod{25} ):\nThat means ( n = 1, 26, 51, 76, 101 \pmod{125} )", "Compute ( n^3 \mod 125 ):", "- ( n = 1 ): ( 1^3 = 1 \equiv 1 ) ✅\n- ( n = 26 ): ( 26^3 = 17,576 ); compute ( 17576 \mod 125 ):\n ( 125 \ imes 140 = 17500 ), ( 17576 - 17500 = 76 <br/>\not\equiv 1 )\n- ( n = 51 ): ( 51^3 = 132,651 ); ( 125 \ imes 1061 = 132,625 ), ( 132651 - 132625 = 26 <br/>\not\equiv 1 )\n- ( n = 76 ): ( 76^3 = 438,976 ); ( 125 \ imes 3511 = 438,875 ), ( 438976 - 438875 = 101 <br/>\not\equiv 1 )\n- ( n = 101 ): ( 101^3 = 1,030,301 ); ( 125 \ imes 8242 = 1,030,250 ), ( 1030301 - 1030250 = 51 <br/>\not\equiv 1 )", "No others satisfy ( n^3 \equiv 1 \pmod{125} )", "Therefore, the only solution modulo 125 is:", "[\nn \equiv 1 \pmod{125}\n]", "---", "## Are There More Solutions? Re-evaluation via Group Theory", "Note: The multiplicative group modulo ( 5^3 = 125 ) is cyclic of order ( \phi(125) = 100 = 2^2 \cdot 5 ).", "We seek solutions to ( n^3 \equiv 1 \pmod{125} ), i.e., elements of order dividing 3 in this group.", "Since ( \gcd(3, 100) = 1 ), the only solution to ( x^3 \equiv 1 ) in a cyclic group of order coprime to 3 is the unique identity solution — the trivial root.", "Wait: This seems contradictory to earlier result — but actually, note ( \gcd(3, 100) = 1 ), so in a cyclic group of order 100, the map ( x \mapsto x^3 ) is bijective: every element has a unique cube root.", "That implies there is exactly one solution to ( x^3 \equiv 1 \pmod{125} ), namely ( x \equiv 1 )", "This confirms our result: only solution is ( n \equiv 1 \pmod{125} )", "---", "## Conclusion", "The congruence\n[ n^3 \equiv 1 \pmod{125} ]\nhas exactly one solution modulo 125:\n[\nn \equiv 1 \pmod{125}\n]", "This follows from the structure of the multiplicative group modulo 125, which is cyclic of order 100, and since 3 is coprime to 100, the map ( x \mapsto x^3 ) is a permutation — so 1 has a unique preimage.", "Understanding such modular equations is fundamental in number theory, cryptography (e.g., discrete logs), and"]