02.05.08 Q.01(a)

02.05.08 Q.01(a)

ohad (guest) 27 Jan 2017 09:06

they ask for two solutions to the equation
did someone solve this?

The (guest) 27 Jan 2017 12:00

Denote $a-b = 2m \mod (p-1)$
Note that since $0 \le a,b\le p-2$:
$|m|<\frac{p-1}{2}$
Take the two equations from the question, and subtract them to get:
$-2y = a-b \mod (p-1)= 2m \mod (p-1)$
And so
$y = A(p-1)-m$
And since $|m|<\frac{p-1}{2}$, this has two solutions in the range $0\le y \le p-2$:
$y=p-1 - m \mod (p-1)$
$y=m \mod (p-1)$

x can now be found for each case.

Eyal (guest) 27 Jan 2017 19:25

I didn't quite inderstand your explanation.
especially, if 0<=a,b<=p-2, while calculations are made mod (p-1) then they can take on all values.
|m| could have |m|=(p-1)/2 when a=(p-1)/2 and b=0, assuming (p-1)/2 is even, and I suppose it might…

Anyway, if you mark a-b=2m, then there is another m'=(p-1)/2 + m which also has it that 2m' = p-1+2m=2m
and so,
-2y=2m, leads to y1=-m=p-1-m and y2 = -(p-1)/2 - m = (p-1)/2 - m

Please tell me if I had something wrong,
and I hope that helps.

The (guest) 27 Jan 2017 20:08

Firstly, if $a=\frac{p-1}{2}$ and $b=0$ then $|m|=\frac{p-1}{4}$ and not $|m|=\frac{p-1}{2}$…

Secondly, you're right.
Because I mis-typed
$y=m \mod (p-1)$ instead of $y = -m \mod (p-1)$

I missed my mistake (that both solutions I gave would be equivalent, had I written what I meant)