Suppose $a$ and $d$ are integers and $m$ and $n$ are natural numbers such that $d|a^{m}-1$ and $d|a^{n}-1$. Prove that $d|a^{\text{gcd(m,n)}}-1$.
I just need some help getting started. I'm wondering if there is some theorem or lemma that I can cite that I'm missing or something maybe.
$$d\mid a^m-1,a^n-1\iff a^m\equiv a^n\equiv 1\pmod{d}$$
$$\iff \text{ord}_d(a)\mid m,n\iff \text{ord}_d(a)\mid \gcd(m,n)$$
$$\iff a^{\gcd(m,n)}\equiv 1\pmod{d}\iff d\mid a^{\gcd(m,n)}-1$$