2
$\begingroup$

Because:

A) for odd $x$ and $x \equiv 1\pmod {4}$ the upper formula is the same as $x - (x-1)/4$

B) for odd $x$ and $x \equiv 3\pmod {4}$ the upper formula is the same as $(x + 1)/4$

Example A) ((17-1)/2)^2 mod 17 = 13 or 17-16/4=13 , 17 mod 4 = 1

Example B) ((19-1)/2)^2 mod 19 = 5 or (19+1)/4=5 , 19 mod 4 = 3

This question is closely connected with square residues or to be more precise with "centered" square residues! reformulation of square residues for odd numbers? Example for 25:25-(25-1)/4 = 19

  • 0
    Please edit your problem then... it's not clear.2012-09-05

2 Answers 2

4

Since you have made it clear you want to work $\pmod{x}$, then the expression is always $4^{-1}$ for odd $x$.

Added Someone came along and added a very long explanation for a short computation I took for granted. Here is what I was thinking: Since $x=0\pmod{x}$, $((x-1)/2)^2=(-1/2)^2=1/4=4^{-1} \pmod{x}$

You can easily compute what $4^{-1}$ is for your given $x$ with the Euclidean algorithm. Use the alg to find $a,b$ such that:

$ax+4b=1$

Then $4^{-1}=b\pmod{x}$

  • 0
    @rschwieb No problem.2012-09-05
0

Why not if $x=1 \pmod 4$ then $0$, else $1$?

  • 1
    @rschwieb: the question has changed (it is now $\pmod x$)2012-09-05