- #1
AngelofMusic
- 58
- 0
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.
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.