Searching for a non-negative integer

[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) ?

?

 

[davilla]

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)

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

 

[Nec]

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

 

[Nec]

Anyone ?

 

[Gokul43201]

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

 

[Gokul43201]

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.

 

[arivero]

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) ?

?

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

 

[arivero]

Hey I can also do it by hardware...

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

 

[Gokul43201]

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)

 

[Nec]

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.

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

 

[Nec]

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

 

[Gokul43201]

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.

 

[Gokul43201]

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

 

[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 a lot for your help and links, --lol--