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

Non Iterative Modulous Calculation

  1. Jul 23, 2008 #1
    hello,

    I'm interested in non-iteratative modulous calculation. As in, I would like to calculate the number of steps one has to take to reach the desired answer without an iterative set of calculations of any kind

    (i.e. not

    a+b+ b+b+b+b+b = answer

    or

    a+b = answer? - nope
    a+2b = answer? - nope
    a+3b = answer? - nope
    a+4b = answer? - yes!


    )


    here are three varied examples to illustrate my problem




    Example one:

    The time starts at 12:00 (a 24 hour clock) and I check the clock every 43mins.

    I want to know how to calculate how many checks I will have made when I catch the clock and it shows 12:15

    (the answer is 1006 checks but how would I calculate it with a general rule?)



    Example two:

    f(1) = 19x
    f(2) = 30x + 1

    I need to calculate the first integer that is in both functions

    (the answer is 361, f1(x) = 19, f2(x) = 12)

    how would I calculate it with a general rule?




    Example three:

    f(1) = 9x
    f(2) = 13x + 1

    (the answer is 27, f1(x) = 3, f2(x) = 2. How would I calculate it?)


    thanks in advance
     
  2. jcsd
  3. Jul 23, 2008 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    All of these are examples of Diophantine equations, equation to be solved in terms of integers, and there is a standard way of solving linear Diophantine equations.




    Then you know wrong. After 1006 checks the clock will have run 1006*43= 43258 minutes. Since there are 24*60= 1440 minutes in 24 hours, the clock will have gone around 30 times (43258/1440= 30.04...) plus an additional 58 minutes. After 1006 checks, the clock will read 12:58, not 12:15. But 58- 43= 15 so, in fact, 1005 is correct. Perhaps your 1006 is including the starting time which I would not call a "check".

    You want a number n so that n*43= 15 (mod 24*60) or 43n= 15 (mod 1440) That is the same as asking for n and m so that 43n= 1440m+ 15 (m is the number of 24 hour cycles). And that is equivalent to the Diophantine equation 43n- 1440m= 15.

    Now, 43 divides into 1440 33 times with remainder 21- that is, 1440- 33(43)= 21. 21 divides into 43 twice with a remainder of 1- that is 43- 2(21)= 1. If we replace the 21 by 1440- 33(43), we have 43- 2(1440- 33(43))= 43- 2(1440)+ 66(43)= 67(43)- 2(1440)= 1. Multiplying both sides of that by 15, 1005(43)- 30(1440)= 15. One solution of 43n- 1440m= 15 is n= 1005, m= 30. That means that if we check 1005 times we will find the clock at 12:15


    First, you do NOT mean 'f1(x)= 19, f2(x)= 12'. You mean that f1(19)= 19(19)= 361 and f2(12)= 30(12)+ 1= 361. It wasn't until I looked at example 3 that I understood that!

    I interpret your problem as asking for integers m and n such that 19n= 30m+1. Again, that is a Diophantine equation, 19n- 30m= 1. 19 divides into 30 once with remainder 11: 30- 19= 11. 11 divides into 19 once with remainder 8: 19- 11= 8. 8 divides into 11 once with remainder 3: 11- 8= 3. 3 divides into 8 twice with remainder 2: 8- 2(3)= 2. And, finally, 2 divides into 3 once with remainder 1: 3- 2= 1. If we replace the 2 in that by 8- 2(3) we have 3- (8- 2(3))= 3(3)- 8= 1. If we replace the 3 in that by 11- 8, we have 3(11- 8)- 8= 3(11)- 4(8)= 1. If we replace 8 in that by 19- 11, we have 3(11)- 4(19- 11)= 7(11)- 4(19)= 1. Finally, if we replace the 11 by 30- 19, we have 7(30- 19)- 4(19)= 7(30)- 11(19)= 1. (Now that we have that it is easy to check that 7(30)- 11(19)= 210- 209= 1.)
    A solution to the Diophantine equation 19n- 30m= 1 is n= -11, m= -7. f1(-11)= 19(-11) = -209 and f2(-7)= 30(-7)+ 1= -210+1= -209.

    Of course, there are other possible solutions. If we add 30k to n and 19k to m, for any integer k, we have f1(n+ 30k)= 19n+ 19(30)k and f2(m+ 30k)= 19(m+ 30k)+ 1= 19m+ 1+ 19(30)k so as long as m and n give the same value, so do n+ 19k and m+ 30k for any k.
    Taking k= 1 gives n= -11+ 30= 19 and m= -7+ 19= 12: f1(19)= 19(19)= 361 and f2(12)= 30(12)+ 1= 361. That is the smallest positive integer value that is the same for both functions.


    Here, you mean f1(3)= 27, f2(2)= 27, not that f1(x)= 3, f2(x)= 2.

    Again, 9n= 13m+ 1 is the same as 9n- 13m= 1. 9 divides into 13 once with remainder 4: 13- 9= 4. 4 divides into 9 twice with remainder 1: 9- 2(4)= 1. If we replace that 4 by 13- 9 we have 9- 2(13- 9)= 3(9)- 2(13)= 1. That tells you that n= 3 and m= 2 and the common value is f1(3)= 9(3)= 27 = 26+ 1= 13(2)+ 1= f2(2)


    You are welcome.
     
    Last edited: Jul 23, 2008
  4. Jul 23, 2008 #3
    yes I included the start at 12:00 as one check

    thanks for your help



    I'm just going through your steps:


    (hopefully) my last stupid question, but what reasoning did you use to reformat the equations:

    * 9- 2(13- 9) to equal 3(9)- 2(13)

    and from example two:

    * 3- (8- 2(3)) to equal 3(3)- 8= 1
    * 3(11- 8)- 8 to equal 3(11)- 4(8)= 1
    * 7(30- 19)- 4(19) to equal 7(30)- 11(19)= 1
     
  5. Jul 24, 2008 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Basic algebra 9- 2(13- 9)= 9- 2(13)+ 2(9)= (1+ 2)(9)- 2(13)= 3(9)- 2(13)

    3- (8- 2(3))= 3- 8+ 2(3)= (3+ 2)(3)- 8= 3(3)- 8

    3(11- 8)- 8= 3(11)- 3(8)- 8= 3(11)- (3+1)(8)= 3(11)- 4(8)

    7(30- 19)- 4(19)= 7(30)- 7(19)- 4(19)= 7(30)- (7+ 4)(19)= 7(30)- 11(19)
     
    Last edited: Jul 24, 2008
  6. Jul 25, 2008 #5
    I understand basic algebra. I just don't (fully) understand the methodology you've used to get to your answer when applied to (slightly) different functions

    Perhaps I'm being a bit dense,

    for example, this works fine:



    but when I have additions to both of the functions (answer: 112):

     
  7. Jul 25, 2008 #6

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    The problem is in
    "c. 3 divides into 6 = 2 r 0

    6 - 3(2) = 0

    ???"
    as I am sure you see by your "???"! The objective is to eventually get "= 1" so we can work back to the orignal equation. Getting "= 0" makes that impossible.

    The problem is that, here, your original equation, 9m - 33n = 9, has all three of its coefficients divisible by 3: that's why you got "6 divided by 3 gives a remainder of 0".

    Of course, we can simplify that equation by dividing through by 3: 3m- 11n= 3.
    Now, 3 divides into 11 3 times with a remainder of 2: 11- 3(3)= 2. 2 divides into 3 once with remainder 1: 3- 2= 1. Replacing the "2" in that by 11- 3(3), we have 3- (11- 3(3))= 4(3)- (1)11= 1 (which is true: 12- 11= 1). Now, multiply through by 3 to get 12(3)- 3(11)= 3 (still true: 36- 33= 3) so m= 12, n= 3 is a solution. And, obviously, 3(12(3)- 3(11)= 3(9)- 3(33)= 3(3)= 9 so m= 12, n= 3 is a solution to the original equation. Of course it is easy to see that m= 12+ 11k, n= 3+ 3k is also a solution for any integer k: 3(12+ 11k)- 11(3+ 3k)= 36+ 33k- 33- 33k and the two "33k" terms cancel out.

    Suppose you had 9m- 33n= 8, where the two coefficients have a common factor, 3, but the term on the right side doesn't. Now, you would get "= 0" as before (we don't multiply by the right side until after we get "=1") but we can't divide through by 3 and still have integers. It's easy to see, in that case, that for any m and n, 9m- 33n= 3(3m- 11n) and so is a multiple of 3. If the right side is not a multiple of 3 they can't be equal- there is NO integer solution.

    If, in am- bn= c, a and b have a common factor but c does NOT have that factor, there is NO solution. If a, b, and c all have a common factor, divide through by that factor first.
     
  8. Jul 28, 2008 #7
    ok, last one using your method (answer is 533, m = 18, n = 16)...

    f(1) = 29x + 11
    f(2) = 33x + 5


    initial:

    29m - 33n = -6 or
    29m - 33n = 27 or
    33n - 29m = 6


    steps:

    33/29 = 1 r 4

    33 - 29 = 4

    29/4 = 7 r 1


    29 - 7(4) = 1


    29 - 7(33) + 7(29) = 1

    answer: 7(33) - 8(29) = 1


    n is not 7 and m is not 8.

    ...Also no multiplication of 7 and 8 will make the true answer: m = 18 and n = 16. Nor will

    help! :(
     
  9. Jul 28, 2008 #8

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    How did you get that second equation? The two functions will give the same value when 29m+ 11= 33n+ 5. Then 29m- 33n= 5- 11= -6.

    No. 7(33) - 8(29)= 231- 232= -1. you have the signs wrong.


    Yes, it is true that 7(33)- 8(29)= -1 but your problem was 29m- 33n= -6, not 1. Multiply through by 6: 42(33)- 48(29)= -6. (Check: 42(33)= 1386 and 48(29)= 1392: difference, -6) Because the signs are wrong on that, m= -42 and n= -48 is a solution. Other integer solutions are given by m= -42+ 29k, n= -48+ 33k for any integer k. Taking k= 2 gives the smallest positive solution: m= -42+ 58= 16, n= -48+ 66= 18.
    f1(18)= 29(18)+ 11= 533 and f2(15)= 33(15)+ 5= 533/
     
  10. Jul 30, 2008 #9
    ok, so your basic algorithm is:

    step one:

    f(1) = am + c
    f(2) = bn + d

    am + c = bn + d

    am - bn = c - d

    step two:

    while remainder does not equal "1"

    a / b = [possible factor] remainder [a]

    step three:

    replace and factorise an earlier iteration of step two to get two mutiplicands of the original [a] and which are your answers (if the answer to the step is a factor of [c-d] multiply both sides answer on the right is: [c-d])

    =====================================

    where have I gone wrong in the following?:

    f(1) = 19x + 15
    f(2) = 37x + 2


    19m + 15 = 37n + 2
    19m - 37n = -13


    * 37 / 19 = 1 r 18

    37 - 19 = 18

    * 19 / 18 = 1 r 1

    19 / 18 = 1


    ???

    please be patient, I've almost got it!
     
  11. Jul 30, 2008 #10

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor


    No, 19/18 is not equal to 1, the quotient is 1 with remainder 1 as you say just above that.

    As to "where have I gone wrong", you have done nothing wrong except that you have not completed it. "19/8= 1 r 1" tells you that 19- 18= 1 (obvious!) and 37/19= 1 r 18 tells you that 37- 19= 18. So 19- 18= 19- (37- 19)= 2(19)- 37= 1.

    Since you want "= -13", multiply that equation by -13: (-26)(19)- (-13)(37)= -13. That tells you that one solution to 19m- 37n= -13 is m= -26, n= -13. Any integer solution can be written m= -26+ 37k, n= -13+ 19k for k any integer. In particular, taking k= 1 gives the smallest positive integer solution: m= -26+ 37= 11, n= -13+ 19= 6.

    As a check, 11(19)- 6(37)= 209- 222= -13.

    Or, since your original problem was to find common values for
    f1(x) = 19x + 15
    f2(x) = 37x + 2

    f1(11)= 19(11)+ 15= 209+ 15= 224
    f2(6)= 37(6)+ 2= 222+ 2= 224.
     
  12. Jul 31, 2008 #11
    I understand all of your solutions. Thanks

    I was under the impression that (after you have divided through by all common factors) if "=0"appears and ="1" doesn't, there is no solution

    which seems to be indicated here:

    but somehow...

    answer: 465

    f(1) = 21x + 3
    f(2) = 23x + 5

    21m - 23n = 2

    * 21 divides into 23 = 1 r 3

    23 - 21 = 3


    * 3 divides into 21 = 7 r 0

    21 - 7(3) = 0

    now obviously

    7(23) - 8(21) = 0

    ???

    so how do you get from

    7(23) - 8(21) = 0 to the actual answer which is 20(23) - 22(21) = 2


    Thanks in advance
     
  13. Jul 31, 2008 #12

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Well, no. 23- 21= 2, not 3.

     
  14. Jul 31, 2008 #13
    *brain fart*

    in that case I'm done, thanks for all of your help :)
     
  15. Aug 22, 2008 #14
    hello, sorry to trouble you again, I thought this was all done and dusted

    I've since written an algorithm, but it came across a problem when it came to this (btw: answer is: 210, or 14(15) - 11(19) = 1 )


    f(1) = 15x
    f(2) = 19x + 1


    15n - 19m = 1.


    * 15 divides into 19 once with remainder 4:
    19-15 = 4

    * 4 divides into 15 thrice with remainder 3
    15 - 3(4) = 3

    * finally 4 divides into 3 once with remainder 1
    4 - 3 = 1


    ----------------------

    * if we replace the 3 in [4 - 3] with [15-3(4)] we get

    4 - 15-3(4) = 1 or:

    4(4) - 15 = 1

    * if we replace the 4 in [4(4) - 15] with [19-18] we get

    4(19) - 4(15) - 15 = 1 or

    4(19) - 5(15) = 1

    n = 4, m = 5 which would be correct if it where 15x + 1 and 19x

    where have I gone wrong?

    thanks in advance :)
     
  16. Aug 23, 2008 #15

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor


    Look back at your original equation: you wanted to solve 15n - 19m = 1. You have instead 4(19)- 5(15)= 1. The numbers are reversed. You need to write (-5)(15)- (-4)(19)= 1. Your solutions are n= -5 and m= -4. If you want, say, the smallest positive solution, use the fact that, for any integer k, n= -5+ 19k, m= -4+ 15k is also a solution.

    (Do you see what happens if you replace n and m by those in the equation? 15n- 19m becomes 15(-5+ 19k)- 19(-4+ 15k)= (-5)(15)- (-4)(1)+ (15)(19k)- (19)(15k) and the terms involving k cancel.)

    Taking k= 1, n= -5+ 19= 14, m= -4+ 15= 11. f1(14)= 15(14)= 210, f(11)= 19(11)+ 1= 209+ 1= 210.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Non Iterative Modulous Calculation
  1. Iterated integrals (Replies: 6)

  2. Iterated tangent (Replies: 0)

  3. Iterative routines (Replies: 13)

Loading...