Given a positive integer $k$ and an integer $a\equiv 3 \pmod{8}$, show that $a^m+a+2$ is divisible by $2^k$ for some positive integer $m$.
Problem
Source: Romania TST 2016 Day 3 P2
Tags: number theory
Mathuzb
01.11.2017 12:22
Any solution??
jishu2003
01.11.2017 12:39
A possible solution
$a^m+a+2\equiv3^m+3+2\equiv$
$3^m-3\equiv3\cdot(3^{m-1}-1)$
$\equiv3\cdot(3-1)(m)\equiv$
$3\cdot2\cdot(m) \pmod{8}$
(for some integer m)
Therefore $a^m+a+2=8k+6m=2(4k+3m)$
So the given expression is always
a multiple of $2^1$
(NOTE: $a^m-1=
(a-1)(a^{m-1}+a^{m-2}\cdots+1$[
jishu2003
01.11.2017 12:43
And then the result follows....
RagvaloD
01.11.2017 13:02
$a=8x+3$ Lemma: $v_2(a^{2^{k-2}}-1)=k$ Proof: By LTE $v_2(a^{2^{k-2}}-1)=v_2(a^2-1)+v_2(2^{k-3})=v_2(64x^2+48x+8)+k-3=k$ By induction For $k=1,2,3$ we can take $m=1$ Let $2^k|a^m+a+2$ and $2^{k+1}\not |a^m+a+2$ then $a^m+a+2 \equiv 2^k \pmod{2^{k+1}}$ $a^{2^{k-2}}-1 \equiv 2^k \pmod{2^{k+1}}$ $(a^{m+2^{k-2}}+a+2) =(a^m+a+2)+a^m(a^{2^{k-2}}-1) \equiv 2^k+2^k \equiv 0 \pmod {2^{k+1}}$ So $2^{k+1}| a^{m+2^{k-2}}+a+2$