# Divisibility of integers

Let $n > 1$ be an integer. Then $2^n - 1\nmid 3^n - 1$. I don't know how to prove it. Can anybody help me, please?

In general, for a fixed positive integer $a > 1$, has $a^n - 1|(a +1)^n - 1$ any integer solutions?

-
Have you tried using the standard factorization: $a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+..+a^{n-k}b^{k-1}+...+b^{k-1})$? – AQP Mar 6 '12 at 6:33
Maybe you could work in the case n=2k+1, since , when n is even, $2^n -1$ is divisible by 3, and $3^n-1$ is clearly not. – AQP Mar 6 '12 at 18:03
@ksjo3: Please tell us the source of the problem. Did you get it somewhere? Do you know there is a solution? Did you make it up yourself? – Aryabhata Mar 6 '12 at 18:04
It is an exercise in a book. I don't konw how to prove it. – ksj03 Mar 7 '12 at 2:38
@ksjo3 Please tell us which book, and where in that book. This could help people know what sort of techniques you are expected to apply to the problem. – Matthew Conroy Mar 7 '12 at 22:58

As @AQP said, if $n$ is even then $3\mid 2^n-1$ so $2^n-1\nmid 3^n-1$.

If $n=2k-1$ then $2^n-1 \equiv 1 \pmod{3}$ so $2^n-1$ is a quadratic residue mod 3.

$3(3^n-1)=3^{2k}-3$ so $2^n-1 \mid 3^n-1$ would require that $3^{2k}\equiv 3 \pmod{2^n-1}$, i.e. that 3 is a quadratic residue mod $2^n-1$.

But $2^n-1\equiv 3 \pmod{4}$ so is divisible by an odd number of primes $p\equiv 3\pmod{4}$. By quadratic reciprocity 3 cannot be a quadratic residue mod $2^n-1$, hence $2^n-1\nmid 3^n-1$.

-

The idea used below is very close to the one used by @Zander. It will not be a surprise to those who have seen my other posts that the details take longer.

If $n$ is even, then $2^n-1$ is divisible by $3$, so $2^n-1$ cannot divide $3^n-1$ unless $n=0$.

So let $n>1$ be odd. Let $p$ be a prime that divides $2^n-1$. Then since $2^n \equiv 1 \pmod{p}$, the order of $2$ modulo $p$ is odd, so $2$ is a quadratic residue of $p$. If furthermore $2^n-1$ divides $3^n-1$, then $3^n \equiv 1 \pmod {p}$, and therefore $3$ is also a quadratic residue of $p$.

The number $2$ is a quadratic residue of the odd prime $p$ iff $p\equiv \pm 1 \pmod{8}$. So $p$ must be of the shape $24k+1$, $24k+7$, $24k+17$, or $24k+23$. But by Quadratic Reciprocity, $3$ is a non-residue of $p$ if $p$ is of the shape $24k+7$ or $24k+17$. Thus it is enough to show that if $n$ is odd, then $2^n-1$ has at least one prime factor of the shape $24k+7$ or $24k+17$.

To do this, we show that not all primes in the prime factorization of $2^n-1$ can be of shapes $24k+1$ and/or $24k+23$. Suppose to the contrary that they all are. We will obtain a contradiction.

Note that $24k+1$ is congruent to $1$ modulo both $3$ and $8$, while $24k+23$ is congruent to $-1$ modulo both $3$ and $8$. Since $2^n-1$ has shape $8s-1$, its prime factorization must have an odd number of occurrences of (not necessarily distinct) primes of the form $24k+23$. But that implies that $2^n-1\equiv -1 \pmod 3$, which is not the case when $n$ is odd.

-
You are right. Thanks for explanation. – ksj03 Mar 10 '12 at 4:53
The assertion that $2^m−1$ cannot divide $3^n−1$ if $m>1$ is not correct. Let $m$ be any odd positive integer, $n = \phi(2^m - 1)$, then by Euler's Theorem we have $3^n\equiv1\mod 2^m - 1$. – ksj03 Mar 11 '12 at 5:25