Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$$

share|cite|improve this question
What have you tried? I would first try using induction, and a binomial expansion. – Andrew Jul 1 '12 at 9:19
I 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.) – Martin Sleziak Jul 1 '12 at 13:46
Its from Pre-Indonesian TSTST 2010,but your proof is understandable . – Frank Jul 1 '12 at 20:23
up vote 3 down vote accepted

$\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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.