divisibility - Gcd number theory proof: $(a^n-1,a^m-1)= a^{(m,n)}-1$

Prove that if $a>1$ then $(a^n-1,a^m-1)= a^{(m,n)}-1$

where $(a,b) = \gcd(a,b)$

I've seen one proof using the Euclidean algorithm, but I didn't fully understand it because it wasn't very well written.
I was thinking something along the lines of have $d= a^{(m,n)} - 1$ and then showing
$d|a^m-1$ and $d|a^n-1$ and then if $c|a^m-1$ and $c|a^n-1$, then $c\le d$.

I don't really know how to show this though...

I can't seem to be able to get $d* \mathbb{K} = a^m-1$.

Any help would be beautiful!