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
05.04.2016 17:33
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?
28.12.2016 01:48
Any solution?
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.
28.12.2016 04:19
Tough one!
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!
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?
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!
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?
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 !
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
31.12.2016 21:39
What is that supposed to mean? Also typing it up. I got distracted. I deleted half of sol yesterday.
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?
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.
31.12.2016 22:18
Any clarity suggestions?
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
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
31.12.2016 22:21
I skipped a lot of steps, but it should still make sense.
31.12.2016 22:29
Someone pls fix red part.
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)
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