Show $\bmod m\!:\ ar\equiv b,\ br\equiv a\Rightarrow a^2\equiv b^2$

Question

Suppose that $ar\equiv b$ (mod $m$) and $br\equiv a$ (mod $m$) for some $r$. Show that $a^2\equiv b^2$ (mod $m$).

I've tried quite a few different things and I'm unable to get rid of terms with $r$ in it (if that is even necessary) to show that $a^2=b^2=mz$ for some integer $z$.

I know that $ar-b=mx$ and $br-a=my$ for integers $x,y$. I tried using different mod properties like sum, difference, and product to see if it helped, but didn't have any luck. I ended up with $(a^2-b^2)(r^2-1)=m^2xz=m(mxy)$, but this is was no help and just made things more complicated. Any hints are greatly appreciated. I know there is something obvious that I haven't considered and my mind is just stuck in a certain mode of thinking and I can't escape it at the moment.

Answer 1

$$a^2\equiv abr\equiv bar\equiv b^2\pmod m.$$

Answer 2

Below is a conceptual derivation, showing how to view it as arising via CM = cross multiplication criterion for fraction equivalence. If $a$ and $b$ are invertible then we can use familiar properties of (modular) fractions, where we define $\,a/b := ab^{-1}.\,$ Solving for $r$ in both we obtain

$$\begin{align} \color{#c00}b\,r\equiv \color{#c00}a\\ \color{#0a0}a\,r\equiv \color{#0a0}b\end{align}\ \Longrightarrow\ \color{#c00}{\dfrac{a}b}\equiv r \equiv \color{#0a0}{\dfrac{b}a}\,\overset{\rm CM}\Longrightarrow\, \color{#c00}a\color{#0a0}a\equiv \color{#c00}b\color{#0a0}b\qquad\qquad $$

so $\,a^2\equiv b^2\,$ by CM. We can eliminate fractions to handle the case when $a$ or $b$ is not invertible. The proof of CM amounts to scaling the fractions to put them over a common denominator $ab$. We can do the same thing with the equations defining the fractions, where the denominator is just the coef of $\,r,\,$ e.g. $\, b\,r\equiv a \!\iff\! r\equiv a/b\,$ has denominator $\,b.\,$ So we want to scale both equations so they have the same coef of $\,r\,$ - which will necessarily be a common multiple of $a$ and $b$. We choose the simple multiple $\,ab,\,$ yielding

$$\begin{align} &a\times [b\,r\equiv a]\to \color{#c00}{ab\,r}\equiv a^2\\ &\:\!b\times [a\,r\equiv b]\to \color{#c00}{ba\,r}\equiv b^2 \end{align}\ \Rightarrow\ a^2\equiv b^2$$

This proof amounts to scaling the proof of the CM criterion by $\,ab,\,$ so we work only with (modular) integers (vs. fractions). Of course we can do the same with the general CM rule for $\frac{a}b\equiv \frac{c}d$ to obtain

$$ \begin{align} &b\,r\equiv a\\ &d\,r\equiv c\end{align}\ \Longrightarrow\ ad\equiv bc\qquad\qquad $$

Remark $ $ More generally, from an equational point of view, we can view the above derivation as cross-multiplying the equations to eliminate $\,r.\,$ From this standpoint we can view the above as a special case of general elimination algorithms such as the Grobner basis algorithm (which is a (multivariate) generalization of both the division (with remainder) algorithm and Gaussian elimination). Even more generally we can view it as a special case of various overlapping (unification) methods of generating consequences of equations used in term rewriting systems, e.g. the Knuth Bendix algorithm. For example, see here where I show how to derive a proof of uniqueness of inverses this way.

Answer 3

Since $ar^2 \equiv br \equiv a$, we have $b^2\equiv a^2r^2\equiv a^2 \bmod m$