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?

  • $\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 Aug 17 '12 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 Aug 17 '12 at 10:50

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}} $$

  • $\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 Aug 17 '12 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 Aug 17 '12 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 Aug 17 '12 at 9:06
  • 1
    $\begingroup$ @user31899: Why wouldn't choosing $x_0\equiv w_0\pmod{p^k}$ work? $\endgroup$ – Jyrki Lahtonen Aug 17 '12 at 10:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.