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?

Graph of (a - x)(b - x) + x = 0 and ab mod n



Answers 1


Let's say you want to compute $\tt{Mod[ab,n]}$ when $\tt{a<n<b}$ (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<n}$ 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 <n$),

$$ \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<n<b$. 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<n$) is sufficient (but perhaps not necessary) for

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

runway44
runway44
May 28, 2020 02:38 AM

Related Questions


Modular Forms: With special congruences!

Updated September 26, 2017 16:20 PM

Function that describes certain modulo function values

Updated October 22, 2017 20:20 PM

help on exercise for student on arithmetic

Updated May 05, 2019 23:20 PM

An elementary number theory problem

Updated August 19, 2017 08:20 AM