modular math problem

[Gokul43201]

Given, A>0 and odd B>0, find C = f(A,B), satisfying :

1 + BC == 0 (mod 2^A)

[matt grime]

Euclid's Algorithm on B and 2**A will do it. sorry, my six key is buggered so i can't do powers in pseudotex.

[Gokul43201]

matt,

I'm not sure I follow. You are talking about the GCD algorithm, right ?

I don't see how this works. Can you show me how, on an example, say 2^A = 64, B = 15 ?

[Hurkyl]

Recall that the extended Euclidean algorithm will give you two numbers, u and v, such that u * m + v * n = gcd(m, n)...

[Gokul43201]

Yes, I've used it to solve linear diophantine eqns...but don't see how it can be used here.

[matt grime]

B is odd, 2**A is a power of two, they are coprime.

[Hurkyl]

Maybe it would help if I rewrite it as

(-u) * m + gcd(m, n) = v * n

?

[Gokul43201]

Thanks,

I never cease to amaze myself !