Hensel's lemma modular arithmatic example problem

1k Views Asked by At

In an example for Hensel's Lemma we have met the criteria to use Hensel's lemma and have begun to apply it in a Hensel's iteration.

We have $f(x)=x^2+1$ and our initial $x_0=2$ is a solution $\pmod{5}$, to compute a solution to this $\pmod{5^2}$ we have the next step:

$$x_1\equiv x_0-\frac{f(x_0)}{f'(x_0)}\equiv2-\frac{5}{-1}\equiv 7\pmod{25}$$

So $x_1$ is a solution $\pmod{25}$


Question: I cant see how $f'(x_0)\equiv -1\pmod{25}$

I know $f'(x)=2x$, plugging in $f'(2)\equiv 4\pmod{25}$, where does the $-1$ come from, I know $4\equiv -1\pmod{5}$, but we are working in $\pmod{25}$

1

There are 1 best solutions below

0
On BEST ANSWER

it is worth working through one or two simple examples from first principles, as it were, before confidently applying the general formula. as André points out, the utility of Hensel's lemma is that the lifting process always uses computations to the original base. the clever trick, which is the essence of the lemma, works because a kind of cancellation is ensured.

you have found your first value $2 (\mod 5)$. so for the first lift you look for a solution of the type $2+5k$. inserting this you require: $$ (2+5k)^2 +1 \equiv_{5^2} 0 $$ expanding: $$ 2^2 + 2\cdot 2\cdot5k+5^2k^2 +1 \equiv_{5^2} 0 $$

now here the quadratic term can be cancelled because its coefficient is a multiple of $5^2$

$2^2+1$ is divisible by $5$ because you had already chosen $2$ for exactly that reason. this allows the crucial simplification - you can divide the whole equation through by $5$ and work $\mod 5$. so we have: $$1+4k \equiv_5 0$$ which gives $k=1$

so your next step of the solution is, as assumed, $2+5k$ which evaluates to $7$

now you go round the same loop again looking for a solution $7+25k \quad (\mod 125)$