Find $X, Y \in \mathbb{Z}$ such that $2^a X + (2^b - 1) Y = 1$ (coprimality)

Question

I've been wrecking my brain trying to solve this exercise. Is this answer wrong?

$$X= (2^{a})^{b-1}, Y= (-1) (2^b +1) \ [(2^b -1)(2^b +1)]^{a-1}$$

Answer 1

Supposing $a,b>0$.For sure there exists a number $m\in \Bbb{Z}$ such that:

$$mb\geq a\Rightarrow m\geq \frac{a}{b} \Rightarrow m\geq \left \lceil{\frac{a}{b}}\right \rceil=M $$

Notice that if:

$$Y=-\sum_{i=0}^{M} 2^{bi}=\frac{-2^{b(M+1)}+1}{2^b-1}$$

Then the equation becomes:

$$2^a X-2^{b(M+1)}+1=1$$

Clearly this is satisfied by:

$$X=2^{bM+b-a}$$

So our particolar solutions are:

$$X=2^{b\left(\left \lceil{\frac{a}{b}}\right \rceil+1\right)-a} \ , \ Y=\frac{1-2^{b\left(\left \lceil{\frac{a}{b}}\right \rceil+1\right)}}{2^b-1}$$

So the general solutions are:

$$X=2^{b\left(\left \lceil{\frac{a}{b}}\right \rceil+1\right)-a}+(2^b-1)k \ , \ Y=\frac{1-2^{b\left(\left \lceil{\frac{a}{b}}\right \rceil+1\right)}}{2^b-1}-2^ak$$

:)

Answer 2

If $a=b$, then $X=1$, $Y=-1$ is an obvious solution.

If we can find a solution $(X',Y')$ for $(a+1,b)$ then $(X,Y)=(2X',Y')$ is a solution for $(a,b)$.

If we can find a solution $(X',Y')$ for $(a,2b)$ then $(X,Y)=(X',(2^b+1)Y')$ is a solution for $(a,b)$.

These three observation allow us to find a solution for every $(a,b)\in\Bbb N^2$ with $b>0$. Indeed, we can reapeatedly double $b$ until $b\ge a$ and then repeatedly increase $a$ until $a=b$, and from there work our way backwards.

Explicitly, find $k\in\Bbb N_0$ such that $2^kb\ge a$ (to be concrete, $k=\lceil\log_2\frac ab\rceil$). Then take $$ \begin{align}X&=2^{2^kb-a},\\ Y&=-\prod_{j=0}^{k-1}(2^{2^jb}+1)=-(1+2^b+2^{2b}+\ldots +2^{(2^k-1)b})=-\frac{2^{2^kb}-1}{2^b-1}.\end{align}$$

---

In fact, knowing that $x-1$ divides $x^n-1$ for all $n\in\Bbb N$, we can write down directly (i.e., without the three observations above) $$ \begin{align}X&=2^{nb-a},\\ Y&=-\frac{2^{nb}-1}{2^b-1}\end{align}$$ with $n$ picked so to make $nb\ge a$, in other words we can let $n=\lceil\frac ab\rceil$.

Answer 3

If $a$ and $b$ are natural numbers and $b > 0$,

$2^{ab} = ((2^{b} - 1) + 1)^{a}$

$2^{ab} = \sum_{i = 1}^{a} {a \choose i} (2^{b}-1)^{i} + 1$

$2^{a} 2^{a(b-1)} = (2^{b}-1)\sum_{i = 1}^{a} {a \choose i}(2^{b}-1)^{i-1} + 1$

$2^{a}2^{a(b-1)} - (2^{b}-1)\sum_{i = 1}^{a} {a \choose i}(2^{b}-1)^{i-1} = 1$

It is only a special case of the other answers, of course.

Answer 4

@Hagen gave a simple solution from the fact that $\frac{x^n-1}{x-1}$ is integer. $X=2^{nb-a}$ and $Y=-\frac{2^{nb-1}}{2^b-1}$.

In particular for $n=a$, we have $X=2^{ab-a}$ (which is the same as your $X$) and $Y=-\frac{2^{ab-1}}{2^b-1}$(which is clearly not the same as your answer). So, the answer that you got was wrong.

In general given two integers $a,b$ with $\gcd(m,n)=d$. You can find algorithmically $X$, $Y$ such that $mX+nY=d$. This is essentially based on the euclidean algorithm. In short, the algorithm is as follows: Say $m>n$, then by diving $m$ by $n$, you can express $m=nq+r$ with $r<n$.

Suppose that we can find $X',Y'$ such that $X'r+Y'n=d$. Then, $X'm+(Y'-qX')n=d$. This means that if we solve the problem for $(r,n)$ we solve the problem for $(m,n)$. The algorithm then comes from repeating this process, reducing the problem of $(m,n)$ to $(r,n)$ until you can't do any more reductions, i.e. until you reach $(d,0)$.