Congruence modulo ($2^{10}$)

Question

Good evening, i’d like to discuss the following congruence which i’m stuck with, with you, hoping to find answers : Find the number of solution of

$$x^5-16x\equiv 0 \mod 2^{10}$$

I think i have to imply a congruence (mod $2^5$) to find conditions on x and think i’d like to say that x has to be even. Then i’d like to return mod $2^{10}$ or at least being helped by Group Theory finding condition on the moltiplicative order of x. In this way i could find an isomorphism between Z/2^5z and Z/2^3z x Z/2z and easily conclude after knowing the order of x. I think i should procede this way but i don’t really have any idea to find the solution. Any tip or advice would be amazing, Thanks!

Ps. I think i know the number of solution, should be eight.

Answer 1

First, we note that $$ x^5 - 16x \equiv (x-2)x(x+2)(x^2+4) \equiv 0 \mod 2^{10} $$ Hence $x$ is even, $x=2t$. The equation becomes: \begin{gather} (2t-2)(2t)(2t+2)(4t^2+4) \equiv 2^5(t-1)t(t+1)(t^2+1)\equiv 0 \mod 2^{10}\\ (t-1)t(t+1)(t^2+1)\equiv 0 \mod 2^{5} \end{gather}

Now we have again two cases:

Case 1: $t$ is even, $t=2w$. Hence we have \begin{gather} (2w-1)2w(2w+1)(4w^2+1) \equiv 0 \mod 2^5\\ w\equiv 0 \mod 2^4 \end{gather} So we have solutions $x$ of the form $x=4w$ with $0\leq x < 2^{10}$ and $w\equiv 0 \mod 2^4$. Then we have $0\leq w<2^8$ with $w\equiv 0 \mod 2^4$. We obtain $\frac{2^8}{2^4} = 2^4$ solutions.

Case 2: $t$ is odd, $t=2w+1$. Hence we have \begin{gather} (2w)(2w+1)(2w+2)(4w^2+4w+1+1) \equiv 0 \mod 2^5\\ w(w+1)\equiv 0 \mod 2^2 \end{gather} So we have again to split:

• $w\equiv 0\mod 2^2$: then we have solutions $x$ of the form $x=2t=4w+2$ with $0\leq x < 2^{10}$ and $w\equiv 0 \mod 2^2$. Then we have $0\leq w < \frac{2^9-1}{2}$ with $w\equiv 0 \mod 2^2$. We obtain $\left\lceil\frac{2^9-1}{2\cdot 2^2}\right\rceil = 2^6$ solutions.
• $w\equiv 3\mod 2^2$: then we have solutions $x$ of the form $x=2t=4w+2$ with $0\leq x < 2^{10}$ and $w\equiv 3 \mod 2^2$. Then we have $0\leq w < \frac{2^9-1}{2}$ with $w\equiv 3 \mod 2^2$. We obtain $\left\lceil\frac{2^9-1}{2\cdot 2^2}\right\rceil = 2^6$ solutions.

Finally we get $2^4+2^6+2^6 = 16+64+64 = 144$ solutions.

Answer 2

This is an extended hint which is a start to one way of approaching the problem. The strategy is to work with a power of $2$ times an odd number to cancel as much as possible.

Write $x=2^ry$ with $y$ odd ($1\lt x\le 2^{10}$). Clearly $x$ is even so $1\le r\le 10$. Use equality to represent equivalence mod $2^{10}$

Then $2^{5r}y^5-2^{r+4}y=0$ and $\left(2^{4(r-1)}y^4-1\right)2^{r+4}y=0$

Now either $r+4\ge 10$ or the first factor in brackets must be even. Since $y$ is odd, this second possibility implies $r=1$ and you need $y^4-1$ to be divisible by $32$.