I am new to modular arithmetic, so I was reading multiple articles on the web. This khanacademy page describes it very intuitively.

However, I have one query for the below equation: $$A\mod B = (A+K.B)\mod B$$ Is there a mathematical way to find the least (other than the trivial 0) $K$ for which the above equation holds true or the only possible approach is to use a loop until I find one?

Or, if I have two numbers $x$ and $y$, how would I mathematically find least $K$ such that $$(x.K)\mod y = 0$$

  • $\begingroup$ The least $K$ is $K=0$ (if you take $K$ among the natural numbers)… $\endgroup$ – Bernard May 26 '17 at 18:17
  • $\begingroup$ Yes, that's trivial. My bad. I should have stated it. Updating it now. $\endgroup$ – user3243499 May 26 '17 at 18:19
  • $\begingroup$ The whole point is it holds for any integer $K$, so $K=1,2,3,...$ all work $\endgroup$ – Matt B May 26 '17 at 18:20
  • $\begingroup$ @MattB Modular arithmetic seems confusing at first. I have updated the question description to include a case where I want to check for specific reminder 0. $\endgroup$ – user3243499 May 26 '17 at 18:26
  • $\begingroup$ Least $K$ from among which set? ...$A\equiv A+KB\pmod B$ for all $K\in \mathbb Z.$ $\endgroup$ – DanielWainfleet May 26 '17 at 19:13

The statement $a \mod{b} = c \mod{b}$ is equivalent to saying that there exists some integer $r$ such that $a-c=rb$. So in particular if $a - (a+kb)=kb = k \cdot b$ hence $a \mod{b} = a+kb \mod{b}$ is always true for any integer $k$.

For your second part, we want to know what is the least $K$ such that $xK \mod{y} = 0 \mod{y}$ for some given integers $x,y$. Or to rephrase that, we want to know what is the least $K$ such that there exists an integer $r$ with $xK=ry$. Clearly $K=y$ works as we can then take $r=x$ but there's no guarantee that this is the least possible solution.

Indeed, consider the case $x=4$ and $y=6$. Then $K=y=6$ works, but we could have taken $K=3$ (with $r=2$) as $4 \times 3 = 6 \times 2$.

Looking at this more closely, it turns out then whenever $x$ and $y$ share a common divisor, we can take this factor out of $y$, so in the end the least possible value is $K=\frac{y}{\gcd(x,y)}$ (this is always an integer).

To see that this works, note that $xK=\frac{xy}{\gcd(x,y)}=y\frac{x}{\gcd(x,y)}$ so $r=\frac{x}{\gcd(x,y)}$. I'll leave you to check that this is actually minimal.

  • $\begingroup$ Thanks for such an intuitive answer. Here K is minimal since we divide $y$ with the greatest possible divisor which is also a divisor of $x$. $\endgroup$ – user3243499 May 26 '17 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.