Oh boy I didn't believe Eric Schneider when he first told me that this was a TST problem. One solution is presented here using Cyclotomic Polynomials.

Wait did they specifically mention you couldn't cite Zsigmondy?

The title is bad, since Zsigmondy is some-what different than the problem; the fact that all prime divisors of $a^n-1$ must divide $a^m-1$ is not included in the special cases of the theorem. However, here's a solution using the bomb. Solution: By Zsigmondy's theorem, there exists a primitive prime divisor of $a^n-1$ for all $a, n$, except for $(a,n)=(2,6), (2^k-1,2)$. In our first case, we can list out all of the possible $a^m-1$, with $m<n$, and find that none work (the complete list is $31, 15, 7, 3, 1$). Hence, we must examine the second case. If $(a, n)=(2^k-1, 2)$, any prime divisor must divide $(2^k-1)^2-1=(2^k)(2^k-2)=(2^{k+1})(2^{k-1}-1)$. The set of all prime divisors of $a^n-1$ is the set of prime divisors of $2^{k-1}-1$ and $2$. The only possible $m$ to examine is $m=1$, which yields $(2^k-1)-1=2^k-2=2(2^{k-1}-1)$. Thus $a^m-1$ is divisible by all of the prime divisors of $a^n-1$, and our solution set is $(a,n)=(2^k-1,2), (1,n)$, for arbitrary $n$. We are done. $\blacksquare$

PlatinumFalcon wrote: The title is bad, since Zsigmondy is some-what different than the problem; the fact that all prime divisors of $a^n-1$ must divide $a^m-1$ is not included in the special cases of the theorem. However, here's a solution using the bomb. Solution: By Zsigmondy's theorem, there exists a primitive prime divisor of $a^n-1$ for all $a, n$, except for $(a,n)=(2,6), (2^k-1,2)$. In our first case, we can list out all of the possible $a^m-1$, with $m<n$, and find that none work (the complete list is $31, 15, 7, 3, 1$). Hence, we must examine the second case. If $(a, n)=(2^k-1, 2)$, any prime divisor must divide $(2^k-1)^2-1=(2^k)(2^k-2)=(2^{k+1})(2^{k-1}-1)$. The set of all prime divisors of $a^n-1$ is the set of prime divisors of $2^{k-1}-1$ and $2$. The only possible $m$ to examine is $m=1$, which yields $(2^k-1)-1=2^k-2=2(2^{k-1}-1)$. Thus $a^m-1$ is divisible by all of the prime divisors of $a^n-1$, and our solution set is $(a,n)=(2^k-1,2), (1,n)$, for arbitrary $n$. We are done. $\blacksquare$ Just a small mistake,$n$ should be larger than 1

Our solutions just follow from the edge case exceptions of Zsigmondy's, which can be tested to work: \[\boxed{(1,c), \left(2^c-1, 2\right) ~ \forall ~ c \in \mathbb{N}}.\] Vacuous truth plus slightly ambiguous wording plus known theorem equals not exactly the best candidate for a TST question.

For this question, were you allowed zsigmondy? Else, does there exist any elementary way to prove this

Just edge cases of zsigmondy.