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

Short method for computing this?

  1. May 26, 2015 #1
    suppose a side of an equation : 26q+1 , and i want the least positive integer value for q that makes this side of equation divisible by 7, is there any short method to do this ?
     
  2. jcsd
  3. May 26, 2015 #2

    Merlin3189

    User Avatar
    Gold Member

    I don't know any short method, but you can work in mod 7.

    So for eg. if 11x + 8 is divisible by 5, then in mod 5
    11x + 8 = 0
    10x + x + 8 = 0
    0 + x + 8 = 0
    x + 3 + 5 = 0
    x + 3 + 0 = 0
    So x is 2, 7, 12, etc.

    Ed: just noticed this is too simple. So 13x +9 is divisible by 5. In mod 5,
    13x + 9 = 0
    3x + 4 = 0
    3x = -4
    3x = 1
    so 3x = 6, 11, 16, 21, 26, 31, 36, etc
    so x= 2, 7, 12, etc.
     
    Last edited: May 26, 2015
  4. May 26, 2015 #3
    but when working with higher mod like mod 26 would this way be efficient ? for example when 9x-1 is divisible by 26
     
  5. May 27, 2015 #4

    Merlin3189

    User Avatar
    Gold Member

    No, I don't know how to make that simpler. Perhaps if you search on Diophantine equations, you can find something to help.

    AFAIK
    9x-1 = 0 (Mod 26)
    then 9x= 1 is as far as I can get.
    So 9x = 1, 27, 53, 79, 105,... The only way I can see to help now, is to look at these Mod 9
    (so 0 = 1, 0, 8, 7, 6, 5, 4, 3, 2, 1, 0, ..) so the second term is the first that is not false
    so 9x = second term = first term + 1 x 26 = 1 + 1*26 = 27
    so x= 3
    Check 9 x 3 - 1 = 27 -1 =26

    That was a bit too easy,
    so try 9x -17 = 0 (Mod 26)
    then 9x = 17
    So 9x = 17, 43, 69, ...
    now to looking at these Mod 9
    (so 0 = 8, 7, 6, 5, 4, 3, 2, 1, 0, .. ) so the 9th term is the first that is not false
    so 9x = 9th term = first term + 8 x 26 = 17 + 8*26 = 225
    so x= 25
    (Check 9 x 25 - 17 = 225 -17 = 208 = 26 x 8 )

    It actually looks as if you could simplify the Mod 9 step, but in some cases the change in mod base does not give such a simple sequence.
     
  6. May 29, 2015 #5

    Svein

    User Avatar
    Science Advisor

    A short trip into Excel gave q=4 (next one is 11, then 18 , 25).
     
  7. May 29, 2015 #6

    Merlin3189

    User Avatar
    Gold Member

    But what method did you use in Excel?
     
  8. May 29, 2015 #7

    Svein

    User Avatar
    Science Advisor

    Brute force - I created the series 0, 1, 2... 29 in column B, 26*Bn + 1 in column C and Mod(Cn, 7) in column D. Then I just looked for 0 in column D.
    (
    0 1 1
    1 27 6
    2 53 4
    3 79 2
    4 105 0
    5 131 5
    6 157 3
    7 183 1
    8 209 6
    9 235 4
    10 261 2
    11 287 0
    12 313 5
    13 339 3
    14 365 1
    15 391 6
    16 417 4
    17 443 2
    18 469 0
    19 495 5
    20 521 3
    21 547 1
    22 573 6
    23 599 4
    24 625 2
    25 651 0
    26 677 5
    27 703 3
    28 729 1
    29 755 6)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook