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: Quick question about modulo

  1. Apr 23, 2004 #1
    I'm doing review exercises for my computer science class and we're discussing hashing functions. One of them involves quadratic probing and I came upon an interesting trend. Whenever I have:

    x*(x+1)%5 where % stands for the modulo operator, and x > 0 and is an integer, I can never seem to get any results except 0, 1 and 2.

    Is there some inherent property of [tex]x^2+x[/tex] such that whenever it is divided by 5, it only produces remainders in 0, 1, and 2? This isn't part of the homework, and the trend has held up for the few data points I tried, but I'm wondering if there's any number x that would give another remainder such as 3 or 4.

    I tried proving by induction, but that got me nowhere. I tried reasoning it out that: x(x+1) will always be even, since it will be even number * odd, but that means that doesn't really narrow down the possible remainders.

    I don't need a rigorous proof or anything, but can anyone explain why this is? I haven't taken number theory so I don't know much about this.
  2. jcsd
  3. Apr 23, 2004 #2


    User Avatar
    Science Advisor
    Homework Helper

    The only possible results are 0,1 and 2 - you only need to check the residues mod 5.

    In general, for a prime [tex]p[/tex], [tex]x^2+x[/tex] takes at most [tex]\frac{p+1}{2}[/tex] values mod [tex]p[/tex]

    I can pair off all but one of the numbers so that for each pair, [tex]x,y[/tex] , [tex](x+y)\equiv-1[/tex]
    Then I can multiply both sides by [tex](x-y)[/tex]
    [tex](x+y)(x-y) \equiv -1 \times (x-y)[/tex]
    [tex] x^2-y^2\equiv y-x[/tex]
    move the [tex]x[/tex]'s and [tex]y[/tex]'s together:
    So [tex]x[/tex] and [tex]y[/tex] have the same residue.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook