Modulo Arithmetic Shortcut

Question

Consider two numbers $x$ and $y$ such that $0<x<y<7500$. Consider a function $m(x,y)$, defined: $m(x,y)= (2019201913*x + 2019201949*y ) \bmod 2019201997$.

May this function be simplified?

Define $m(x,y) = (ax+by)/c$. I noticed that a, b, and c are equal to 8 orders of magnitude ($20192019 \_ \_$) .

$2019201913\equiv-84\bmod2019201997$ and $2019201949\equiv-48\bmod2019201997$ — J. W. Tanner, Dec 27 '19 at 00:28
Thus $m'(x,y) = 2019201997-(84x + 48y)$?... Obviously, this breaks down after a certain domain, specifically for values of $(x,y)$ for which $m'(x,y)<0$. However, for this specific problem, $0<x<7500$ and $0<y<7500$, so $m'$ will never be less than $0$. All correct? — Matthew Anderson, Dec 27 '19 at 00:39
You still have to do modular reduction, but it’s simpler to multiply by $84$ than to multiply by $2019201913$ — J. W. Tanner, Dec 27 '19 at 00:43
Okay. Given that $0<x<y<7500$, would I still have to perform modular reduction? — Matthew Anderson, Dec 27 '19 at 00:45
$m(x,y)\equiv -12(7x+4y)\pmod{!2019201997}.\ $ "Simpler" depends on what you plan to do with it. — Bill Dubuque, Dec 27 '19 at 00:52

score 0 · Accepted Answer · answered Dec 27 '19 at 19:11

Given that:

$2019201913 ≡ -84 \pmod{2019201997}$
$2019201949 ≡ -48 \pmod{2019201997}$

$m(x,y)$ may be simplified to $m(x,y)= (-84x-48y) \bmod 2019201997 $. Given that $x,y \in (0,7500) $, $m(x,y)$ can be considered to be equal to $2019201997-84x-48y$. This, of course, may be further simplified to $2019201997−12(7+4)$.

Modulo Arithmetic Shortcut

1 Answers1