For every positive integer n, the number $a^{2^n}−1$ has at least n+1 distinct prime divisors Let $a>3$ be an odd integer. Prove that for every positive integer $n$, the number $a^{(2^{n})}-1$ has at least $n+1$ distinct prime divisors.
This problem smells very strongly of induction, but maybe a more complex version than I am trying.
What I have done so far:
Let $a=2k+3$ for positive integers $k$.
Proof by induction.
Base case:
If $n=1$, then $a^{(2^n)}-1$ must have at least one prime divisor (it's greater than 1).
So now assume for $n=k$, that is, $a^{(2^k)}-1$ has at least $k+1$ distinct prime divisors.
So let $a^{(2^k)}-1=p_1 \cdot p_2 \cdot p_3 \cdots p_k \cdot p_{k+1} \cdot m$ for some positive integer $n$ and for distinct primes $p_1, \;p_2, \;p_3, \; \cdots , \;p_{k+1}$.
Now consider $n=k+1$. If $n=k+1$ then the given equation becomes $(p_1 \cdot p_2 \cdot p_3 \cdots p_k \cdot p_{k+1} \cdot m+1)^2-1=(p_1 \cdot p_2 \cdot p_3 \cdots p_k \cdot p_{k+1})(p_1 \cdot p_2 \cdot p_3 \cdots p_k \cdot p_{k+1}+2)$. Will this necessarily have $k+2$ distinct prime divisors, because if so the induction is complete? 
 A: $$ a^{2^{n+1}} - 1 = \left( a^{2^n} - 1 \right)  \left( a^{2^n} + 1 \right) $$
and
$$  \gcd( a^{2^n} - 1 , a^{2^n} + 1  ) = 2. $$
A: Let $a=2k+3$ for positive integers $k$.
Proof by induction:
Base Case: If $n=1$, then $a^2-1=(a+1)(a-1)=4(k+1)(k+2)$. As $gcd(k+1,k+2)=1$ and both $k+1$ and $k+2$ are greater than $1$, $a^2-1$ has at least $2$ distinct prime divisors.
Now assume for $n=q$, that is, assume that $a^{2^q}-1$ has at least $q+1$ distinct prime divisors ($q$ is a positive integer).
So let $a^{2^q}-1=p_1 \cdot p_2 \cdot p_3 \cdots p_k \cdot p_{k+1} \cdot m$ for some positive integer $m$ and for distinct primes $p_1, \; p_2, \; p_3, \; \dots  \; p_k, \; p_{k+1}$.
WLOG $p_1<p_2<p_3<p_4< \; \cdots \; p_k<p_{k+1}$.
Now, as $a^{2^q}$ is an odd square it is congruent to $1 \pmod{4}$. So $p_1=2$ and $m$ is even.
Consider $n+q+1$,
$a^{2^{q+1}}-1=a^{2^q+2^q}-1=(a^{2^q}-1)(a^{2^q}+1)=(2p_2p_3 \cdots p_{k+1} \cdot m)(2p_2p_3 \cdots p_{k+1} \cdot m +2)$      (from above)
$=4(p_2p_3 \cdots p_{k+1} \cdot m)(p_2p_3 \cdots p_{k+1} \cdot m+1)$ this is clearly divisible by the $k+1$ original primes. But as $m$ is even $(p_2p_3 \cdots p_{k+1} \cdot m+1)$ is odd and thus cannot be divisible by any of the $k+1$ original primes ($gcd(a^{2^q}-1,a^{2^q}+1)=2$). It is thus a new prime or divisible by a new prime. 
Hence, $a^{2^{q+1}}-1$ is divisible by at least $q+2$ primes thus completing the induction.
Therefore, by the principle of induction, for odd positive integers $a>3$, $a^{2^n}-1$ is divisible by $n+1$ distinct primes for all positive integers $n$.
Note: the little hiccup is that you needed to establish that $m$ was even.
