From what I know, the question can be solved from congruence modulo or without. Since the question is before the concept of congruence modulo in the book which I am using, I guess a solution without using modulo should be the answer.
Here's what I have tried till now -
Let $a^{2^n}$ = k
$a^{2^m} = a^{2^{n+r}}$ (where $r ≠ 0$)
$a^{2^m} = a^{2^n\cdot 2^r} + 1 = k^{2^r} + 1$
The expression then simplifies to $\gcd(k+1, k^{2^r} + 1)$
Ideally, there should be two cases - one where $k$ is odd and one where $k$ is even. But I am unable to find a solution on that basis. Thanks in advance!
Source : Challenge and Thrill of Pre-College Mathematics