# Searching for a non-negative integer

1. Jun 17, 2004

### Nec

I have an integer A and a possitive odd integer B, can you tell me how to find a nonnegative integer C such that C<2^A and 1+BC=0(mod 2^A) ??????

????

2. Jun 17, 2004

### davilla

Sorry, I don't remember how to solve Diophantine equations off the top of my head. Anyways, where's the brain teaser?

3. Jun 17, 2004

### Nec

You give me the solution, I will sure tell you where it is...lol...

4. Jun 18, 2004

### Nec

Anyone ???

5. Jun 18, 2004

### Gokul43201

Staff Emeritus
Give us a day. It sure looks like a solution (C<2^A, and C odd) exists for every odd B.

Last edited: Jun 18, 2004
6. Jun 18, 2004

### Gokul43201

Staff Emeritus
If you have A = 4, 2^A = 16.
Any odd B is 4k+1 or 4k-1. Choose C to be the other of the pair.
So, 1+BC = 1+ (4k+1)(4k-1) = 16k^2 == 0 (mod 16)

Looking for a general solution for all A.

7. Jun 18, 2004

### arivero

As C is bounded, I would use a loop
Do[If[Mod[1+B C,2^A]==0,Print[C]],{C,1,2^A}]

8. Jun 18, 2004

### arivero

Hey I can also do it by hardware...
Code (Text):

CLOCK-->---------(E)->COUNTER(C)         REGISTER(B)
E    |                           |           |
^     |                           |           |
|    |                           v           v
|     ----(E)------------>MULTIPLiER
|                                        |
|                                        |
-----------<-----------------------(AND)

Last edited: Jun 18, 2004
9. Jun 18, 2004

### Gokul43201

Staff Emeritus
I hope this is not what Nec means by "how do you find..." I have been looking for analytic forms of the kind, C = f(A,B)

10. Jun 18, 2004

### Nec

I already put you into my list of top 10 ! --smile--

11. Jun 18, 2004

### Nec

Thanks for any1 who has given my problem some shots --smile--

12. Jun 19, 2004

### Gokul43201

Staff Emeritus
Hey Nec,

Can you tell us what it is you are looking for - an existence proof or an analytic form for C given A,B ?

Also, Would it be okay if I reposted this question in the Number Theory section ?There's bound to be someone who can crack it in no time at all.

13. Jun 20, 2004

### Gokul43201

Staff Emeritus
Hey Nec,

I've heard from Hurkyl and matt grime, that there is no analytic form for determining C from A,B. However, C can be found using the Euclidean algorithm (backwards).

Example : Let, A = 6 => 2^A = 64, B = 17. We always know that GCD (2^A,B) = 1.

This can be found using the Euclidean Algorithm , as follows :

64 = 17.3 + 13
17 = 13.1 + 4
13 = 4.3 + 1

Now retrace, 1 = 13 - 4.3 = 13 - (17 - 13.1).3 = 13 - 17.3 + 13.3 = 13.4 - 17.3
= (64 - 17.3).4 - 17.3 = 64.4 - 17.12 - 17.3 = 64.4 - 17.15

So, 1 + 17.15 = 64.4 OR C = 15

If this is not clear, look up the Euclidean Algorithm for determining the GCD and also see linear Diophantine Equations.

http://mathworld.wolfram.com/EuclideanAlgorithm.html
http://mathworld.wolfram.com/DiophantineEquation.html

14. Jun 20, 2004

### Nec

Sorry, I have been out of town since Sunday's morning, I could not answer your post...
Yes, I was wondering if there was an analytic form to archieve Cs from A and B. Thanks Gokul alot for your help and links, --lol--