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?

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. $$

May 28, 2020 02:38 AM

- Serverfault Help
- Superuser Help
- Ubuntu Help
- Webapps Help
- Webmasters Help
- Programmers Help
- Dba Help
- Drupal Help
- Wordpress Help
- Magento Help
- Joomla Help
- Android Help
- Apple Help
- Game Help
- Gaming Help
- Blender Help
- Ux Help
- Cooking Help
- Photo Help
- Stats Help
- Math Help
- Diy Help
- Gis Help
- Tex Help
- Meta Help
- Electronics Help
- Stackoverflow Help
- Bitcoin Help
- Ethereum Help