Let $w(x)$ be largest odd divisor of $x$. Let $a,b$ be natural numbers such that $(a,b)=1$ and $a+w(b+1)$ and $b+w(a+1)$ are powers of two. Prove that $a+1$ and $b+1$ are powers of two.
Problem
Source: Serbia additional TST 2016
Tags: number theory
Wolowizard
05.04.2016 17:33
My solution:
It's easy to see that $a,b$ are odd.
Let $a+1=2^xa_1$,$b+1=2^yb_1$.
Conditions reduce to:
$2^xa_1+b_1-1=2^A$
$2^yb_1+a_1-1=2^B$
which is equivalent to
Mathemator_13
13.09.2016 23:55
Wolowizard wrote: It's easy to see that $a,b$ are odd. Let $a+1=2^xa_1$,$b+1=2^yb_1$. Conditions reduce to: $2^xa_1+b_1-1=2^A$ $2^yb_1+a_1-1=2^B$ which is equivalent to OK, then what?
aopser123
28.12.2016 01:48
Any solution?
tree3
28.12.2016 02:23
I solved this with substitutions and modular arithmetic. I also set up a p-adic inequality which will yield the desired result. Tell me if you want the full solution.
suli
28.12.2016 04:19
Tough one!
Let $a + 1 = 2^m p$, $b = 1 = 2^n q$, for some odd $p, q$. It is clear $a$ and $b$ are odd, hence $m, n \ge 1$.
We have $2^m p - 1 + q = 2^A$ and $2^n q + p = 2^B + 1$ for some $A, B \ge 0$.
Suppose $p, q \ge 3$. Then we find $2^A = 2^m p + q - 1 \ge 2^m \cdot 3$, so $A \ge m+2$. Similarly $B \ge n+2$. Also $p = 2^B + 1 - 2^n q$, so
$$2^m (2^B + 1 - 2^n q) = 2^A + 1 - q.$$Thus $2^m \mid q-1$, so let $q - 1 = 2^m r$, for some integer $r$. Then
$$2^B + 1 - 2^n (2^m r + 1) = 2^{A-m} - r,$$so
$$r = \frac{2^B + 1 - 2^n - 2^{A-m}}{2^{n+m} - 1}.$$Let $S = n+m, B' = B \pmod S, A' = (A-m) \pmod S.$ Then $2^S \equiv 1 \pmod {2^S - 1},$ so
$$2^S - 1 \mid 2^{B'} + 1 - 2^n - 2^{A'} = K.$$However, notice that $B' \le S-1$, so
$$K < 2^{S-1} + 1 - 1 - 1 < 2^S,$$$$K > 1 + 1 - 2^n - 2^{S-1} > -2^S.$$Thus, $K = 0$, or
$$2^{B'} + 1 = 2^n + 2^{A'}.$$Then clearly $\{B', 0\} = \{n, A'\}$. Because $n \ge 1$, we must have $B' = n$ and $A' = 0$. As a result, we have
$$m + n \mid A - m$$$$m + n \mid B - n.$$Let $A - m = tS, B - n = uS$.
Suppose $u > t$. Then since $t \ge 1$, we have $u \ge 2$. The condition $p > 0$ becomes (after substituting in known expressions):
$$2^S (2^B + 1 - 2^n - 2^{A-m}) < (2^S - 1)(2^B + 1)$$$$2^B + 1 < 2^S (2^n + 2^{A-m}) = 2^{S+n} + 2^{A-n}$$But this is clearly false since $B - n \ge A - m + (m+n) \rightarrow B \ge A + 2n > A + n$ and $B > S+n$. Thus $u \le t$. But similar reasoning (and $q > 0$) gives $u \ge t$, so in fact $u = t$.
Now it is easy to compute
$$a = 2^m (2^B + 1 - 2^n - 2^S r) - 1$$$$b = 2^n (1 + 2^m r) - 1,$$and a simple computation gives
$$a + 2^m b = 2^{(u+1) C} - 1$$$$b = 2^n \cdot \frac{2^{(u+1)C} - 1}{2^C - 1} - \frac{2^{(t+1)C} - 1}{2^C - 1}.$$Because $u = t$, both terms have $\frac{2^{(u+1)C} - 1}{2^C - 1}$ as a common factor, so $\gcd(a, b) > 1$, contradiction. Thus in fact one of $p, q$ is one. WLOG $p = 1$, then $2^n q = 2^B$, so $q = 1$ as well.
aopser123
28.12.2016 06:16
tree3 wrote: I solved this with substitutions and modular arithmetic. I also set up a p-adic inequality which will yield the desired result. Tell me if you want the full solution. I would like to see a full solution, if it differ with suli's(which should be the case, since you've mentioned inequality with p-adic valuations...), if it is not a problem... Thanks in advance!
Wave-Particle
30.12.2016 06:46
tree3 wrote: I solved this with substitutions and modular arithmetic. I also set up a p-adic inequality which will yield the desired result. Tell me if you want the full solution. I am also interested in such a solution. Could you please explain?
Kaladesh
31.12.2016 19:59
tree3 wrote: I solved this with substitutions and modular arithmetic. I also set up a p-adic inequality which will yield the desired result. Tell me if you want the full solution. I would also like to see your solution!
wu2481632
31.12.2016 21:10
tree3 wrote: I solved this with substitutions and modular arithmetic. I also set up a p-adic inequality which will yield the desired result. Tell me if you want the full solution. What's your solution?
Wave-Particle
31.12.2016 21:19
wu2481632 wrote: tree3 wrote: I solved this with substitutions and modular arithmetic. I also set up a p-adic inequality which will yield the desired result. Tell me if you want the full solution. What's your solution? guys guys tree3 promised me via PM he would post it today i hope he doesn't accidentally delete his solution again like yesterday edit: i just had a brief conversation with him. To those interested in a solution...it'll be up by the hour !
rmrf
31.12.2016 21:37
aiyer12 wrote: guys guys tree3 promised me via PM he would post it today i hope he doesn't accidentally delete his solution again like yesterday edit: i just had a brief conversation with him. To those interested in a solution...it'll be up by the hour ! Hi, we don't care about your conversation with tree3
tree3
31.12.2016 21:39
What is that supposed to mean? Also typing it up. I got distracted. I deleted half of sol yesterday.
Kaladesh
31.12.2016 22:13
tree3 wrote: What is that supposed to mean? Also typing it up. I got distracted. I deleted half of sol yesterday. It means that we care about the content of the solution, not the content of the conversation On that note, I am very interested in this solution which takes more than 34 minutes to type up! Must be a long and strong one...how long did it take you to find it?
tree3
31.12.2016 22:15
Let $a+1=2^ck$ and let $b+1=2^dl$, where $l, k$ are odd. The equations can be rewritten as $2^ck+l=2^m+1$, $2^bl=2^n+1$. Subtracting the two equations yields $l-k+2^ck-2^dl=2^m-2^n$. Then take $\pmod {2^{\min(c,d)}}$. WLOG, assume $c\le d$. Since$ k$ and$ l $ are positive integers, they are $\ge1$, so $c\le m$ and $d\le n$. Then $l- k \equiv 0 \mod 2^c$ or that $v_2(l-k)\ge c$. Let then $l=k+s \cdot 2^v$. It can be seen that the parity of $s$ is even iff $c=d$. Otherwise $s$ must be odd. Then plug the new form for $l$ into the first equation. This yields $2^ck+k+s2^c=2^m+1$. Since $c\le m$, once again $k=t\cdot 2^u+1$ for some $u,t$. The parity of $t$ is even iff $c=m$. Plugging in the new form for $k$ yields $2^c(2^ct+t+s)=2^m$. Dividing out by $2^c$, yields that $t+s$ must be even or otherwise $m-c=0$. Then note that the parity of $t$ is the same as the parity of $s$ by the parity conditions. This means $c=m$. This then implies that $k=l=1$, which is proved as desired.
tree3
31.12.2016 22:18
Any clarity suggestions?
hinna
31.12.2016 22:20
tree3 wrote: Let $a+1=2^ck$ and let $b=2^dl$, where $l, d$ are odd. The equations can be rewritten as $2^ck+l=2^m+1$, $2^bl=2^n+1$. Subtracting the two equations yields $l-k+2^ck-2^dl=2^m-2^n$. Then take $\pmod {2^{\min(c,d)}}$. WLOG, assume $c\le d$. Since$ k$ and$ l $ are positive integers, they are $\ge1$, so $c\le m$ and $d\le n$. Then $l-k=0$ mod $2^c$ or that $v_2(l-k)\ge c$. Let then $l=k+s \cdot 2^v$. It can be seen that the parity of $s$ is even iff $c=d$. Otherwise $s$ must be odd. Then plug the new form for $l$ into the first equation. This yields $2^ck+k+s2^c=2^m+1$. Since $c\le m$, once again $k=t\cdot 2^u+1$ for some $u,t$. The parity of $t$ is even iff $c=m$. Plugging in the new form for $k$ yields $2^c(2^ct+t+s)=2^m$. Dividing out by $2^c$, yields that $t+s$ must be even or otherwise $m-c=0$. Then note that the parity of $t$ is the same as the parity of $s$ by the parity conditions. This means $c=m$. This then implies that $k$ and $l$, which is proved as desired. Since you keep editing it, here is the latexed
Kaladesh
31.12.2016 22:20
Yes. Use \ge for greater than or equal. Use paragraphs. Make sure all equations are in LaTeX. Check your work, as in the first sentence you say $b = 2^dl$, not $b+1 = 2^dl$. EDIT: you fixed this
tree3
31.12.2016 22:21
I skipped a lot of steps, but it should still make sense.
tree3
31.12.2016 22:29
Someone pls fix red part.
FE_Eliminator
31.12.2016 22:31
l- k \equiv 0 \mod 2^c => $l- k \equiv 0 \mod 2^c$ (Still looking for the projective proof)
ywq233
18.05.2019 20:53
(The solution is still incorrect, I'll try to fix it tomorrow) Let $a+1=m\cdot2^x............(1)\;\;\;\;\;\;\;\;b+1=n\cdot2^y............(2)\;\;\;\;\;\;\;\;a+n=2^c............(3)\;\;\;\;\;\;\;\;b+m=2^d............(4)$. We proceed by induction on $c+d$.Assume the conclusion($m=n=1$) is true for all $c'+d'<c+d$.The base of induction is trivial. Subtract $(1),(3)$ and $(2),(4)$ respectively,we get:$$n-1=2^c-m\cdot2^x............(5)\;\;\;\;\;\;\;\;m-1=2^d-n\cdot2^y............(6)$$Assume $m,n\ne1$.Easy to know that $c>x$ and $d>y$.So $2^x\mid n-1$ and $2^y\mid m-1$. Let $n=k\cdot2^x+1............(7)\;\;\;\;\;\;\;\;m=l\cdot2^y+1............(8)$.Plug $(7),(8)$ into $(5),(6)$:$$k+l\cdot2^y+1=2^{c-x}............(9)\;\;\;\;\;\;\;\;l+k\cdot2^x+1=2^{d-y}........(10)$$Similarly $2^y\mid k+1,2^x\mid l+1$. Let $k+1=u\cdot2^y............(11)\;\;\;\;\;\;\;\;l+1=v\cdot2^x............(12)$. Plug $(11),(12)$ into $(9),(10)$,we get:$$u+l=2^{c-x-y}............(13)\;\;\;\;\;\;\;\;k+v=2^{d-x-y}............(14)$$Compare $(1)(12),(2)(11),(3)(13),(4)(14)$ and use the inductive hypothesis to get $u=v=1$. Plug back into $(13),(14),(11),(12),(7),(8),(1),(2)$ respectively to get:$$c=2x+y,d=2y+x,k=2^y-1,l=2^x-1,n=2^{x+y}-2^x+1,m=2^{x+y}-2^y+1,a=2^{2x+y}-2^{x+y}+2^x-1,b=2^{x+2y}-2^{x+y}+2^y-1$$But $2^{x+y}+1$ divides both $a$ and $b$,contradicts $(a,b)=1$ ! So $m=n=1$.\square