Hensel’s Lemma

May 2025
M	T	W	T	F	S	S
	1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30

We start from a problem:

Problem: Find the number of elements in $\{1,2,\cdots, 2025\}$ such that it is congruent to $a^2$ module $2025$ for some integer $a$ .

Solution. The problem is the same as finding the number of solutions to

$x\equiv a^2 \pmod {2025}$

Using Chinese Remainder Theorem, the problem reduces to the system of equations

$x\equiv a^2 \pmod {5^2}$

$x\equiv a^2 \pmod {3^4}$

Our goal, thus, is to find the number of solutions for each of the equation. We start by looking at the first one

$x\equiv a^2 \pmod {5^2}$

Such equation is pretty hard to solve. But what if we only consider $x\equiv a^2 \pmod{5}$ ? By finding solutions in this set, we are allowed to reduce the range of our solution set to the module class of these solutions. Then how do we extend it? Here is where Hensel’s Lemma comes in.

Hensel’s Lemma Let $f(x)$ be a polynomial with integer coefficients. Let $k$ be a positive integer, and $r$ an integer such that $f(r)≡0 \pmod{p^k}$ . Then if $f'(r)\not\equiv 0\pmod p$ , there is an unique integer $s$ such that $f(s)\equiv 0 \pmod{p^{k+1}}$ and $s\equiv r \pmod {p^k}$ . If $f'(r)\equiv 0 \pmod p$ , then for all of the $s$ such that $s\equiv r \pmod{p^k}$ , $f(s)\equiv 0\pmod{p^{k+1}}$ .

Proof. We want something similar to binomial expansion so that we can cancel the terms with $p^{k+1}$ . We could think of Taylor Series expansion, and that’s where $f'(r)$ comes. Specifically, the polynomial

$f(r+p^kt)=f(r)+f'(r)p^kt+\frac{f''(r)}{2!}p^{2k}t^2+\cdots$

Therefore,

$f(r+p^kt)\equiv f(r)+f'(r)p^kt\pmod {p^{k+1}}$

When $f'(t)\not\equiv 0\pmod p$ , and $f(r+p^kt)=0\pmod {p^{k+1}}$ , we have

$t\equiv -\frac{f(r)}{f'(r)p^k}$

If, on the other hand, that $f'(r)\equiv 0\pmod p$ , then

$f(r+tp^k)\equiv f(r)+tp^kf'(r)\pmod {p^{k+1}}\equiv f(r)\pmod {p^k}$

This completes our proof.

Now let’s apply this lemma to the problem. For $x\equiv a^2\pmod 5$ . $x=\{1,4\}$ . So we could get that $1,4,6,9,\cdots$ are solutions. Adding with $25$ . We get $11$ solutions. Similarly, for $x\equiv a^2\pmod 3$ , $x=\{1\}$ . This gives us $27$ solutions. Don’t forget $x\equiv a^2\pmod 9$ , which has $\{1,4,7\}$ . In this case, there are $3$ solutions, $\{9,36,63\}$ . Together with $81$ , there’s a total of $31$ solutions. Therefore, the answer for this problem is $11\times 31=341$ .

Leave a Reply Cancel reply