# Remainders of division form a parabola

by Electro   Last Updated May 28, 2020 03:20 AM - source

If we plot the remainders $$a b \bmod n$$ for $$a, b, n \in \mathbb{Z}_{>0}$$ such that $$a < n < b$$ where $$a$$ and $$b$$ are fixed, in many cases, the points form a parabola given by quadratic equation $$(a - x)(b - x) + x = 0$$. In particular, it can be proven that this always happens if $$a = c^2$$ and $$b = (c+1)^2$$ for some $$c \in \mathbb{Z}_{>0}$$. Is there any nice explanation for this phenomenon?

Tags :

Let's say you want to compute $$\tt{Mod[ab,n]}$$ when $$\tt{a (and $$\tt{a},\tt{b}$$ are fixed).

Since $$\tt{b>n}$$, we may as well reduce $$\tt{b}$$ in the product, yielding $$\tt{a}\,\tt{Mod[b,n]}$$. If $$\tt{b/2 then this is $$\tt{a(b-n)}$$. If $$\tt{a}$$ isn't small enough, this product may still be too big. If $$\texttt{a}$$ is closer to $$\tt{n}$$ than $$\tt 0$$, then $$\tt a-n$$ will be smaller than $$\tt a$$ (in size) but $$\tt (a-n)(b-n)$$ is negative, yet can be made positive by adding a big enough multiple of $$\tt n$$; if we're lucky simply adding $$\tt n$$ will make it positive.

For $$\tt (a-n)(b-n)+n$$ to be positive (and thus the correct residue, since it is automatically $$\tt ),

$$\tt 0<(a-n)(b-n)+n$$

$$\updownarrow$$

$$\tt 0< \left(n-\frac{a+b-1}{2}\right)^2-\left(\frac{a+b-1}{2}\right)^2+ab$$

for all $$\tt a. Since $$\tt n=(a+b-1)/2$$ is in between $$\tt a$$ and $$\tt b$$, it would suffice for the minimum:

$$\tt (a+b-1)^2<4ab$$

Thus, this condition (with $$\tt b/2) is sufficient (but perhaps not necessary) for

$$\tt Mod[ab,n]=(a-n)(b-n)+n.$$

runway44
May 28, 2020 02:38 AM