# What is the fastest or usual way to calculate $(\frac{x-1}{2})^2$ mod $x$ if $x$ is odd?

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

-
Should the title read "...mod 4 if x is odd?" – rschwieb Sep 5 '12 at 16:36
No.This is not the same! – Bojan Vasiljević Sep 5 '12 at 16:41
It's not a matter of being appropriate or not, it's a matter of being comprehensible or not. – rschwieb Sep 5 '12 at 16:43
If $x\equiv 1\pmod 4$ then $({x-1\over2})^2\equiv 0\pmod 4$ and if $x\equiv 3\pmod 4$ then $({x-1\over2})^2\equiv 1\pmod 4$ (in fact $({x-1\over2})^2\equiv 1\pmod 8$). However, how should $x+1\over 4$ be the same as $({x-1\over2})^2 \pmod 4$? – Hagen von Eitzen Sep 5 '12 at 16:44
Please edit your problem then... it's not clear. – rschwieb Sep 5 '12 at 16:46

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

-
The point being that if $x = 2y+1$, $4 ((x-1)/2)^2 = (x-1)^2 \equiv 1 \mod x$. If $x \equiv 3 \mod 4$, i.e. $x = 4j-1$ for some integer $j$, then $4j \equiv 1 \mod x$, so $4^{-1} \equiv j$. If $x \equiv 1 \mod 4$, i.e. $x = 4j + 1$, then $4^{-1} \equiv -j \equiv 3j+1 \mod x$. – Robert Israel Sep 5 '12 at 17:10
@Petr Pudlák I think I'm going to remove what you put because it's overcomplicated. – rschwieb Sep 5 '12 at 18:21
@rschwieb No problem. – Petr Pudlák Sep 5 '12 at 18:53

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

-
I'm having a bit of trouble with the person's question being mod 4, and at the same time dividing by 4, which isn't invertible mod 4... do you have a sense for what he's asking? – rschwieb Sep 5 '12 at 16:45
This question is closely connected with square residues or to be more precise with centered square residues!math.stackexchange.com/questions/186758/…. Example for 25:25-(25-1)/4 = 19 – Bojan Vasiljević Sep 5 '12 at 17:04
@rschwieb: the question has changed (it is now $\pmod x$) – Ross Millikan Sep 5 '12 at 17:23