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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.