# Nonprimes with $3^{n-1} \equiv 2^{n-1} \pmod n$

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

-
I believe this follows from the existence of infinitely many Carmichael numbers, but maybe there is a more elementary proof. – Qiaochu Yuan Jul 29 '10 at 6:54
I was just writing to refer to pseudoprimes :-) – mau Jul 29 '10 at 8:38

## 3 Answers

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

-

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.

-
If q is relatively prime to 3. I don't know if this occurs infinitely often. – Qiaochu Yuan Jul 29 '10 at 17:18

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.

-