Why Does x*(x+1)%5 Only Yield the Remainders 0, 1, and 2?

[AngelofMusic]

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 x^2+x 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.

 

[NateTG]

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

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

I can pair off all but one of the numbers so that for each pair, x,y , (x+y)\equiv-1
Then I can multiply both sides by (x-y)
(x+y)(x-y) \equiv -1 \times (x-y)
x^2-y^2\equiv y-x
move the x's and y's together:
x^2+x=y^2+y
So x and y have the same residue.

 

[M98Ranger]

Hi there,

Thank you for reaching out with your question about modulo and quadratic probing in hashing functions. It's great to see that you are actively reviewing and trying to understand the concepts in your computer science class.

To answer your question, there is indeed a property of x^2+x that leads to the trend you are observing. This property is known as the "binomial theorem" and it states that when you expand the expression (x+1)^2, you will get x^2+2x+1. When you divide this by 5, you will see that the remainder can only be 0, 1, or 2.

To understand why this is the case, let's look at the expansion of (x+1)^2 in terms of modulo 5:

(x+1)^2 = (x^2 + 2x + 1) % 5

Now, let's consider the possible remainders for each term:

x^2 % 5 can only be 0, 1, 2, 3, or 4
2x % 5 can only be 0, 2, or 4
1 % 5 can only be 1

So, when we add these terms together, we can see that the only possible remainders are 0, 1, or 2. This explains why you are only getting these results in your exercise.

I hope this helps to clarify why this trend is occurring. Keep up the great work in your studies!