Given, A>0 and odd B>0, find C = f(A,B), satisfying :
1 + BC == 0 (mod 2^A)
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.
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 ?
Recall that the extended Euclidean algorithm will give you two numbers, u and v, such that u * m + v * n = gcd(m, n)...
Yes, I've used it to solve linear diophantine eqns...but don't see how it can be used here.
B is odd, 2**A is a power of two, they are coprime.
Maybe it would help if I rewrite it as
(-u) * m + gcd(m, n) = v * n
I never cease to amaze myself !
Separate names with a comma.