Prove that there are infinitely many composite numbers $n$ so that $n$ divides $3^{n-1}-2^{n-1}$. I proved $n=p^t$, where $p$ is a prime number and $t>1$, never satesfies the condition above.
-
2$\begingroup$ Your claim about $p^t$ is not true. Try $n = 23^2$. $\endgroup$ – Robert Israel May 19 '15 at 23:16
-
1$\begingroup$ The sequence is oeis.org/A073631. No proof of infiniteness there, though, $\endgroup$ – Robert Israel May 19 '15 at 23:31
-
2$\begingroup$ AoPS. $\endgroup$ – user26486 May 19 '15 at 23:36
All Carmichael numbers not divisible by $3$ satisfy this condition. Alford, Granville Pomerance showed there are infinitely many Carmichael numbers, and their proof can be modified to show there are infinitely many that are congruent to $1 \mod 3$: more generally, Thomas Wright proved there are infinitely many Carmichael numbers $\equiv a \mod M$ for any positive integers $a,M$ with $\gcd(a,M) = 1$.
Let $p$ be a prime $>5$ that is $\equiv 1 \pmod{4}$ and does not divide $3^5-2^5$, then let $$m=\frac{3^{5p}-2^{5p}}{3^5-2^5}.$$ $m$ is an integer since $3^5 \equiv 2^5 \pmod{3^5-2^5}$, so $3^{5p}\equiv 2^{5p}\pmod{3^5-2^5}$, so $3^5-2^5 \mid 3^{5p}-2^{5p}$.
Now $$m-1 = \frac{3^{5p}-2^{5p}}{3^5-2^5}-1 \equiv \frac{3^5-2^5}{3^5-2^5}-1\equiv 0 \pmod{p}$$ by Fermat's little theorem and the fact that $p \nmid 3^5-2^5$. Therefore $p\mid m-1$. Now mod $5$, $3^5-2^5\equiv 1 \pmod{5}$, and $p=4k+1=(5-1)k+1$, so $$3^p-2^p = 3(3^{5-1})^k-2(2^{5-1})^k\equiv 3\cdot 1-2\cdot 1 = 1 \pmod{5}$$ by Fermat's little theorem. Finally $$m-1 = \frac{3^{5p}-2^{5p}}{3^5-2^5}-1 \equiv \frac{3^p-2^p}{1}-1\equiv 1 - 1\equiv 0 \pmod{5}$$ by the line above. Thus $5\mid m-1$ as well. Since $5\ne p$, $5p \mid m-1$. Now $m\mid 3^{5p} - 2^{5p}$ by the definition of $m$, and since $m-1 = 5pk$ for some $k$, we have $$(3^{5p})^k = 3^{m-1} \equiv (2^{5p})^k = 2^{m-1} \pmod{m}.$$
Now we just need to show that $m$ is composite. But in the same way that we showed $3^5-2^5 \mid 3^{5p}-2^{5p}$, we have $3^p-2^p\mid 3^{5p}-2^{5p}$. Now suppose $q$ is a common prime factor of $3^5-2^5$ and $3^p-2^p$, then we have that $q\ne 2,3$ since it divides $3^5-2^5$, and let $n$ be the least integer exponent such that $2^n\equiv 3^n \pmod{q}$, since $2$ and $3$ are invertible modulo $q$, we have that if $2^l\equiv 3^l \pmod{q}$, and $l=an+r$ for some $a$ and $0\le r<n$ integers, then since $2^n\equiv 3^n\pmod{q}$, we can cancel the $2^{an}$ and $3^{an}$ to get $2^r\equiv 3^r \pmod{q}$, so $r=0$ since $n$ is the least such positive integer. But then $n\mid 5$ and $n\mid p$, so $n=1$. But then $2\equiv 3 \pmod{q}$, or $q\mid 3-2=1$, which is impossible. Thus $3^5-2^5$ and $3^p-2^p$ are relatively prime, so $3^p-2^p \mid m$.
Now we just need to show $3^p -2^p \ne m$. However $(3^5-2^5)(3^p-2^p)<3^{5+p}+2^{5+p}$. Therefore if we show that for $p$ large enough, $$3^{5p} \overset{?}{>} 2\cdot 2^{5p}+3^{p+5} > 2^{5p}+3^{p+5}+2^{p+5} > 2^p + (3^5-2^5)(3^p-2^p),$$ we will be done.
This inequality is true if and only if $$1 > 2\left(\frac{2}{3}\right)^{5p}+3^{5-4p}.$$ However, the right hand side of the inequality is a decreasing function of $p$, so if it is true for any value of $p$, it will be true for all larger values of $p$. Wolfram Alpha can check this for $p=2$. Thus $m$ is composite for $p>5$ as we required at the beginning. There are infinitely many such $m$ since there are infinitely many $p \equiv 1 \pmod{4}$.
Adapted from here https://primes.utm.edu/notes/proofs/a_pseudoprimes.html
Alternatively if you can show that $3^p-2^p$ is composite infinitely often, the argument becomes much simpler.