Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Congruence modulo m

  1. Jul 24, 2011 #1
    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:
    [tex]x \equiv a \pmod m[/tex]

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

    Thank you in advance.
     
  2. jcsd
  3. Jul 24, 2011 #2

    HallsofIvy

    User Avatar
    Science Advisor

    For example, If a= 5 and m= 7, then x= 5 (mod 7) if and only if x= 5+ 7k for integer k. k= 0 gives x= 5, of course, and k= -1 gives x= -2. The "smallest absolute value" is 2, not 5, because ⌈m/2⌉= 3 and 3< 5. If a= 3 then x= 3 (mod n7) if and only if x= 3+ 7k. k= 0 gives x= 3 while k= -1 gives 3- 7= -4. Now the "smallest absolute value" is 3.

    In general x= a (mod m) (for [itex]0\le a< m) if and only if x= a+ mk for integer k. k= 0 gives x= a> 0 and k= -1 gives a- m< 0. Which of those has smaller absolute value depends on how close a is to m.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook