Show that $6m \mid (2m+3)^n + 1$ if and only if $4m \mid 3^n + 1$

Question

Let $m$ and $n$ be positive integers. How to prove that $$6m \mid (2m+3)^n + 1$$ if and only if $$4m \mid 3^n + 1$$

Answer 1

$\newcommand{\jaco}[2]{{\left(\frac{#1}{#2}\right)}}$I have tried to solve this - I hope I did not make too many mistakes there. Maybe there is much easier solution than this one.

---

Let us start by a few easy observations.

Since $2m+3 \equiv 3 \pmod m$, we see that $$m\mid (2m+3)^n+1 \Leftrightarrow m\mid 3^n+1. \tag{1}$$

It is obvious that $$3\mid (2m+3)^n+1 \Rightarrow 3\nmid m. \tag{2}$$

Since $3\nmid x$ implies $x^2\equiv 1 \pmod 3$ (Little Fermat's theorem), we get (using this fact for $x=2m+3$) that $$3\mid (2m+3)^n+1 \Rightarrow n\text{ is odd.}\tag{3}$$

Now we get $$3\mid (2m+3)^{n}+1 \Rightarrow m\equiv1\pmod3, \tag{4}$$ since $m\equiv2\pmod3$ $\Rightarrow$ $2m+3\equiv1\pmod3$ $\Rightarrow$ $(2m+3)^n\equiv1\pmod3$ $\Rightarrow$ $(2m+3)^n+1\equiv2\pmod3$.

It is easy to see that $$4\mid 3^n+1 \Leftrightarrow n\text{ is odd}\tag{5}$$ and $$m\mid 3^n+1 \Rightarrow 3\nmid m.\tag{6}$$

For odd $n=2k+1$ we have $3^{2k+1}+1=(3+1)(3^{2k}-3^{2k-1}+\dots+3^2-3+1)$, which shows that $$\frac{3^{2k+1}+1}4\equiv 1 \pmod 2.$$ Hence $$4m\mid 3^n+1 \Rightarrow m\text{ is odd.}\tag{7}$$

---

Now a few more facts with a little less elementary proof. We will use Legendre symbol and quadratic reciprocity.

We first show: $$4m\mid 3^n+1 \Rightarrow m\equiv1 \pmod 3.\tag{8}$$ We know that $n$ is odd, let $n=2k+1$. It suffices to show that each odd prime factor $p$ of $3^{2k+1}+1$ fulfills $p\equiv1\pmod 3$.

Suppose that $p\mid 3^{2k+1}+1$ and, consequently $p\mid 3^{2(k+1)}+3$. Therefore $-3$ is a quadratic residue modulo $p$ and $\jaco{-3}p=1$. We get: $$\jaco{-3}p=\jaco{-1}p\jaco3p$$ $$1=(-1)^{\frac{p-1}2}(-1)^{\frac{p-1}2}\jaco{p}3.$$ Hence $\jaco{p}3=1$, which implies $p\equiv1\pmod{3}.$

---

Now we are ready to show that $6m\mid (2m+3)^n+1$ $\Leftrightarrow$ $4m\mid 3^n+1$.

$\boxed{\Rightarrow}$ If $6m\mid (2m+3)^n+1$ then:

• $\gcd(m,4)=1$ by (7)
• $n$ is odd by (3)
• $4\mid 3^n+1$ by (5)
• $m\mid 3^n+1$ by (1)

Together we have $4m\mid 3^n+1$.

$\boxed{\Leftarrow}$ If $4m\mid 3^n+1$ then:

• $n$ is odd by (5)
• $\gcd(m,6)=1$ by (6), (7)
• $m\mid (2m+3)^n+1$ by (1)
• $2\mid (2m+3)^n+1$ since $2m+3$ is odd
• $3\mid (2m+3)^n+1$ since $m\equiv1 \pmod 3$ by (8), which yields $2m+3\equiv 2\pmod 3$ and $(2m+3)^n\equiv2\pmod3$ (using the fact that $n$ is odd).

Together we have $2\cdot 3 \cdot m \mid (2m+3)^n+1$.