Modulo Prime Power

The congruence is equivalent to $x^3 - 3x - 123 = 0 \pmod{q}$ . Let $f(x) = x^3 - 3x - 123$ .

By Lagrange's Theorem, we know that $f(x) \equiv 0 \pmod{p}$ has at most $3$ roots. So we want $k > 1$ . By Hensel's lifting lemma, every root $r$ of $f(x) \equiv 0 \pmod{p^{k-1}}$ will lift to exactly one unique solution for $f(x) \equiv 0 \pmod{p^k}$ , if $f'(r) \not\equiv 0 \pmod{p}$ . It easily follows by induction that the congruence $f(x) \equiv 0 \pmod{p^k}$ has at most $3$ roots if $f'(r) \not\equiv 0 \pmod{p}$ for all the roots $r$ of $f(x) \equiv 0 \pmod{p}$ .

Thus, there must exist a root $r$ of $f(x) \equiv 0 \pmod{p^k}$ such that $f'(r) \equiv 0 \pmod{p}$ . This gives $0 \equiv 3r^2 - 3 \equiv 3(r-1)(r+1) \pmod{p}$ . Thus, we have either $3 \equiv 0 \pmod{p}$ or $r - 1 \equiv 0 \pmod{p}$ or $r + 1 \equiv 0 \pmod{p}$ .
The first case gives $p = 3$ .
The second case gives $r \equiv 1 \pmod{p}$ . Note that $f(r) \equiv 0 \pmod{p^k} \Rightarrow f(r) \equiv 0 \pmod{p}$ , so we have $0 \equiv f(1) \equiv -125 \pmod{p}$ . This gives $p = 5$ as the only solution.
The third case gives $r \equiv -1 \pmod{p}$ . Similarly, we have $0 \equiv f(-1) \equiv -121 \pmod{p}$ . This gives $p = 11$ as the only solution. Since $f(x) \equiv 0 \pmod{p^k} \Rightarrow f(x) \equiv 0 \pmod{p^{k-1}}$ , then for each $p$ and $k$ , we can use Hensel's lifting lemma to find all the roots of $f(x) \equiv 0 \pmod{p^k}$ given the roots of $f(x) \equiv 0 \pmod{p^{k-1}}$ .

For $p = 3$ , $f(x) \equiv 0 \pmod{3^k} \Rightarrow f(x) \equiv 0 \pmod{3} \Rightarrow x^3 \equiv 0 \pmod{3} \Rightarrow x \equiv 0 \pmod{3}$ . But for all integers $y$ , $f(3y) \equiv 27y^3 - 9y - 123 \equiv 3 \pmod{9}$ , so $f(3y) \not\equiv 0 \pmod{3^k}$ for all $k \geq 2$ . Therefore $f(x) \equiv 0 \pmod{3^k}$ has no solution for all $k \geq 2$ . So $k=1$ gives only one root, while $k \geq 2$ gives no roots. So there is no $q$ such that $p=3$ .

[Note: The rest of the proof establishes that $q=25, 121, 125$ are the only possible solutions. There are slightly quicker ways of showing this, though it's all based on the same idea. - Calvin]

For $p = 5$ , $0 \equiv f(x) \equiv x^3 - 3x + 2 \equiv (x+2)(x-1)^2 \pmod{5}$ . So $x \equiv 1, 3 \pmod{5}$ are the only solutions to $f(x) \equiv 0 \pmod{5}$ . Now we consider $k = 2$ . $f'(3) \not\equiv 0 \pmod{5}$ , so the root $x \equiv 3 \pmod{5}$ will lift to exactly one solution of $f(x) \equiv 0 \pmod{5}$ . Call this solution $x_1$ . For $x \equiv 1 \pmod{5}$ , since $f'(1) \equiv 0 \pmod{5}$ and $f(1) \equiv 0 \pmod{25}$ , then it will lift to multiple solutions of $f(x) \equiv 0 \pmod{25}$ , namely $x \equiv 1, 6, 11, 16, 21 \pmod{5}$ . So the congruence $f(x) \equiv 0 \pmod{25}$ has $6$ solutions. Now, we consider $k = 3$ . Again, $x_1$ will lift to exactly one solution of $f(x) \equiv 0 \pmod{125}$ . Call this solution $x_2$ . For $x \equiv 5j + 1 \pmod{25}$ where $j= 0,…,4$ , we have $f(x) \equiv (5j+1)^3 - 3(5j+1) - 123 \equiv 125j^3 + 75j^2 - 125 \equiv 75j^2 \pmod{125}$ . Only roots where $f(x) \equiv 0 \pmod{125}$ will be lifted, so we want $75j^2 \equiv 0 \pmod{125} \Rightarrow 3j^2 \equiv 0 \pmod{25} \Rightarrow j = 0$ . So only $x \equiv 1 \pmod{25}$ will lift. Specifically, it lifts to the solutions $x \equiv 1, 26, 51, 76, 101 \pmod{125}$ . Thus, the congruence $f(x) \equiv 0 \pmod{125}$ has $6$ solutions as well. Now consider $k = 4$ . Again, $x_2$ will lift to exactly one solution of $f(x) \equiv 0 \pmod{625}$ . For $x \equiv 25j + 1 \pmod{125}$ where $j = 0,.., 4$ , we have $f(x) \equiv (25j+1)^3 - 3(25j+1) - 123 = 15625j^3 + 1875j^2 - 125 \equiv -125 \not\equiv 0 \pmod{625}$ . So none of these roots will lift and the congruence $f(x) \equiv 0 \pmod{625}$ only has $1$ solution. Since this solution is the one that gives $f'(x) \not\equiv 0 \pmod{5}$ , then it will lift to exactly $1$ solution for each $k \geq 5$ . So for $p = 5$ , we have $k = 1$ giving $2$ roots, $k = 2, 3$ giving $6$ roots, and $k \geq 4$ giving $1$ root. Thus, when $p=5$ , $q = 25$ or $125$ .

For $p = 11$ , $0 \equiv f(x) \equiv x^3 - 3x - 2 \equiv (x-2)(x+1)^2 \pmod{11}$ . So $x \equiv 2, 10 \pmod{11}$ are the only solutions to $f(x) \equiv 0 \pmod{11}$ . Now we consider $k = 2$ . $f'(2) \not\equiv 0 \pmod{11}$ , so the root $x \equiv 2 \pmod{11}$ will lift to exactly one solution of $f(x) \equiv 0 \pmod{121}$ . Call this solution $x_3$ . For $x \equiv 10 \pmod{11}$ , since $f'(10) \equiv 0 \pmod{11}$ and $f(10) \equiv 0 \pmod{121}$ , then it will lift to multiple solutions of $f(x) \equiv 0 \pmod{121}$ , namely $x \equiv 11j - 1 \pmod{121}$ , where $j = 1,…, 10$ . So the congruence $f(x) \equiv 0 \pmod{121}$ has $12$ solutions. Now consider $k = 3$ . Again, $x_3$ will lift to exactly one solution of $f(x) \equiv 0 \pmod{1331}$ . For $x \equiv 11j - 1 \pmod{121}$ where $j = 1,…, 11$ , we have $f(x) \equiv (11k-1)^3 - 3(11k-1) - 123 \equiv 1331k^3 - 363k^2 - 121 \equiv -121(3k^2+1) \pmod{1331}$ . Only roots where $f(x) \equiv 0 \pmod{1331}$ will be lifted, so we want $-121(3k^2+1) \equiv 0 \pmod{1331} \Rightarrow 3k^2+1 \equiv 0 \pmod{11}$ . But it is easy to check that $k = 1,..., 10$ does not satisfy this congruence, so none of these roots will lift. Therefore, the congruence $f(x) \equiv 0 \pmod{1331}$ only has $1$ solution. Since this solution is the one that gives $f'(x) \not\equiv 0 \pmod{11}$ , then it will lift to exactly $1$ solution for each $k \geq 4$ . So for $p = 11$ , we have $k = 1$ giving $2$ roots, $k = 2$ giving $12$ roots, and $k \geq 3$ giving $1$ root. Thus, when $p = 11$ , $q=121$ .

We have now exhausted all the cases, so the only possible $q$ are $25, 121$ and $125$ . Their sum is $271$ , so $N = 271$ .

Denote $f(x)=x^3-3x-123.$ Because $deg(f)=3,$ if $q$ is a prime, then $f$ can have no more than three roots in the field of residues modulo $q$ . So $q=p^k$ for $k\geq 2.$

The main step in the argument, that allows to rule out most possibilities for $p$ , is the following lemma, which is a particular case of the famous Hensel's Lemma.

Lemma. Suppose $p$ is a prime, different from $3,$ $5,$ and $11$ . Suppose $x$ is an integer, such that $f(x)\equiv 0 \pmod {p^k}$ , for some $k\geq 1.$ Then there is exactly one residue $y$ modulo $p^{k+1}$ , congruent to $x$ modulo $p^k,$ such that $f(y)\equiv 0 \pmod {p^{k+1}}.$

Proof. Consider all residues $y$ modulo $p^{k+1}$ that are congruent to $x$ modulo $p^k.$ Each such $y$ can be written as $x+p^k z,$ where $z$ is an integer; the class of $y$ modulo $p^{k+1}$ is uniquely determined by the class of $z$ modulo $p$ . Plugging into $f(y)\equiv 0 \pmod {p^{k+1}}$ congruence that we need to solve, we get $(x+p^k z)^3-3(x+p^k z) -123 \equiv 0 \pmod {p^{k+1}}$ , which is equivalent to $(x^3-3x-123)+ 3x^2p^kz+3xp^{2k}z^2 + p^{3k} z^3 -3xp^k z \equiv 0 \pmod {p^{k+1}}$ Suppose $x^3-3x-123=p^k\cdot v.$ Because $k\geq 1,$ $2k$ and $3k$ are greater than or equal to $k+1,$ so the above can be rewritten as $p^k\cdot v + (3x^2-3)p^kz \equiv 0 \pmod {p^{k+1}}$ Dividing by $p^k$ , we get $3(x^2-1) z \equiv v \pmod p$ If $3(x^2-1)$ is not divisible by $p,$ this congruence has a unique solution modulo $p$ , and we are done. If $p\mid 3(x^2-1)$ , then either $p=3$ or $x\equiv \pm 1 \pmod p.$ Finally, if $f(1)\equiv 0 \pmod p$ , then $p\mid -125$ , so $p=5$ ; if $f(-1)\equiv 0 \pmod p$ , then $p\mid -121,$ so $p=11$ .

Remark. The above argument also works if $p$ is $5$ or $11$ and $x$ is not $1$ or $-1$ modulo $p.$ Indeed, in this case $3(x^2-1)\neq 0 \pmod p.$

Suppose for some $q=p^k,$ $p\neq 3, 5, 11,$ we have $f(x)\equiv 0 \pmod q$ for at least four residues modulo $q.$ Then by the above lemma the same must be true for $p^{k-1},$ $p^{k-2}, ... , p^1=p,$ which is impossible. Therefore, $p$ must be $3,$ $5,$ or $11.$

Case 1. $p=3.$ If $f(x)\equiv 0 \pmod 3,$ then $x^3 \equiv 0 \pmod 3,$ so $x=3y$ for some $y$ . But then $f(x)=27y^3-9y-123$ is never divisible by $9.$ So, no $q=3^k$ can satisfy the condition of the problem.

Case 2. $p=11.$ If $f(x)\equiv 0 \pmod {11},$ then, by direct check, either $x\equiv -1$ or $x\equiv 2$ modulo $11.$ For $x\equiv 2 \pmod {11},$ the Remark above implies that there is exactly one residue modulo $11^k,$ congruent to $2$ modulo $11,$ such that $f(x)\equiv 0 \pmod {11^k}.$

If $x\equiv -1 \pmod {11},$ then $x=-1+11y,$ so

$\begin{aligned} f(x) &=(-1+11y)^3-3(-1+11y)-123 \\ &= -121-3\cdot 11^2y^2+11^3y^3 \\ &=11^2(-1-3y^2+11y^3) \\ \end{aligned}$

So for every $y=1,2,...,11,$ we get $x$ such that $f(x)$ is divisible by $121,$ thus $q=121$ works. On the other hand, $11^2(-1-3y^2+11y^3)\equiv 0 \pmod {11^3}$ if and only if $-1-3y^2\equiv 0 \pmod{11},$ which never happens. So for any $k\geq 3$ there are no residues modulo $11^k$ , congruent to $-1$ modulo $11,$ such that $f(x)\equiv 0 \pmod {11^k}.$ Together with the sub-case $x\equiv 2 \pmod {11},$ considered above, we conclude that for $p=11$ there is one solution: $q=121.$

Case 3. $p=5.$ If $f(x)\equiv 0 \pmod {5},$ then, by direct check, either $x\equiv 1$ or $x\equiv 3$ modulo $5.$ For $x\equiv 3 \pmod 5,$ the Remark above implies that there is exactly one residue modulo $5^k,$ congruent to $3$ modulo $5,$ such that $f(x)\equiv 0 \pmod {5^k}.$

If $x\equiv 1 \pmod 5,$ then $x=1+5y,$ so $\begin{aligned} f(x) &=(1+5y)^3-3(1+5y)-123 \\ &=-125+3\cdot 25y^2+125y^3 \\ &=25(-5+3y^2+5y^3)\\ \end{aligned}$

So for every $y=0,1,2,3,4$ we get $x$ such that $f(x)$ is divisible by $25,$ thus $q=25$ works.

Note that $25(-5+3y^2+5y^3)\equiv 0 \pmod {5^3}$ if and only if $y\equiv 0 \pmod 5,$ that is $y=5z.$ In this case $x=1+25z$ and $f(x)=125(-1+15z^2+125z^3).$ This gives $5$ different residues $x$ modulo $5^3,$ so $q=125$ also works. On the other hand, $f(x)$ is never divisible by $5^4$ for $x\equiv 1 \pmod 5.$ So for any $k\geq 4$ there is only one residue $x$ modulo $5^k,$ such that $f(x)\equiv 0 \pmod {5^k},$ with $x\equiv 3 \pmod 5.$

Putting this all together, $q$ is $121,$ $25,$ or $125,$ so the answer is $121+25+125=271.$