1
$\begingroup$

Solve $x^{15} \equiv 6 \pmod{7^2}$.

My approach based on Hensel's lemma:

First let's solve $x^{15} \equiv 6 \pmod{7}$, observe $3$ is a primitive root $\pmod{7}$, so let $x=3^y$ to get $15y \equiv 3 \pmod{6}$, solve to get $y_1=1, y_2=3, y_3=5$, the corresponding $x$'s are $x_1=3, x_2=6, x_3=5$

Now I use Hensel's lemma to lift the solutions to $\pmod{7^2}$. For example for $x_1$ one has $x_1^{15}-6=7 \times 2049843$ and $15x_1^{14}=3^{15} \times 5$, thus $7^0||(15x_1^{14})$, solve $2049843+3^{15} \times 5z_1 \equiv 0 \pmod{7}$ to get $z_1 \equiv 1 \pmod{7}$, so $w_1=x_1+7 \times z_1=10$ is a solution to the original equation.

Similar to $w_1$ one can lift $x_2,x_3$to get $w_2=6$ and $w_3=33$ are the other two solutions to the original equation $\pmod{49}$.

But does this way produce all the solutions?

$\endgroup$
2
  • $\begingroup$ We can verify using index-formula. As $\phi(7^2)=7\phi(7)=7\cdot 6=42$ is divisible by 1,2,3,6,7,14,21,42 $3^2=9,\ 3^3=27,\ 3^6=729≡43≡-6,\ 3^7≡-3\cdot 6 =-18,\ 3^{14}=324≡30 \ 3^{21}≡-18\cdot 30 =-540≡-1(mod\ 7^2)$ So, 3 is a primitive root $(mod\ 7^2)$. $idx_36=idx_3(-6)(-1)=idx_3(-6)+idx_3(-1)=6+21=27$ So, the problem reduces to $15idx_3x=27(mod\ 42)$ (15,42)=3 which divides 27, so there will exactly 3 solutions $(mod\ 42)$ $=>5idx_3x≡9(mod\ 14)=>idx_3x≡13(mod\ 14)≡13, 27, 41(mod\ 42)$ $=>x≡3^{13}, 3^{27}, 3^{41}(mod\ 7^2)$ $\endgroup$
    – lab bhattacharjee
    Commented Aug 17, 2012 at 10:02
  • $\begingroup$ For an example, where lifting fails (because the derivative will be divisiple by $p$ at a root) see this question. $\endgroup$
    – Jyrki Lahtonen
    Commented Aug 17, 2012 at 10:50

1 Answer 1

Reset to default
3
$\begingroup$

Yes, when Hensel's lemma applies, it gives all solutions.

One way to see why (the simplest form of) Hensel's lemma is true is nothing more than simply solving the equation

$$ f(x + a p^k) \equiv 0 \pmod{p^{k+1}} $$

for $a$ in a situation where $f(x) \equiv 0 \pmod{p^k}$ and the Taylor series for $f(x)$ makes sense and the higher order terms vanish, due to the high powers of $p$ involved:

$$ f(x + a p^k) \cong f(x) + a p^k f'(x) \pmod{p^{k+1}} $$

$\endgroup$
4
  • $\begingroup$ Is there a more obvious way to prove it? ie if Hensel's lemma applies then every solution can be seen as rised from a basic solution through Hensel? $\endgroup$
    – user31899
    Commented Aug 17, 2012 at 8:42
  • $\begingroup$ @user: I guess I'm missing the point of your comment. I'm not sure what could be more obvious than the fact that extensions of a solution modulo $p^k$ to a solution modulo $p^{k+1}$ are determined by solving a linear equation. $\endgroup$
    – user14972
    Commented Aug 17, 2012 at 8:59
  • $\begingroup$ Yeah I know a solution mod $p^k$ has a unique lift to a solution mod $p^{k+1}$. But conversely (assumes Hensel applies), given a solution $w_0$ mod $p^{k+1}$, does there exist a root $x_0$ mod $p^k$ whose lift is $w_0$? That's what I'm wondering.. $\endgroup$
    – user31899
    Commented Aug 17, 2012 at 9:06
  • 1
    $\begingroup$ @user31899: Why wouldn't choosing $x_0\equiv w_0\pmod{p^k}$ work? $\endgroup$
    – Jyrki Lahtonen
    Commented Aug 17, 2012 at 10:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .