Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

2 Answers

up vote 4 down vote accepted

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

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
1  
@rschwieb: the question has changed (it is now $\pmod x$) –  Ross Millikan Sep 5 '12 at 17:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.