Hint $\, $ By below $\, a^M\!-\!1,\:a^N\!-\!1\ $ and $\, a^{(M,N)}\!-\!1\ $ have the same set $\,S$ of common divisors $\,d,\, $ therefore they have the same greatest common divisor $\ (= \max\ S).$
$$\begin{eqnarray}\ {\rm mod}\:\ d\!:\ a^M\!\equiv 1\equiv a^N&\!\iff\!& {\rm ord}(a)\ |\ M,N\!\color{#c00}\iff\! {\rm ord}(a)\ |\ (M,N)\!\iff\! \color{#0a0}{a^{(M,N)}\!\equiv 1}\\[.2em]
{\rm i.e.}\ \ \ d\ |\ a^M\!-\!1,\:a^N\!-\!1\! &\!\iff\!\!&\ d\ |\ \color{#0a0}{a^{(M,N)}\!-\!1},\qquad\,\ {\rm where} \quad\! (M,N)\, :=\, \gcd(M,N)
\end{eqnarray}\ \ \ \ \ $$
Note $ $ We used the GCD universal property $\ a\mid b,c \color{#c00}\iff a\mid (b,c)\ $ [which is the definition of a gcd in more general rings]. $ $ Compare that with $\ a and, analogously, $\,\ a\subset b,c\iff a\subset b\cap c.\ $ Such universal "iff" characterizations enable quick and easy simultaneous proof of both directions.
The conceptual structure that lies at the heart of this simple proof is the ubiquitous order ideal. $\ $ See this answer for more on this and the more familiar additive form of a denominator ideal.
Generally: $\, \gcd(f(m), f(n)) = f(\gcd(m,n))\ $ if $\, f(n) \equiv f(n\!-\!m)\pmod{\!f(m)}\, $ and $\, f(0) = 0,\,$ which is proved by a simple induction in this answer.
In fact there is a $q$-analog: the result also holds true for polynomials $ \ f(n) = (x^n\!-\!1)/(x\!-\!1),\, $ and $\ x\to 1\ $ yields the integer case (Bezout identity) - see this answer for a simple proof.