When is $(x \textrm{ mod } a) \textrm{ mod } b = (x \textrm{ mod } b) \textrm{ mod } a$?

Question

I don't know when the equation $(x \textrm{ mod } a) \textrm{ mod } b = (x \textrm{ mod } b) \textrm{ mod } a$ holds.

I am looking for non-trivial necessary of sufficient conditions on $a,b$, and $x$. Is there any special conditions when they are in $\mathbb{Z}$ or when they are in $\mathbb{Z}/n\mathbb{Z}$?

For now I only found that if $a$ is a multiple of $b$, then it holds for all $x$.

Thank you for the help.

Answer 1

Let $a,b$ be positive integers with $a\le b$.

Claim:$\;$An integer $x$ satisfies the equation $$ (x\;\text{mod}\;a)\;\text{mod}\;b = (x\;\text{mod}\;b)\;\text{mod}\;a \qquad\;\;\;\; $$ if and only if $$ a\,{\Large{\mid}}\!\left(b\left\lfloor{\small{\frac{x}{b}}}\right\rfloor\right) $$ Proof:

Fix positive integers $a,b$ with $a\le b$, and let $x$ be an integer.

Let $r=x\;\text{mod}\;a$ and let $s=x\;\text{mod}\;b$.

By the division algorithm, we get $$ r=x-a\left\lfloor{\small{\frac{x}{a}}}\right\rfloor \\ s=x-b\left\lfloor{\small{\frac{x}{b}}}\right\rfloor $$ Since $0\le r < a$ and $a\le b$ it follows that $r\;\text{mod}\;b=r$, hence \begin{align*} & (x\;\text{mod}\;a)\;\text{mod}\;b = (x\;\text{mod}\;b)\;\text{mod}\;a \\[4pt] \iff\;& r\;\text{mod}\;b=s\;\text{mod}\;a \\[4pt] \iff\;& r=s\;\text{mod}\;a \\[4pt] \iff\;& s\equiv r\;(\text{mod}\;a)\qquad\text{[since $0\le r < a$]} \\[4pt] \iff\;& x-b\left\lfloor{\small{\frac{x}{b}}}\right\rfloor \equiv x-a\left\lfloor{\small{\frac{x}{a}}}\right\rfloor \;(\text{mod}\;a) \\[4pt] \iff\;& b\left\lfloor{\small{\frac{x}{b}}}\right\rfloor \equiv 0 \;(\text{mod}\;a) \\[4pt] \iff\;& a\,{\Large{\mid}}\!\left(b\left\lfloor{\small{\frac{x}{b}}}\right\rfloor\right) \\[4pt] \end{align*} which completes the proof.