Sa, lu dapet pa di disana ??

A feeble start. Clearly we need $a \equiv b \pmod{2}$. Now, if both are even, so $2 \mid a$, then since we need $2^n \mid a^k + b$, we have $2^n < a^k$, so $n < k\log_2 a$, thus $k > n/\log_2 a$. Therefore, for large $n$'s, $b$ will need be divisible by large powers of $2$, absurd. So a necessary condition for $(a;b)$ to be interesting is that $a,b$ be odd.

Denote generally by $v(n)$ the largest integer satisfying $2^{v(n)} | n$. First, note that $a$ and $b$ must be of the same parity, as otherwise $a^{k}+b$ is odd. Assume both of $a,b$ are even and $v(a)=t, v(b)=m$. Take $n$ such that $a^{m+1}+b<2^{n}$. (It easily leads that $n>m$) Than, if $2^{n}|a^{k}+b$, $k>m$ and $a^{k}$ is divisible by $2^{m+1}$. So, $a^{k}+b$ is divisible by $2^{m}$ and not by $2^{m+1}$, but $n>m$ , which is contradiction. Hence, $a,b$ are both odd. Clearly, $a>1$. (Otherwise the left hand side will be bounded, which is impossible). Let $A=v(a^{2}-1)$. We will prove that if there exist some $k$ such that $2^{A}| a^{k}+b$, than $(a,b)$ is an "interesting" pair. Let's assume there is such $k$. Starting from $A$, any integer is of type $v(a^{2^{n}}-1)$, because $v(a^{2^{n}}-1)+1=v(a^{2^{n+1}}-1)$. (Easy to prove). So, $v(a^{2^{n}}-1)=n+2$, if $n\geq{A}$. Use induction on $n$ to prove that $(a,b)$ is interesting. As it's true for $n=A$, it's obviously true for any smaller $n$. Assume it holds for some $n$ and assume $2^{n}|a^{k}+b$ for some $k$. If $2^{n+1}|a^{k}+b$, it's proved for $(n+1)$. Otherwise, $a^{k}+b=2^{n}t$ for an odd $t$. Consider the number $a^{k+2^{n-2}}+b$: $a^{k+2^{n-2}}+b=(a^{k}+b)+a^{k}(a^{2^{n-2}}-1)$. In the last sum, both summands are divisible by $2^{n}$ and not by $2^{n+1}$. So their sum is divisible by $2^{n+1}$, which completes our induction. Hence, the necessary and sufficient condition for $(a,b)$ is that $a>1$, both of them are odd and there exist such $k$ that $a^{k}+b$ is divisible by $2^{v(a^{2}-1)}$. But the last one imply that either $b+1$ is divisible by $2^{v(a^{2}-1)}$ or $a+b$ is divisible by $2^{v(a^{2}-1)}$. Finally, the answer: All the interesting pairs are of the following type: $(a,b)$ such that $a>1$, both of them are odd and either $2^{v(a^{2}-1)}|(a+b)$ or $2^{v(a^{2}-1)}|(b+1)$. If I haven't done any typo, the answer seems too non-elegant

One benign mistake. For $A = v(a^2-1)$, with odd $a >1$ (thus $A \geq 3$), we have $a^4 - 1 = (a^2 - 1)(a^2 + 1)$, so $v(a^{2^2}-1) = 1 + A$, hence by simple induction $v(a^{2^n}-1) = n - 1 + A$ (and not $n+2$, as stated). Notice the reason to work with $A = v(a^2-1)$, and not $A = v(a-1)$, is that then we cannot establish the value of $v(a^2-1)$. Later on, we need consider $a^{k + 2^{n + 1 - A}} + b$ (and not $a^{k + 2^{n -2}} + b$, as stated). Finally, the characterization of the interesting pairs $(a,b)$ may be made more explicit. They are given by any odd $a > 1$, and then, denoting $A = v(a^2-1)$, by just those $b$ of the form $b = 2^A m - 1$ or $b = 2^A m - a$, for any positive integer $m$ such that $b > 0$.

lasha wrote: But the last one imply that either $b+1$ is divisible by $2^{v(a^{2}-1)}$ or $a+b$ is divisible by $2^{v(a^{2}-1)}$. This is necessary but no longer sufficient, so the previous paragraph is redundant. We can prove the sufficiency using order, but my proof is too complicated.

For any positive integer $n$, let $v(n)$ be the largest integer such that $2^{v(n)}|n$. Lemma: If $b\equiv1\pmod{2^{v(a-1)}}$, then there exists $k\in\mathbb{N}$ such that $a^k\equiv b\pmod{2^n}$ for any $n\in\mathbb{N}$. Proof: Let $v(a-1)=p$, $a=2^pl+1$ where $l$ is odd, and $b=2^pm+1$. For $n\le p$, the statement is obvious (just take $k=1$), suppose $n>p$. Note that $a^{2^{n-p}}-1=\sum_{i=1}^{2^{n-p}}(2^pl)^i{2^{n-p}\choose i}=\sum_{i=1}^{2^{n-p}}(2^pl)^i\frac{2^{n-p}}{2^{n-p}-i}{2^{n-p}-1\choose i}$. Note that $v((2^pl)^i\frac{2^{n-p}}{2^{n-p}-i}{2^{n-p}-1\choose i})\ge pi+n-p-v(i)>n$. So $a^{2^{n-p}}\equiv1\pmod{2^n}$. If $a,a^2,\ldots,a^{2^{n-p}}$ have distinct values in modulo $2^n$, then they take all values of the form $2^pm+1$, so $a^k\equiv b\pmod{2^n}$ for some $k$. Otherwise, the order of $a$ modulo $2^n$ is less then $2^{n-p}$, thus we must have $a^{2^{n-p-1}}\equiv1\pmod{2^n}$. But we have $a^{2^{n-p-1}}-1=\sum_{i=1}^{2^{n-p-1}}(2^pl)^i{2^{n-p-1}\choose i}$. For $i\ge 2$, we have $v((2^pl)^i{2^{n-p-1}\choose i})=pi+n-p-1-v(i)\ge n$, and for $i=1$, we have $v((2^pl)^i{2^{n-p-1}\choose i})=v(2^pl2^{n-p-1})=n-1$. So $2^n\not|a^{2^{n-p-1}}-1$, a contradiction. Our lemma is proved. Since $a^k+b$ is even, then $a$ and $b$ have the same parity. Suppose they are both even. For $n>v(b)$, we have $a^k\equiv-b\pmod{2^n}$. So we must have $kv(a)=v(b)$, or $k=\frac{v(a)}{v(b)}$. Thus $a^{\frac{v(a)}{v(b)}}+b$ is divisible by $2^n$ for all $n>v(b)$, which is impossible. Therefore $a$ and $b$ are both odd. For $n=v(a^2-1)$, we have $a^k\equiv-b\pmod{2^n}$. Note that either $a^2-1|a^k-1$ or $a^2-1|a^k-a$. Thus $-b-1$ or $-b-a$ is divisible by $2^{v(a^2-1)}$, equivalently, $2^{v(a^2-1)}$ divides $b+1$ or $a+b$. (i) $a\equiv1\pmod4$ Let $a=2^k\cdot l+1$ where $k\ge2$ and $l$ is odd. Then $a^2-1=4^kl^2+2^{k+1}l$, so $v(a^2-1)=k+1$. So $b=2^{k+1}m-1$ or $b=2^{k+1}m-2^kl-1=2^k(2m-l)-1=2^kp-1$. Either way, we have $b=2^kq-1$ for some positive integer $q$. From our lemma, we know that there exists $x\in\mathbb{N}$ such that $a^x\equiv-b\pmod{2^n}$, so $(2^k\cdot l+1,2^kq-1)$ is an interesting pair for any $k\ge2$ and odd $l$. (ii) $a\equiv-1\pmod4$ Let $a=2^k\cdot l-1$ where $k\ge2$ and $l$ is odd. Then $a^2-1=4^kl^2-2^{k+1}l$, so $v(a^2-1)=k+1$. Then $b=2^{k+1}m-1$ or $b=2^{k+1}m-2^kl+1=2^kq+1$ where $q$ is odd. (ii.i) $b=2^{k+1}m-1$ Note that $v(a^2-1)=v(4^kl^2-2^{k+1}l)=k+1$. Since $-b\equiv1\pmod{2^{k+1}}$, then it follows from our lemma that there exists $x$ such that $(a^2)^x\equiv-b\pmod{2^n}$. So $(2^k\cdot l-1,2^{k+1}m-1)$ is interesting for $k\ge2$ and odd $l$. (ii.ii) $b=2^kq+1$ Consider a sufficiently large $n$. It is easy to see that the inverse of $a$ modulo $2^n$ is of the form $a^*\equiv 2^kr-1$ for odd $r$. Since $-ba^*\equiv1\pmod{2^{k+1}}$, from our lemma we know that there exists $x$ such that $(a^2)^x\equiv-ba^*\pmod{2^n}$, which gives $a^{2x+1}\equiv-b\pmod{2^n}$. Therefore $(2^kl-1,2^kq+1)$ is interesting for $k\ge2$ and odd $l,q$.

We can easely see that a+b is even. let v(n) denotes exponent of 2 in n. If a and b are even ,then for sufficiently large k we must have v(b)<v(2^(k)*a)thus we have that the set of exponents of t(k)=a^k+b is finite ,contradiction. So we have that a and b are odd integers . Let v(t(m))=s,s is natural . So t(k)= ( a^k+b) is div. by 2^s and not by 2^(s+1) Let r(a,s) denotes the smallest natural number such that a^r=1(mod 2^s). Let M(s) be the set of positive integers such that if p is in M ,then a^p+b is div. by 2^s We can easely conclude that M(s)={z=k+qr/ q is in {Z} , and z>=0},and that M(s+1) is a subset of M(s). If we assume that a^r=1(mod 2^(s+1))=>M(s)=M(s+1),but this is impossible ,such that k is in M(s) ,but not in M(s+1).So we must have that (a^r-1) is not div. by 2^(s+1). So we have to solve the following problem: Problem:Find all pairs of odd positive integers (a,b) such that ,if {T} is the set of exponents of 2 in all t(k)'s,and p is in {T},then (a^(r(a,p))-1) is not div. by 2^(p+1). Let prove the following lemma: Lemma: If (a^(r(a,n))-1) is not divisible by 2^(n+1),then (a^(r(a,n+1))-1) is not div. by 2^(n+2),where n>=2. Proof: Such that (a^(r(a,n+1))-1) is div by 2^n so we get that r(a,n+1) is div by r(a,n),by the condition we have that r(a,n+1)>r(a,n)=> r(a,n+1)=qr(a,n)(q>=2). Let us take q=2,we can easely see that v(a^(r(a,n+1))-1)=n+1,which finishes the proof. Let call the set {G} good if n is in G ,then(a^(r(a,n))-1) is not divisible by 2^(n+1) .By the lemma we have that G={m,m+1,...}.And thus the problem is following: Problem:Find all pairs of odd positive integers (a,b) such that {T}is a subset of {G},where {G} depends on m, and m depends on a . Solution:Consider 2 cases: 1) a-1=(2^m)*k,k is odd ,m>=2 . 2)a+1=(2^m)*k,k is odd ,m>=2. 1)SOl.In the 1-st case,if we assume that there is an element h of {T} with h<m ,then we must have r(a,h)=1,but (a-1) is also divisible by 2^m, so by 2^(h+1),contradiction .Thus we have that G={m,m+1,...} and {T} is a subset of {G}. We have that t(k)=a^k+b=(a^k-1)+(b+1) ,and such that (a^k-1) is div. by (a-1) ,so by 2^m,we get that v(b+1)>=m.And this pairs satisfy to conditions of original problem ,as we shown above,in the beginning of proof and by lemma. So we get that (a,b)=((2^m)*k+1 ,(2^n)*s-1,where n>=m>=2 ,and k,s are odd).(A). 2)SOl. In the second case we can see , like in 1-st case,that if h is in {T} then h=1,or h>=(m+1) ,such that v(a^(2)-1)=m+1,and r(a,1)=1. If k is odd,then t(k)=(a^(k)+1)+(b-1) with v(a^(k)+1)=m,by Hensel's lemma,thus v(b-1)=m,which clearly satisfies to all conditions. If k is even ,we get that v(b-1)>=m ,is not stronger ,then the first. Thus we get that in this case all pairs of such integers are (a,b)=((2^m)*k-1,(2^m)*s+1,where m>=2 ,k and s are odd.)(B) If b=4k+3 ,then v(b+1)>=m ,thus we get another solution: (a,b)=(2^m*k-1, 2^n*s -1 ,n>=m>=2 ,k,s are odd) Thus all the solutions are: A=(2^m*k+1,2^n*s-1,n>=m>=2,k and s are odd.) B=(2^m*k-1,2^m*s+1 ,k and s are odd.) C=(2^m*k-1,2^n*s-1, n>=m+1>=3, k and s are odd.)

It is easy to see that $a,b$ have to be odd Let $exp_2(k)$ denote the largest power of $2$ in $k$ Suppose $(a,b)$ is an interesting pair Let $\alpha=exp_2(a^2-1)$. There exists $\alpha_0$ such that $2^{\alpha}|a^{\alpha_0}+b$ If $\alpha_0$ were even, $2^{\alpha}|a^{\alpha_0}+b=(a^{\alpha_0}-1)+(b+1)\Rightarrow exp_2(b+1)\ge \alpha$ If $\alpha_0$ were odd, $2^{\alpha}|a^{\alpha_0}+b=(a^{\alpha_0}-1)+(b+1)=(a^{\alpha_0}+1)+(b-1)\Rightarrow exp_2(b+1)=exp_2(a-1)$ and $exp_2(b-1)=exp_2(a+1)\Rightarrow exp_2(a+b)\ge\alpha$ since if $\alpha_0$ is odd then $exp_2(a^{\alpha_0}-1)=exp_2(a-1)$ and $exp_2(a^{\alpha_0}+1)=exp_2(a+1)$ Now we prove sufficiency If $exp_2(b+1)\ge \alpha$ then $2^{\alpha}|(a^2-1)+(b+1)$ If $exp_2(a+b)\ge \alpha$ then $2^{\alpha}|a^1+b$ In either case $\exists t, t_0$ s.t. $t\ge \alpha$ and $2^t||a^{t_0}+b$ If $t_0'$ is a positive integer such that $exp_2(t_0'-t_0) = t-\alpha+1$ then we see that $a^{t_0'}+b=a^{t_0}(a^{t_0'-t_0}-1)+(a^{t_0}+b)$ is divisible by $2^{t+1}$ since it is the sum of two numbers fully divisible by $2^t$ Hence the answer all odd pairs $(a,b)$ s.t. $min\{exp_2(b+1),exp_2(a+b)\}\ge exp_2(a^2-1)$

Straight from by blog. $a \not= 1$ and $a \equiv b \equiv 1 \pmod{2}$, and $b \equiv -1 \text{ or } -a \pmod{2^{v_2(a^2-1)}}$ Claim 1. $a \equiv b \equiv 1 \pmod{2}$ Trivial. Clearly $a \equiv b \pmod{2}$. If $a, b$ are both even, let $a=2^ua'$, $b=2^vb'$. Of course, $a', b'$ are odd numbers. Now $a^k+b=2^{uk}a'^k + 2^vb'$. If $uk \not= v$, we have $v_2(a^k+b) = \text{min}(uk,v) \le v$. If $uk=v$, then $k$ is just a fixed number, so there exists $n$ such that $2^n > a^k+b$. Contradiction. Claim 2. $a \not= 1$. Trivial. $a^k+b=b+1$, so there exists $n$ such that $2^n > b+1$. Claim 3. If $a \not= 1$, $a<2^n$, and $a$ is odd, then $ord_a 2^n = 2^{n+1-v_2(a^2-1)}$. Clearly $ord_a 2^n$ is in a form of $2^k$. Now we just need $v_2(a^{2^k}-1) \ge n$. Clearly $k \not= 0$ since $a \not= 1$. LTE gives us $v_2(a^{2^k}-1) = v_2(a-1)+v_2(a+1)+v_2(2^k)-1=v_2(a^2-1)+k-1 \ge n$. Therefore, the minimum $k$ is $n+1-v_2(a^2-1)$. We are ready to solve the problem. Here we assume $a \not= 1$ by Claim 2. For any $n$, we must have $-b$ in $X= \{ a^1, a^2, \cdots a^{2^{n+1-v_2(a^2-1)}} \}$ in modulo $2^n$. Now note that $|X|=2^{n+1-v_2(a^2-1)}$. Also, note that every element in $X$ satisfies $x \equiv 1 \text{ or } a \pmod{2^{v_2(a^2-1)}}$. We note that the size of the set $Y=\{ u| 1 \le u \le 2^n, u \equiv 1 \text{ or } a \pmod{2^{v_2(a^2-1)}}\}$ is $|X|=2^{n+1-v_2(a^2-1)}$ Therefore, a number is in $X$ if and only if it is $1$ or $a$ in mod $2^{v_2(a^2-1)}$. This forces us, to have $b \equiv -1 \text{ or } -a \pmod{2^{v_2(a^2-1)}}$. This also shows that it is enough to have $b \equiv -1 \text{ or } -a \pmod{2^{v_2(a^2-1)}}$. We are done!