# General solutions for bezout's identity case when integers take exponential form

How do you go about finding the integer solutions for something like that? : $$a^bx + c^dy$$ where $$a,b,c,d$$ are positive integers and $$a$$ is odd and $$c$$ is even

Using bezouts idenity we know that there exists solutions for: $$a^bx + c^dy = gcd(a^b, c^d)$$ and since $$a^b, c^d$$ share no common factors $$a^bx + c^dy =1$$

The problem is, how do you apply Extended Euclidean algorithm on $$a^b, c^d$$ (Obviously it's so easy to if you plug some values in, but I am trying to find a general solution)

I even tried to find one solution just by playing around with the equation but I doubt it works:

$$a^b(\frac {c^d + 1} {a^b}) + c^d(-1) = 1$$

Since $$c$$ is even then $$c^d$$ is even then $$(c^d + 1)$$ is odd

The only thing left is to check the divisblity

Since $$a$$ is odd then $$a^d$$ is odd

But Of, course this entire solution is wrong since $$(c^d + 1)$$ is not necessarily divisible by $$a^d$$ but you get idea. I need a general solution like the one I provided.

Btw, I am not asking for a solution, some hint would be more than enough except if the equation I provided is unsolvable, In this can case plz tell me so.

• Why can't you just write $r=a^b$ and $s=c^d$ and solve $rx+sy=1$ by the Euclidean algorithm? Then $r$ is odd, and $s$ is even. Commented Mar 2, 2023 at 20:45
• @Dietrich Burde then $r = 2k_1 - 1$ and $s = 2k_2$ right? Commented Mar 2, 2023 at 20:49
• There is no closed form solution for general $\,a,b,c,d,\,$ but you can optimize the computation by using Hensel / Newton methods, e.g. assuming $(a,c)=1$ we have $\,x \equiv (a^{-1})^b\pmod{\!c^d}$ which can be computed by Hensel lifitng $\, a^{-1}\pmod{\! c}\,$ up to $\!\bmod c^d\,$ by Newton iteration, e.g. see here Commented Mar 2, 2023 at 21:12
$$a^b x + c^d y = 1$$ has no closed form solution for general (symbolic) integers $$\,a,b,c,d,\,$$ but we can optimize solution computation by using Hensel / Newton methods, e.g. assuming as you do that $$(a,c)=1$$ we have $$\,x \equiv (a^{-1})^b\pmod{\!c^d}$$ which can be computed very efficiently by Hensel lifting the inverse $$\, a^{-1}\pmod{\! c}\,$$ up to $$\!\bmod c^d\,$$ by Newton iteration, e.g. see the worked examples here and in its linked posts.