Finding the maximum or minimum of two numbers using mod

Question

To find the maximum of two coprime positive integers $a,b$:

$$\frac{ab \left[(a \bmod{b}) \bmod{a}) + ((b \bmod{a}) \bmod{b})\right]}{(a \bmod{b})(b \bmod{a})}=\max(a,b).$$

From this, you can also get

$$\frac{(a \bmod b)(b \bmod a)}{((a \bmod{b}) \bmod{a}) + ((b \bmod{a}) \bmod{b})}=\min(a,b).$$

You can get around the coprime requirement easily. If $f(a,b)$ is either of the functions above, then if they're coprime, take $f(a+1,b+1)-1$, which will work unless $a=b$, in which case it will recurse forever I guess.

---

Why it works

The key mechanism is that $a \bmod b$ only changes $a$ if $a>b$, otherwise it stays the same.

First, consider $(a\bmod{b})\bmod{a}$. If $a<b$, then $a\bmod b=a$; it doesn't affect it. So if $a<b$, the second mod will give you $a \bmod a=0$. But if $a>b$, $a \bmod b$ will give you some remainder smaller than $b$.

So out of the top two mod expressions that get summed, one will be $0$, the other will be $\max(a,b) \bmod { \min(a,b) }$.

Meanwhile on the bottom, you'll have $\min(a,b) \cdot (\max(a,b) \bmod \min(a,b))$. Overall, you're looking at:

$$\frac{(\max(a,b) \bmod \min(a,b))\cdot a \cdot b}{(\max(a,b) \bmod \min(a,b)) \cdot \min(a,b)}$$

The ugly mod terms cancel out, and you just have $ab/\min(a,b)$, which cancels out the smaller of $a,b$ and leaves you with $\max(a,b)$.

---

Example

Let $a=3,b=5$.

$$\frac{(3 \pmod{5} \pmod {3} + 5 \pmod{3} \pmod{5})\cdot 3\cdot 5}{(3 \pmod{5})(5 \pmod{3})}$$

$$\Longrightarrow \frac{(3 \pmod {3} + 2 \pmod{5})\cdot 3\cdot 5}{(3) \cdot (2) }$$

$$\Longrightarrow \frac{2 \cdot 3 \cdot 5}{2\cdot 3}=5=\max(3,5).$$

Answer 1

Here's a simpler test ...

• if $a\bmod b= a$ then $0\leq \vert a\vert\leq \vert b\vert $, else $a\bmod b\neq a$ and $\vert b\vert <\vert a\vert$

it's sort of a crappy test though.