Non Iterative Modulous Calculation

[spikenigma]

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

 

[HallsofIvy]

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

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.

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

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

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?

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.

Example three:

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

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

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)

thanks in advance

You are welcome.

 

[spikenigma]

*snip clock example

yes I included the start at 12:00 as one check

thanks for your help



I'm just going through your steps:

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

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)
[/size]

(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

 

[HallsofIvy]

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)

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

and from example two:

* 3- (8- 2(3)) to equal 3(3)- 8= 1

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

* 3(11- 8)- 8 to equal 3(11)- 4(8)= 1

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

* 7(30- 19)- 4(19) to equal 7(30)- 11(19)= 1

7(30- 19)- 4(19)= 7(30)- 7(19)- 4(19)= 7(30)- (7+ 4)(19)= 7(30)- 11(19)

 

[spikenigma]

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:

f(1) = 51x
f(2) = 57x + 18

* 51n = 57m + 18 is the same as 51n - 57m = 18

a. 51 divides into 57 = 1 r 6

57 - 51 = 6

b. 6 divides into 51 = 8 r 3

51 - 8(6) = 3

c. 3 divides into 6 = 2 r 0

6 - 2(3) = 0


d. if we replace the 6 [in step b] with (57-51)

51 - 8(57) + 8(51) = 3

which equals

8(57) - 9(51) = 3

which equals

48(57) - 54(51) = 18


answer: 2754
[/size]

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

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


9m + 4 = 33n + 13 is the same as 9m - 33n = 9

a. 9 divides into 33 = 3 r 6

33-3(9) = 6

b. 6 divides into 9 = 1 r 3

9-6 = 3

c. 3 divides into 6 = 2 r 0

6 - 3(2) = 0

?

[from step a] replacing the 3 with [9-6] from step b.

d. 33 - 9(9) + 9(6) = 6

33 is not a factor in either 9(9) nor 9(6) and I don't want to further simplify or I may lose the factors

?
[/size]

 

[HallsofIvy]

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


9m + 4 = 33n + 13 is the same as 9m - 33n = 9

a. 9 divides into 33 = 3 r 6

33-3(9) = 6

b. 6 divides into 9 = 1 r 3

9-6 = 3

c. 3 divides into 6 = 2 r 0

6 - 3(2) = 0

?

[from step a] replacing the 3 with [9-6] from step b.

d. 33 - 9(9) + 9(6) = 6

33 is not a factor in either 9(9) nor 9(6) and I don't want to further simplify or I may lose the factors

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.

 

[spikenigma]

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! :(

 

[HallsofIvy]

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

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.

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

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

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! :(

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/

 

[spikenigma]

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!

 

[HallsofIvy]

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!

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.

 

[spikenigma]

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:

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.

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

 

[HallsofIvy]

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

Well, no. 23- 21= 2, not 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

 

[spikenigma]

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

*brain fart*

in that case I'm done, thanks for all of your help :)

 

[spikenigma]

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

 

[HallsofIvy]

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

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.