# How to find the least integer in modular arithmetic?

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

• The least $K$ is $K=0$ (if you take $K$ among the natural numbers)… – Bernard May 26 '17 at 18:17
• Yes, that's trivial. My bad. I should have stated it. Updating it now. – user3243499 May 26 '17 at 18:19
• The whole point is it holds for any integer $K$, so $K=1,2,3,...$ all work – Matt B May 26 '17 at 18:20
• @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. – user3243499 May 26 '17 at 18:26
• Least $K$ from among which set? ...$A\equiv A+KB\pmod B$ for all $K\in \mathbb Z.$ – DanielWainfleet May 26 '17 at 19:13

## 1 Answer

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.

• 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$. – user3243499 May 26 '17 at 19:02