Show that $6m \mid (2m+3)^n + 1$ if and only if $4m \mid 3^n + 1$ 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$$
 A: $\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$.
