0

I show you my attempt: $$(125, 98) = 1 \Rightarrow(x^{98} , 125) = 1 \Rightarrow (x, 125) = 1$$ (Euclidian Algorithm)

$$x^{\phi(125)} = x^{100} \equiv1\pmod{125} \wedge x^{98} \equiv99(\mod 125) \Rightarrow x^2\equiv99 \pmod{125} \Rightarrow x^2 \equiv{99}\pmod{5} \Rightarrow x^2 \equiv{4}\pmod{5}$$

Thus, $$5|(x-2)(x+2)$$ $$x\equiv{7,3}\pmod{5}$$ $$x\equiv{7,3}\pmod{125}$$

I ask you to check my solution and explain me when I got wrong.

xawey
  • 381

2 Answers2

1

HINT:

$$x^{100}\equiv1,x^{98}\equiv99\implies x^2(x^{98})\equiv1\implies99x^2\equiv1\pmod{125}\ \ \ \ (1)$$

$(1)\implies99x^2\equiv1\pmod5\iff-x^2\equiv1\iff x^2\equiv-1\equiv4\implies x\equiv\pm2$

Now use Hensel's lemma (1), (2)

lab bhattacharjee
  • 274,582
  • Ok, I have a problem with Hensel's Lemma, Could you show me it ? – xawey Aug 31 '14 at 16:06
  • @xawey, Have you followed by links ? – lab bhattacharjee Aug 31 '14 at 16:13
  • Yes, I used (1), but I have a problem – xawey Aug 31 '14 at 16:15
  • @xawey, Please share where you are stuck when I try to show the same. – lab bhattacharjee Aug 31 '14 at 16:19
  • @xawey, Starting with $$x\equiv2\pmod5, x=5t+2\implies x^2=25t^2+20t+4\equiv20t+4\pmod{25}$$ But $x^2\equiv-1\pmod{25},\implies 20t+4\equiv-1\pmod{25}\iff4t+1\equiv0\pmod5\implies t\equiv1\pmod5,t=5u+1\implies x=5(5u+1)+2=25u+7$ $$\implies x^2\equiv 49+350u\pmod{125}\equiv49+100u\implies99x^2\equiv99(49+100u)\equiv(100-1)(50-1)+(100-1)100u\equiv-100u+1-150$$ But $$99x^2\equiv1\pmod{125},\implies1\equiv-100u+1-150\pmod{125}\iff 4u\equiv-1\pmod5\implies u\equiv1\pmod5\implies u=5v+1\implies x=25u+7=25(5v+1)+7\equiv25+7\pmod{125}$$ – lab bhattacharjee Aug 31 '14 at 16:40
  • Look at my attempt. $$r=2$$ Let $f(x) = 99x^2-1$. Is $f'(2) \equiv 0 (\mod 5) $ - no. Is $f(2) \equiv 0 (\mod 25) $ ? - No. Thus, using Hensel Lemma We may find $t$ $$ f(2+5t) \equiv 0 (\mod 5^2) $$ And for $t$: $$tf'(2) \equiv -\frac{f(2)}{5} \pmod5 \ $$ $$t\equiv 4 \pmod5 $$ Thus, $$ f(4 * 5 + 2) = f(22) = 47195 $$ But it isn't true that $$f(22) \equiv 0\pmod5 $$ Where I am wrong ? – xawey Aug 31 '14 at 17:19
1

We have: $$x^2\equiv \frac{1}{99}\equiv 24\pmod{125}.\tag{1}$$ Since $8\cdot 125+24 =1024 = 32^2$ it follows that $x\equiv 32\pmod{125}$ is a solution of $(1)$.

Since $(\mathbb{Z}/125\mathbb{Z})^*$ is a cyclic group, the only other solution is $x\equiv -32\equiv 93\pmod{125}$.

Jack D'Aurizio
  • 353,855