Find all integers $n\geq 1$ such that $n$ divides $2^{n-1}+3^{n-1}$

elementary-number-theorymodular arithmetic

Some experimentation leads us to suspect that only $n=1$ works. It is easy to see that $n$ must be odd. Write $n=2k+1$, we have $n|2^{2k}+3^{2k}$ and hence for any prime factor $p$ of $n$, $p$ must be of the form $4k+1$ (since it divides a sum of squares/ alternatively we can evoke quadratic reciprocity).

Hence we have $n\equiv 1 \pmod{4}$ and we can write $n=4k'+1$ for some $k'$. And hence $n|2^{4k'}+3^{4k'}$.

I was trying to show that any prime factor $p$ of $n$ must satisfies $p\equiv 1\pmod{8}$ but couldn't make much headway.

Best Answer

You have the right idea. The following is based on the AoPS thread Finding positive integer n such that that n divides 2^(n-1)+3^(n-1), which states the problem comes from "Otis excerpts book by Evan Chan". First, the expression being used is

$$f(n) = 2^{n-1} + 3^{n-1} \tag{1}\label{eq1A}$$

Assuming $n \gt 1$ and $n \mid f(n)$, then as you have already concluded, all primes $p$ which divide $2^{n-1}+3^{n-1}$ must be $\equiv 1 \pmod 4$, so $n$ is the form $n = 4k_2 + 1$. Thus, we have

$$f(4k_2 + 1) = 2^{4k_2} + 3^{4k_2} \tag{2}\label{eq2A}$$

For any prime $p$ where $p \mid f(4k_2 + 1)$, using $s \equiv 3^{-1}\pmod{p}$, we get that

$$2^{4k_2} \equiv -3^{4k_2} \pmod{p} \;\to\; (2s)^{4k_2} \equiv -1 \pmod{p} \;\to\; (2s)^{8k_2} \equiv 1 \pmod{p} \tag{3}\label{eq3A}$$

Next, let

$$m = \operatorname{ord}_{p}(2s) \tag{4}\label{eq4A}$$

where $\operatorname{ord}_{p}$ is the multiplicative order modulo $p$. Thus, $m \mid 8k_2$. Using the $p$-adic valuation, if $\nu_2(m) \le 2$, then from \eqref{eq3A} we get

$$m \mid 4k_2 \;\to\; (2s)^{4k_2} \equiv 1 \pmod{p} \;\to\; -1 \equiv 1 \pmod{p} \tag{5}\label{eq5A}$$

which is not possible since $p$ must be an odd prime. Thus, $\nu_2(m) \ge 3$, so $8 \mid m$. Since $m \mid p - 1$, this means $8 \mid p - 1 \;\to\; p = 8q + 1$. Since this is true for all primes $p$ which divide $f(4k_2 + 1)$, this means it must also be true for all primes $p$ which divide $n$. Thus, $n = 8k_3 + 1$.

This can be repeated inductively to get that, for all integers $j \ge 2$, we have $2^{j+1}$ dividing $p - 1$ for all primes $p$ which divide $f(2^{j}k_{j}+1)$, so $n = 2^{j+1}k_{j+1} + 1$. This is clearly impossible, except for $n = 1$, so it means there can't be any integer $n \gt 1$ where $n \mid f(n)$ in \eqref{eq1A}.


Note that, as lulu's comment suggests, this result remains true with the $3$ in \eqref{eq1A} being replaced by any other odd integer, as the only property of $3$ which is used above is that it's odd (so $n$ must be odd). Similarly, the $2$ in \eqref{eq1A} can be replaced by any even integer, just as long as it's coprime to the odd integer in the second term.