How many solutions are there for the congruence $x^{14}+x^7+1 \equiv 0 \; (\text{mod } 343)$?

Question

I have another question for you:

Tell how many solutions does the congruence $x^{14}+x^7+1 \equiv 0 \; (\text{mod } 343)$ and compute at least one of them.

Does this kind of exercise have a standard way to proceed? If so, how would you do that? Thank you very much!

Answer 1

Extended hints:

You undoubtedly observed that $343=7^3$ is a power of an odd prime. Thus we know that the group of units $G=\Bbb{Z}_{343}^*$ of the ring of residue classes $R=\Bbb{Z}_{343}$ is cyclic of order $\phi(7^3)=(7-1)7^2=294$.

We can immediately see that $x$ cannot be divisible by seven, for then we would have $x^{14}+x^7+1\equiv 1\pmod{7}$. Thus all solutions are in $G$.

Furthermore, $$ x^{14}+x^7+1=\frac{x^{21}-1}{x^7-1}. $$ If $x^7-1$ were divisible by seven (i.e. not in $G$), then $x^7\equiv x^{14}\equiv1\pmod7$, which means that $x$ is not a solution. Thus at a solution $x$ the above denominator is invertible in $R$. We also deduce that any solution of your congruence is also a solution of $x^{21}\equiv1\pmod{343}$. Hence $x$ is a solution, iff A) $x^{21}\equiv1$ and B) $x^7\not\equiv1$ (both congruences modulo $343$).

As $21\mid 294$ in the cyclic group $G$ there are _____ elements that satisfy the equation $x^{21}=1$. Out of these ______ also satisfy the equation $x^7=1$, and we just saw that those must be discarded. Therefore there are ______ pairwise non-congruent solutions (you fill in the blanks).

I propose the following probabilistic algorithm for finding a solution:

• Any element of $G$ satisfies the equation $x^{294}=1$. Thus if $x\in G$ is arbitrary, then $r=x^{14}$ satisfies the equation $r^{21}\equiv1$, because $r^{21}=x^{21\cdot14}=x^{294}$.
• With any kind of luck the number $r=x^{14}$ that you produced in the preceding step does not satisfy the equation $r^7\equiv1$. If you were unlucky, and this did happen, then try again until you find at least one solution.

Answer 2

$$x^{14}+x^7+1\equiv0\pmod{7^3}\implies x^{14}+x^7+1\equiv0\pmod{7^2}, x^{14}+x^7+1\equiv0\pmod7$$

Clearly, $(x,7)=1$

$$\implies x^7\equiv x\pmod 7, x^{14}\equiv x^2$$

So, $$x^{14}+x^7+1\equiv0\pmod7\implies x^2+x+1\equiv0$$ $$\iff x^2+x-6\equiv0\iff (x+3)(x-2)\equiv0$$

$$\implies x\equiv2,-3\pmod7$$

Now use Hensel's Lemma

If $\displaystyle f(x)=x^{14}+x^7+1,f'(x)=14x^{13}+7x^6\equiv0\pmod7$

If $\displaystyle x\equiv2,x=2+7a,x^7=(2+7a)^7=2^7+7(2a)^67+\cdots+(7a)^7\equiv2^7\pmod{49}\equiv30$

$\displaystyle\implies x^{14}\equiv(30)^2\equiv18\pmod{49}$

$\displaystyle\implies f'(2)\not\equiv0\pmod7$

Similarly, $\displaystyle f'(3)\not\equiv0\pmod7$

What can we conclude from here?