0
$\begingroup$

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.

Thanks in advance.

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Mar 2, 2023 at 20:45
  • $\begingroup$ @Dietrich Burde then $r = 2k_1 - 1$ and $s = 2k_2$ right? $\endgroup$
    – Danny
    Commented Mar 2, 2023 at 20:49
  • $\begingroup$ @Ditrich Can I have another hint? $\endgroup$
    – Danny
    Commented Mar 2, 2023 at 20:57
  • $\begingroup$ 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 $\endgroup$ Commented Mar 2, 2023 at 21:12
  • $\begingroup$ @Bill Dubuque that's what I am talking about. you got my point. I can have this marked as answer $\endgroup$
    – Danny
    Commented Mar 2, 2023 at 21:14

1 Answer 1

1
$\begingroup$

$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.

[comment promoted to answer per OP request]

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .