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?

  • 1
    $\begingroup$ but why $2*k+3$?maybe it is better $2*k+1$? $\endgroup$ – dato datuashvili Apr 10 '13 at 4:52
  • 1
    $\begingroup$ because $a$ is odd and $a>3$ so $a \geq 5$. $\endgroup$ – John Marty Apr 10 '13 at 4:54
  • $\begingroup$ aa ok clear.sorry $\endgroup$ – dato datuashvili Apr 10 '13 at 4:55

$$ 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. $$

  • $\begingroup$ so therefore $a^{2^{k+1}}-1$ has $k+2$ distinct prime divisors. Right? $\endgroup$ – John Marty Apr 10 '13 at 5:03
  • $\begingroup$ @JohnMarty, that's about it. $\endgroup$ – Will Jagy Apr 10 '13 at 5:06
  • 1
    $\begingroup$ Thanks so much, I'd really done most of the work and was a bit blind at the end! $\endgroup$ – John Marty Apr 10 '13 at 5:10
  • $\begingroup$ @JohnMarty, you do need to be careful about the beginning case, $n=1,$ or $a^2 - 1.$ Indeed, $3^2 - 1 = 8$ has only one prime divisor. You need to carefully work out why, with odd $a \geq 5,$ if one of $\{a-1, a+1 \}$ is a power of 2, the other one is not, i.e. has an odd prime factor. $\endgroup$ – Will Jagy Apr 10 '13 at 17:02
  • $\begingroup$ Yeah, I've taken that into account in writing my proof, despite stuffing it up in the question. There's also a slight hiccup in your argument at the end. I'm going to post a full solution soon. $\endgroup$ – John Marty Apr 10 '13 at 22:45

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.