# Modular math problem

1. Jun 19, 2004

### Gokul43201

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

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

2. Jun 19, 2004

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

3. Jun 19, 2004

### Gokul43201

Staff Emeritus
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 ?

4. Jun 19, 2004

### Hurkyl

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

5. Jun 19, 2004

### Gokul43201

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

6. Jun 20, 2004

### matt grime

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

7. Jun 20, 2004

### Hurkyl

Staff Emeritus
Maybe it would help if I rewrite it as

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

?

8. Jun 20, 2004

### Gokul43201

Staff Emeritus
Thanks,

I never cease to amaze myself !