0
$\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?

  • 0
    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)$2012-08-17
  • 0
    For an example, where lifting fails (because the derivative will be divisiple by $p$ at a root) see [this question.](http://math.stackexchange.com/q/162344/11619)2012-08-17

1 Answers 1