4
$\begingroup$

Is it true that there are infinitely many nonprime integers $n$ such that $3^{n-1} - 2^{n-1}$ is a multiple of $n$?

  • 0
    I believe this follows from the existence of infinitely many Carmichael numbers, but maybe there is a more elementary proof.2010-07-29
  • 0
    I was just writing to refer to pseudoprimes :-)2010-07-29

3 Answers 3

11

I think I know how to prove it without using of Carmichael numbers.

Take $n = 3^{2^k} - 2^{2^k}$. Then it's not hard to prove by induction on $k$ that $2^k | n - 1$. Hence $3^{2^k} - 2^{2^k} | 3^{n-1} - 2^{n-1}$ (that's true because $a - b | a^r - b^r$ for any natural $a, b$ and $k$).

0

as Qiaochu Yuan pointed out, take a Carmichael number q; by definition, 3q-1 and 2q-1 are both congruent to 1 mod q, so their difference is a multiple of q. Since Carmichael numbers are infinite, you are done.

  • 5
    If q is relatively prime to 3. I don't know if this occurs infinitely often.2010-07-29
0

It is true for all n such that $(n,2)=(n,3)=1$ and for which the order of 2 & 3 modulo n is same.