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
    Should the title read "...mod 4 if x is odd?"2012-09-05
  • 0
    No.This is not the same!2012-09-05
  • 0
    It's not a matter of being appropriate or not, it's a matter of being comprehensible or not.2012-09-05
  • 0
    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$?2012-09-05
  • 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
    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$.2012-09-05
  • 0
    @Petr Pudlák I think I'm going to remove what you put because it's overcomplicated.2012-09-05
  • 0
    @rschwieb No problem.2012-09-05
0

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

  • 0
    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?2012-09-05
  • 0
    This question is closely connected with square residues or to be more precise with centered square residues!http://math.stackexchange.com/questions/186758/reformulation-of-square-residues-for-odd-numbers. Example for 25:25-(25-1)/4 = 192012-09-05
  • 1
    @rschwieb: the question has changed (it is now $\pmod x$)2012-09-05