6
$\begingroup$

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?

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

2 Answers 2

12
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ so therefore $a^{2^{k+1}}-1$ has $k+2$ distinct prime divisors. Right? $\endgroup$
    – John Marty
    Apr 10, 2013 at 5:03
  • $\begingroup$ @JohnMarty, that's about it. $\endgroup$
    – Will Jagy
    Apr 10, 2013 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, 2013 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, 2013 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, 2013 at 22:45
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .