Is it true that there are infinitely many nonprime integers $n$ such that $3^{n-1} - 2^{n-1}$ is a multiple of $n$?
Nonprimes with $3^{n-1} \equiv 2^{n-1} \pmod n$
4
$\begingroup$
number-theory
-
0I believe this follows from the existence of infinitely many Carmichael numbers, but maybe there is a more elementary proof. – 2010-07-29
-
0I was just writing to refer to pseudoprimes :-) – 2010-07-29
3 Answers
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.
-
5If 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.