Where, if the answer were even, than $(m+3)^n +1$ would be even, so m must be even That turn the denominator $3m$ into an even integer For the answer to be even, $(m+3)^n+1$must be congruent to 0 modulo 4 And that is impossible

@above hem hem if m is 0 mod 4 and n is an odd integer then your argument is invalid. From $m|(m+3)^n+1$ we see that, after binomial expansion and the euclidean algorithim, $m|3^n+1$. This tells us that $m$ is never a multiple of $3$ Assume $m \equiv 1\pmod{3} \rightarrow m = 3m_1+1$ Then $3|(3m_1+4)^n + 1 \rightarrow 3|4^n+1$ but we have that $4^n+1 \equiv 2 \pmod{3}$ for all $n \in \mathbb{N}$. Thus, this is impossible meaning that $m \equiv 2\pmod{3}$ Now see that if we replace again $3|(3m_1+5)^n +1 \rightarrow (-1)^n + 1 \equiv 0\pmod{3}$ meaning that $n$ is an odd integer. So now we proceed similarly to the above;basically by contradiction Assume that this expression is in fact even. This means that $(m+3)^n+1$ is an even integer meaning that $m$ is even meaning $3m$ is even which makes $(m+3)^n+1 \equiv 0 \pmod{4}$ And here we split it into 2 cases If $n=1$, then $\frac{m+4}{3m}$ has to be an integer meaning that $m|4$. So $m$ can be 1,2,4. Testing out all those values we see that only $m=2$ works and in that case the expression is 1, which is odd. Now if $n>1$ and n is odd, then $1^n \equiv 1 \pmod{4}, 2^n \equiv 0\pmod{4}, -1^n \equiv -1\pmod{4}, 0^n \equiv 0 \pmod{4}$ Clearly we must have that $(m+3)^n \equiv -1 \pmod{4} \rightarrow m+3 \equiv -1 \pmod {4} \rightarrow m \equiv 0\pmod{4}$ This means that $m = 4m_1$ for some integer $m_1$ Now we replace to see that $12m_1|(4m_1+3)^n+1$ This means that $m_1|(4m_1+3)^n+1$ by the euclidean algorithim $m_1|3^n+1$. This means that $m_1 \equiv 1 \pmod{3}$ Now we see that $m_1 \equiv 4m_1 \equiv m \equiv 1\pmod{3}$. But from above we have that $m \equiv 2\pmod{3}$ which is a contradiction. Thus, if the expression is an integer it is never even meaning that it is always odd. EDIT:edited out some useless steps

fanzhuyifan wrote: Where, if the answer were even, than $(m+3)^n +1$ would be even, so m must be even That turn the denominator $3m$ into an even integer For the answer to be even, $(m+3)^n+1$must be congruent to 0 modulo 4 And that is impossible Why is that impossible ?

efang wrote: ....This means that $m_1|(4m_1+3)^n+1$ by the euclidean algorithim $m_1|3^n+1$. This means that $m_1 \equiv 1 \pmod{3}$ You are not right.

It's A 17 in PEN.

IstekOlympiadTeam wrote: efang wrote: ....This means that $m_1|(4m_1+3)^n+1$ by the euclidean algorithim $m_1|3^n+1$. This means that $m_1 \equiv 1 \pmod{3}$ Can you prove your last claim please??

It suffices to show that $\left(2^{k-1}+3\right)^n+1\not\equiv0\pmod{2^k}$ (why?). Indeed, $\left(2^{k-1}+3\right)^n+1\equiv 3n\cdot2^{k-1}+3^n+1$, so it is necessary and sufficient to show that $v_2(3^n+1)=k-1\iff 2\mid n$. This is true by $\pmod{8}$, as long as $k>3$. For the remaining $k\in\{1,2,3\}$, just check cases $\pmod{2}$, $\pmod{4}$, and $\pmod{8}$ to finish $\Box$

If $m = 4(2d+1),\; n = 2p+1$, how to prove $\frac{(m+3)^n+1}{3m}$ is not an integer?

rafayaashary1 wrote: It suffices to show that $\left(2^{k-1}+3\right)^n+1\not\equiv0\pmod{2^k}$ (why?). Indeed, $\left(2^{k-1}+3\right)^n+1\equiv 3n\cdot2^{k-1}+3^n+1$, so it is necessary and sufficient to show that $v_2(3^n+1)=k-1\iff 2\mid n$. This is true by $\pmod{8}$, as long as $k>3$. For the remaining $k\in\{1,2,3\}$, just check cases $\pmod{2}$, $\pmod{4}$, and $\pmod{8}$ to finish $\Box$ For $k=3$ we have $(2^{3-1}+3)^n+1 \equiv 7^n +1 \equiv (-1)^n +1 \equiv 0\pmod{2^3}$ Since $m=4(2b+1)\equiv 2\pmod{3}$ has general solution $m=4(6d-1)$ We need to prove that $\frac{3^{2n+1}+1}{(6d-1)}$ is not an integer. Not easy....

I don't understand why fanzhyifan's solution is wrong.

rafayaashary1 wrote: It suffices to show that $\left(2^{k-1}+3\right)^n+1\not\equiv0\pmod{2^k}$ (why?). Indeed, $\left(2^{k-1}+3\right)^n+1\equiv 3n\cdot2^{k-1}+3^n+1$, so it is necessary and sufficient to show that $v_2(3^n+1)=k-1\iff 2\mid n$. This is true by $\pmod{8}$, as long as $k>3$. For the remaining $k\in\{1,2,3\}$, just check cases $\pmod{2}$, $\pmod{4}$, and $\pmod{8}$ to finish $\Box$ false for $k=3$

Here is an another solution: Checking modulo 3 shows that $n$ is odd and $3|m+1$ so $m$ should have a prime divisor $p \equiv 2 \pmod 3$.We will show that $p=2$. By contradiction,assume that $p>2$.since $p|m$ ,$p|(m+3)^n +1$.we get that: $$(m+3)^n \equiv 3^n \equiv -1 \pmod p \rightarrow 3^{n+1} \equiv -3 \pmod p$$. and since $n+1$ is even,we deduce that $-3$ is a quadratic residue modulo $p$,contracting the fact that $3|p+1$,so $p=2$. Now,assume that $m=2^{2k+1} x$ where $x$ is odd,we split the problem into two cases: 1-$k=0$ then $v_2(3m)=v_2((m+3)^n +1)=1$ and we are done. 2-$k>0$ so $8|m$ but $(m+3)^n \equiv 3^n+1 \equiv 4 \pmod 8$ which is contradiction since $8|3m$.

can somebody explain me why 3^n+1 cant be devided by number which is 2(mod3) @efang and you can?

dato1234567 wrote: can somebody explain me why 3^n+1 cant be devided by number which is 2(mod3) @efang and you can? look. $5 \mid 3^2+1$

Hopefully I didn't fakesolved this!

Another solution using a bit of quadratic residue. Assume that $\frac{(m+3)^n+1}{3m}$ is even, thus m is even. $m|3^n+1$ so $m\equiv 1,2\pmod 3$. If $m\equiv 1\pmod 3$ or n is even then $(m+3)^n+1\equiv 2\pmod3$. Hence, $m\equiv 2\pmod 3$ and n is odd. Because $\frac{(m+3)^n+1}{3m}=2k$ so $(m+3)^n+1=2k.3m$. Because m is also even so $(m+3)^n+1\equiv 0\pmod 4$, but n is odd so $m\equiv 0\pmod 4$. But if $m\equiv 0\pmod 8$ then we have a contradiction as $(m+3)^n+1\equiv 4\pmod 8$ and $3m\equiv 0\pmod 8$. So $m\equiv 4\pmod 8$, let $m=4(2k+1)$. Because $m\neq 4$(as $4\equiv 1\pmod 3$) so $k\geq 1$. Let $p$ be an arbitrary prime factor of $2k+1$. Because $p|m|3^n+1$ and n is odd so $(\frac{-3}{p})=1$. Thus $p\equiv 1\pmod 3$. This is true for every prime factor of $2k+1$. Thus $m\equiv 4.1\equiv 1\pmod 3$. Thus we have a contradiction. Hence, $\frac{(m+3)^n+1}{3m}$ must be odd

Sol: Suppose $A$ is even. Mod 3 gives $n$ odd, $m\equiv 2 (mod 3)$. Now $A$ even gives us $m$ even but $v_2((m+3)^n + 1)) > v_2(3m)$. Suppose $v_2((m+3)^n + 1)=2$ hence $m\equiv 0 (mod 4)$ but again $v_2((m+3)^n + 1)) > v_2(3m)$, so if $m=4x$, $(4x+3)^n+1 \equiv 0 (mod 8)$ and then $x$ odd. $v_2(m)=4$, but by LTE $v_2((m+3)^n + 1)) =v_2(m+4)=2$ and notice that the $v_2$ from denominator and from the numerator are equal so $A$ can't be even. Edit: 100th post

Assume for the sake of contradiction that the conclusion is not true. Then, evidently $m$ must be even. Taking mod 3 of the numerator, $$m^n+1 \equiv 0 \pmod 3$$hence $n$ is odd and $m \equiv -1 \pmod 3$. Now we look at $\nu_2$. If $\nu_2(m) \geq 3$, then $$(m+3)^n + 1 \equiv 3^n + 1 \equiv 4 \pmod 8$$as $n$ is odd, which means $A$ is not an integer. If $\nu_2(m) = 1$, then $m \equiv 2 \pmod 4$, so $(m+3)^n + 1 \equiv 2 \pmod 4$, which means $A$ is odd. If $\nu_2(m) = 2$, then fix a $3k+2$ prime $p \mid m$. Notice that we must have $$3^n + 1 \equiv 0 \pmod m \iff 3^n\equiv -1 \pmod p.$$Now, let $g$ be a generator mod $p$ and set $3 \equiv g^b$. Thus we have $$g^{bn} \equiv -1 \pmod p.$$Now, assume that $p \equiv 1 \pmod 4$. Then $(2k+1) \equiv \frac{p-1}2$ mod $p$, so $ b$ is even and $\left(\frac 3p\right) = 1$. But this is clearly a contradiction as $\left(\frac p3\right) = -1$. The case $p \equiv 3 \pmod 4$ carries out similarly, so we're done.