Proof quadratic congruent equation has no solutions in $\mathbb{N}$

Question

In computer science, quadratic probing is used in hash tables. We choose a $c_1$ and $c_2$ in the hash formula $h(k,i) = (h'(k) + c_1 i + c_2 i^2) \mod{m}$ where $h'(k) = k \mod{m}$ and $m$ is the size of the table. Now say I choose $c_1$ and $c_2$ to be $1$ and $m = 13$. We want $h(k,i)$ to be a permutation of the numbers $0,1,2,...,12$.

It appears that choosing value $1$ for constants $c_1$ and $c_2$ is not a fitting match for this problem. I think it might has to do with the fact that $13$ is prime.

Anyhow, I want to show that:

$\nexists_{i \in \mathcal{n}}: h(k,i) = ((k \mod{13}) + i + i^2)\mod{13} = q$

Where using $q = (k+1)\mod{13}$ will work. For example; there does not exists an $i \in \mathbb{N}$ such that

$h(5,i) = 6$.

I rewrite;

$h(5,i) = ((5\mod{13}) + i + i^2)\mod{13} = (5 + i + i^2)\mod{13} = 6$

Which holds iff

$(i^2 + i - 1)\mod{13} = 0$.

I can't manage to get a formal proof there exists no such $i \in \mathbb{N}$, or am I doing something wrong here? Any help would be greatly appreciated!

Answer 1

You're using modular arithmetic modulo 13, so 0=13=26=..., 1=14=27=... and the equations really mean the numbers are equal. You have only to check thirteen numbers, there is no point trying others. If none of the thirteen is the root of your equation, you have your formal proof that the solution does not exist.

If you want to check other equations, two further facts may be of use:

1. Quadratic formula mostly works even in modulo arithmetics, at least when computing modulo odd prime. Just verify its proof if in doubt, it's short.
2. Computing square root in modular arithmetic is more tricky, but if you just want to check if the square root exists, you can use Legendre symbol.

---

Ok, maybe now I better understand your question. Going on:

• Constant k does not influence whether the function $h(i)=i^2+i+k$ is a permutation on $\mathbb{Z}_{13}$. It just adds some "rotation", but that does not matter when checking one-to-one correspondence - the adding of constant is itself bijection, it cannot change the "bijectivness".
• So the question is: Is the function $g(i)=i^2+i$ bijective in $\mathbb{Z}_{13}$ ? And the answer is NO, because $i^2+i=i(i+1)$, so solving $i(i+1)=0$ we see g(0)=g(12)=0, so we have two elements 0 and 12 both mapping to zero, so the function is not bijective and because we are on finite set, there has to be some number that is not mapped upon.