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$
Show that $6m \mid (2m+3)^n + 1$ if and only if $4m \mid 3^n + 1$
-
0Its from Pre-Indonesian TSTST 2010,but your proof is understandable . – 2012-07-01
1 Answers
$\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$.