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$
-
3I would like to know what is the origin of this problem. (If it is from a textbook, it might be useful to know what you are supposed to know at this stage. E.g. whether a proof using only basic divisibility properties is expected.) – 2012-07-01
-
0What have you tried? I would first try using induction, and a binomial expansion. – 2012-07-01
-
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$.