# Congruence modulo m

1. Jul 24, 2011

### pc2-brazil

1. The problem statement, all variables and given/known data
Find a formula for the integer with smallest absolute value that is congruent to an integer a modulo m, where m is a positive integer.

2. Relevant equations
An integer x is congruent to an integer a modulo m if and only if:
$$x \equiv a \pmod m$$

3. The attempt at a solution
From the definition:
$$x \mod m = a \mod m$$
or:
$$x - a = km$$
where k is an integer.
From the division "algorithm":
$$x = mq + a\mod m$$
where q is the quotient.
But I'm not sure on how to proceed from here. The textbook gives a strange answer: $x \mod m$ if $x \mod m \leq \left \lceil m/2 \right \rceil$ and $(x \mod m) - m$ if $x \mod m > \left \lceil m/2 \right \rceil$
I would say that the smallest absolute value of x is when the quotient (q above) is 0. Thus:
$$x=a\mod m$$
According to the answer, $x=a\mod m$ is only true if $x \mod m \leq \left \lceil m/2 \right \rceil$, but I can't figure out why.