Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Searching for a non-negative integer

  1. Jun 17, 2004 #1

    Nec

    User Avatar

    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. jcsd
  3. Jun 17, 2004 #2
    Sorry, I don't remember how to solve Diophantine equations off the top of my head. Anyways, where's the brain teaser?
     
  4. Jun 17, 2004 #3

    Nec

    User Avatar

    You give me the solution, I will sure tell you where it is...lol...
     
  5. Jun 18, 2004 #4

    Nec

    User Avatar

    Anyone ???
     
  6. Jun 18, 2004 #5

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
  7. Jun 18, 2004 #6

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  8. Jun 18, 2004 #7

    arivero

    User Avatar
    Gold Member

    As C is bounded, I would use a loop
    Do[If[Mod[1+B C,2^A]==0,Print[C]],{C,1,2^A}]
     
  9. Jun 18, 2004 #8

    arivero

    User Avatar
    Gold Member

    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
  10. Jun 18, 2004 #9

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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)
     
  11. Jun 18, 2004 #10

    Nec

    User Avatar

    I already put you into my list of top 10 ! --smile--
     
  12. Jun 18, 2004 #11

    Nec

    User Avatar

    Thanks for any1 who has given my problem some shots --smile--
     
  13. Jun 19, 2004 #12

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  14. Jun 20, 2004 #13

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
     
  15. Jun 20, 2004 #14

    Nec

    User Avatar

    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--
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Searching for a non-negative integer
  1. Poem Search (Replies: 13)

  2. Yagoohoogle search (Replies: 11)

  3. Search for: ? (Replies: 4)

  4. Search of the Union (Replies: 7)

  5. Search for a phrase? (Replies: 7)

Loading...