[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 367
  • Last Modified:

Modulo arithmetic problem

Let a,b,c be pairwise-coprime integers. I need to find the smallest integer t satisfying

   at+b=0 (mod c)

Any ideas? I keep thinking something along the lines of the Euclidean algorithm except the modulo complicates things.

Thanks in advance.
0
InteractiveMind
Asked:
InteractiveMind
  • 4
1 Solution
 
sdstuberCommented:
for small numbers it's not too difficult to find them exhaustively
A	B	C	T
--------------------------------------------
2	3	5	6
2	3	7	2
2	3	11	4
2	3	13	5
2	3	17	7
2	3	19	8
2	5	3	2
2	5	7	8
2	5	9	2
2	5	11	3
2	5	13	4
2	5	17	6
2	5	19	7
2	5	21	8
2	7	3	4
2	7	5	4
2	7	9	10
2	7	11	2
2	7	13	3
2	7	15	4
2	7	17	5
2	7	19	6
2	9	5	3
2	9	7	6
2	9	11	12
2	9	13	2
2	9	17	4
2	9	19	5
2	11	3	2
2	11	5	2
2	11	7	5
2	11	9	8
2	11	13	14
2	11	15	2
2	11	17	3
2	11	19	4
2	11	21	5
2	13	3	4
2	13	5	6
2	13	7	4
2	13	9	7
2	13	11	10
2	13	15	16
2	13	17	2
2	13	19	3
2	13	21	4
2	15	7	3
2	15	11	9
2	15	13	12
2	15	17	18
2	15	19	2
2	17	3	2
2	17	5	4
2	17	7	2
2	17	9	5
2	17	11	8
2	17	13	11
2	17	15	14
2	17	19	20
2	17	21	2
2	19	3	4
2	19	5	3
2	19	7	8
2	19	9	4
2	19	11	7
2	19	13	10
2	19	15	13
2	19	17	16
2	21	5	2
2	21	11	6
2	21	13	9
2	21	17	15
2	21	19	18
3	2	5	6
3	2	7	4
3	2	11	3
3	2	13	8
3	2	17	5
3	2	19	12
3	4	5	2
3	4	7	8
3	4	11	6
3	4	13	3
3	4	17	10
3	4	19	5
3	5	2	3
3	5	4	5
3	5	7	3
3	5	8	9
3	5	11	2
3	5	13	7
3	5	14	3
3	5	16	9
3	5	17	4
3	5	19	11
3	7	2	3
3	7	4	3
3	7	5	6
3	7	8	3
3	7	10	11
3	7	11	5
3	7	13	2
3	7	16	3
3	7	17	9
3	7	19	4
3	7	20	11
3	8	5	4
3	8	7	2
3	8	11	12
3	8	13	6
3	8	17	3
3	8	19	10
3	10	7	6
3	10	11	4
3	10	13	14
3	10	17	8
3	10	19	3
3	11	2	3
3	11	4	3
3	11	5	3
3	11	7	8
3	11	8	7
3	11	10	3
3	11	13	5
3	11	14	15
3	11	16	7
3	11	17	2
3	11	19	9
3	11	20	3
3	13	2	3
3	13	4	5
3	13	5	4
3	13	7	5
3	13	8	9
3	13	10	9
3	13	11	3
3	13	14	5
3	13	16	17
3	13	17	7
3	13	19	2
3	13	20	9
3	14	5	2
3	14	11	10
3	14	13	4
3	14	17	18
3	14	19	8
3	16	5	3
3	16	7	4
3	16	11	2
3	16	13	12
3	16	17	6
3	16	19	20
3	17	2	3
3	17	4	5
3	17	5	6
3	17	7	6
3	17	8	5
3	17	10	11
3	17	11	9
3	17	13	3
3	17	14	13
3	17	16	5
3	17	19	7
3	17	20	21
3	19	2	3
3	19	4	3
3	19	5	2
3	19	7	3
3	19	8	7
3	19	10	7
3	19	11	12
3	19	13	11
3	19	14	3
3	19	16	15
3	19	17	5
3	19	20	7
3	20	7	5
3	20	11	8
3	20	13	2
3	20	17	16
3	20	19	6
4	3	5	3
4	3	7	8
4	3	11	2
4	3	13	9
4	3	17	12
4	3	19	4
4	5	3	4
4	5	7	4
4	5	9	10
4	5	11	7
4	5	13	2
4	5	17	3
4	5	19	13
4	5	21	4
4	7	3	2
4	7	5	2
4	7	9	5
4	7	11	12
4	7	13	8
4	7	15	2
4	7	17	11
4	7	19	3
4	9	5	4
4	9	7	3
4	9	11	6
4	9	13	14
4	9	17	2
4	9	19	12
4	11	3	4
4	11	5	6
4	11	7	6
4	11	9	4
4	11	13	7
4	11	15	16
4	11	17	10
4	11	19	2
4	11	21	13
4	13	3	2
4	13	5	3
4	13	7	2
4	13	9	8
4	13	11	5
4	13	15	8
4	13	17	18
4	13	19	11
4	13	21	2
4	15	7	5
4	15	11	10
4	15	13	6
4	15	17	9
4	15	19	20
4	17	3	4
4	17	5	2
4	17	7	8
4	17	9	7
4	17	11	4
4	17	13	12
4	17	15	7
4	17	19	10
4	19	3	2
4	19	5	4
4	19	7	4
4	19	9	2
4	19	11	9
4	19	13	5
4	19	15	14
4	19	17	8
4	19	21	11
4	21	5	6
4	21	11	3
4	21	13	11
4	21	17	16
4	21	19	9
5	2	3	2
5	2	7	8
5	2	9	5
5	2	11	4
5	2	13	10
5	2	17	3
5	2	19	11
5	2	21	8
5	3	2	3
5	3	4	5
5	3	7	5
5	3	8	9
5	3	11	6
5	3	13	2
5	3	14	5
5	3	16	9
5	3	17	13
5	3	19	7
5	4	3	4
5	4	7	2
5	4	9	10
5	4	11	8
5	4	13	7
5	4	17	6
5	4	19	3
5	4	21	16
5	6	7	3
5	6	11	12
5	6	13	4
5	6	17	9
5	6	19	14
5	7	2	3
5	7	3	4
5	7	4	5
5	7	6	7
5	7	8	5
5	7	9	4
5	7	11	3
5	7	12	13
5	7	13	9
5	7	16	5
5	7	17	2
5	7	18	13
5	7	19	10
5	8	3	2
5	8	7	4
5	8	9	2
5	8	11	5
5	8	13	14
5	8	17	12
5	8	19	6
5	8	21	11
5	9	2	3
5	9	4	3
5	9	7	8
5	9	8	3
5	9	11	7
5	9	13	6
5	9	14	15
5	9	16	11
5	9	17	5
5	9	19	2
5	11	2	3
5	11	3	2
5	11	4	5
5	11	6	5
5	11	7	2
5	11	8	9
5	11	9	5
5	11	12	5
5	11	13	3
5	11	14	9
5	11	16	17
5	11	17	8
5	11	18	5
5	11	19	13
5	11	21	2
5	12	7	6
5	12	11	2
5	12	13	8
5	12	17	18
5	12	19	9
5	13	2	3
5	13	3	4
5	13	4	3
5	13	6	7
5	13	7	3
5	13	8	7
5	13	9	10
5	13	11	4
5	13	12	7
5	13	14	3
5	13	16	7
5	13	17	11
5	13	18	19
5	13	19	5
5	13	21	10
5	14	3	2
5	14	9	8
5	14	11	6
5	14	13	5
5	14	17	4
5	14	19	20
5	16	3	4
5	16	7	8
5	16	9	4
5	16	11	10
5	16	13	2
5	16	17	7
5	16	19	12
5	17	2	3
5	17	3	2
5	17	4	3
5	17	6	5
5	17	7	5
5	17	8	3
5	17	9	2
5	17	11	12
5	17	12	11
5	17	13	7
5	17	14	5
5	17	16	3
5	17	18	11
5	17	19	8
5	17	21	5
5	18	7	2
5	18	11	3
5	18	13	12
5	18	17	10
5	18	19	4
5	19	2	3
5	19	3	4
5	19	4	5
5	19	6	7
5	19	7	6
5	19	8	9
5	19	9	7
5	19	11	5
5	19	12	13
5	19	13	4
5	19	14	13
5	19	16	9
5	19	17	3
5	19	18	7
5	19	21	13
5	21	2	3
5	21	4	3
5	21	8	7
5	21	11	9
5	21	13	14
5	21	16	15
5	21	17	6
5	21	19	11
6	5	7	5
6	5	11	12
6	5	13	10
6	5	17	2
6	5	19	15
6	7	5	3
6	7	11	8
6	7	13	14
6	7	17	13
6	7	19	2
6	11	5	4
6	11	7	4
6	11	13	9
6	11	17	18
6	11	19	14
6	13	5	2
6	13	7	6
6	13	11	7
6	13	17	12
6	13	19	20
6	17	5	3
6	17	7	3
6	17	11	10
6	17	13	8
6	17	19	13
6	19	5	6
6	19	7	5
6	19	11	6
6	19	13	12
6	19	17	11
7	2	3	4
7	2	5	4
7	2	9	10
7	2	11	6
7	2	13	9
7	2	15	4
7	2	17	7
7	2	19	16
7	3	2	3
7	3	4	3
7	3	5	6
7	3	8	3
7	3	10	11
7	3	11	9
7	3	13	7
7	3	16	11
7	3	17	2
7	3	19	5
7	3	20	11
7	4	3	2
7	4	5	3
7	4	9	2
7	4	11	12
7	4	13	5
7	4	15	8
7	4	17	14
7	4	19	13
7	5	2	3
7	5	3	4
7	5	4	5
7	5	6	7
7	5	8	5
7	5	9	7
7	5	11	4
7	5	12	13
7	5	13	3
7	5	16	13
7	5	17	9
7	5	18	7
7	5	19	2
7	6	5	2
7	6	11	7
7	6	13	14
7	6	17	4
7	6	19	10
7	8	3	4
7	8	5	6
7	8	9	4
7	8	11	2
7	8	13	10
7	8	15	16
7	8	17	11
7	8	19	7
7	9	2	3
7	9	4	5
7	9	5	3
7	9	8	9
7	9	10	3
7	9	11	5
7	9	13	8
7	9	16	17
7	9	17	6
7	9	19	15
7	9	20	13
7	10	3	2
7	10	9	5
7	10	11	8
7	10	13	6
7	10	17	18
7	10	19	4
7	11	2	3
7	11	3	4
7	11	4	3
7	11	5	2
7	11	6	7
7	11	8	3
7	11	9	10
7	11	10	7
7	11	12	7
7	11	13	4
7	11	15	7
7	11	16	3
7	11	17	13
7	11	18	19
7	11	19	12
7	11	20	7
7	12	5	4
7	12	11	3
7	12	13	2
7	12	17	8
7	12	19	20
7	13	2	3
7	13	3	2
7	13	4	5
7	13	5	6
7	13	6	5
7	13	8	5
7	13	9	2
7	13	10	11
7	13	11	6
7	13	12	5
7	13	15	11
7	13	16	5
7	13	17	3
7	13	18	11
7	13	19	9
7	13	20	21
7	15	2	3
7	15	4	3
7	15	8	7
7	15	11	12
7	15	13	9
7	15	16	7
7	15	17	10
7	15	19	6
7	16	3	2
7	16	5	2
7	16	9	8
7	16	11	4
7	16	13	7
7	16	15	2
7	16	17	5
7	16	19	14
7	17	2	3
7	17	3	4
7	17	4	5
7	17	5	4
7	17	6	7
7	17	8	9
7	17	9	4
7	17	10	9
7	17	11	7
7	17	12	13
7	17	13	5
7	17	15	4
7	17	16	9
7	17	18	13
7	17	19	3
7	17	20	9
7	18	5	6
7	18	11	10
7	18	13	3
7	18	17	12
7	18	19	11
7	19	2	3
7	19	3	2
7	19	4	3
7	19	5	3
7	19	6	5
7	19	8	3
7	19	9	5
7	19	10	3
7	19	11	2
7	19	12	11
7	19	13	14
7	19	15	8
7	19	16	11
7	19	17	7
7	19	18	5
7	19	20	3
7	20	3	4
7	20	9	10
7	20	11	5
7	20	13	12
7	20	17	2
7	20	19	8
8	3	5	4
8	3	7	4
8	3	11	12
8	3	13	11
8	3	17	6
8	3	19	2
8	5	3	2
8	5	7	2
8	5	9	5
8	5	11	9
8	5	13	14
8	5	17	10
8	5	19	16
8	5	21	2
8	7	3	4
8	7	5	6
8	7	9	7
8	7	11	6
8	7	13	4
8	7	15	16
8	7	17	14
8	7	19	11
8	9	5	2
8	9	7	5
8	9	11	3
8	9	13	7
8	9	17	18
8	9	19	6
8	11	3	2
8	11	5	3
8	11	7	3
8	11	9	2
8	11	13	10
8	11	15	8
8	11	17	5
8	11	19	20
8	11	21	17
8	13	3	4
8	13	5	4
8	13	7	8
8	13	9	4
8	13	11	8
8	13	15	4
8	13	17	9
8	13	19	15
8	15	7	6
8	15	11	5
8	15	13	3
8	15	17	13
8	15	19	10
8	17	3	2
8	17	5	6
8	17	7	4
8	17	9	8
8	17	11	2
8	17	13	6
8	17	15	11
8	17	19	5
8	17	21	11
8	19	3	4
8	19	5	2
8	19	7	2
8	19	9	10
8	19	11	10
8	19	13	9
8	19	15	7
8	19	17	4
8	19	21	16
8	21	5	3
8	21	11	7
8	21	13	12
8	21	17	8
8	21	19	14
9	2	5	2
9	2	7	6
9	2	11	12
9	2	13	7
9	2	17	13
9	2	19	4
9	4	5	4
9	4	7	5
9	4	11	2
9	4	13	14
9	4	17	9
9	4	19	8
9	5	2	3
9	5	4	3
9	5	7	8
9	5	8	3
9	5	11	8
9	5	13	11
9	5	14	15
9	5	16	3
9	5	17	7
9	5	19	10
9	7	2	3
9	7	4	5
9	7	5	2
9	7	8	9
9	7	10	7
9	7	11	9
9	7	13	5
9	7	16	17
9	7	17	3
9	7	19	14
9	7	20	17
9	8	5	3
9	8	7	3
9	8	11	4
9	8	13	2
9	8	17	18
9	8	19	16
9	10	7	2
9	10	11	5
9	10	13	9
9	10	17	14
9	10	19	20
9	11	2	3
9	11	4	5
9	11	5	6
9	11	7	5
9	11	8	5
9	11	10	11
9	11	13	6
9	11	14	5
9	11	16	13
9	11	17	12
9	11	19	3
9	11	20	21
9	13	2	3
9	13	4	3
9	13	5	3
9	13	7	4
9	13	8	3
9	13	10	3
9	13	11	12
9	13	14	11
9	13	16	11
9	13	17	8
9	13	19	7
9	13	20	3
9	14	5	4
9	14	11	7
9	14	13	10
9	14	17	6
9	14	19	9
9	16	5	6
9	16	7	6
9	16	11	8
9	16	13	4
9	16	17	2
9	16	19	13
9	17	2	3
9	17	4	3
9	17	5	2
9	17	7	2
9	17	8	7
9	17	10	7
9	17	11	3
9	17	13	14
9	17	14	9
9	17	16	7
9	17	19	15
9	17	20	7
9	19	2	3
9	19	4	5
9	19	5	4
9	19	7	8
9	19	8	5
9	19	10	9
9	19	11	4
9	19	13	8
9	19	14	15
9	19	16	5
9	19	17	13
9	19	20	9
9	20	7	4
9	20	11	10
9	20	13	5
9	20	17	11
9	20	19	2
10	3	7	6
10	3	11	3
10	3	13	14
10	3	17	15
10	3	19	13
10	7	3	2
10	7	9	2
10	7	11	7
10	7	13	11
10	7	17	18
10	7	19	5
10	9	7	4
10	9	11	9
10	9	13	3
10	9	17	11
10	9	19	20
10	11	3	4
10	11	7	8
10	11	9	7
10	11	13	8
10	11	17	4
10	11	19	16
10	13	3	2
10	13	7	5
10	13	9	5
10	13	11	2
10	13	17	14
10	13	19	12
10	13	21	5
10	17	3	4
10	17	7	6
10	17	9	10
10	17	11	6
10	17	13	10
10	17	19	4
10	17	21	13
10	19	3	2
10	19	7	3
10	19	9	8
10	19	11	8
10	19	13	2
10	19	17	10
10	19	21	17
10	21	11	10
10	21	13	7
10	21	17	3
10	21	19	15
11	2	3	2
11	2	5	3
11	2	7	3
11	2	9	8
11	2	13	14
11	2	15	8
11	2	17	6
11	2	19	5
11	2	21	17
11	3	2	3
11	3	4	3
11	3	5	2
11	3	7	8
11	3	8	7
11	3	10	7
11	3	13	8
11	3	14	15
11	3	16	7
11	3	17	9
11	3	19	17
11	3	20	7
11	4	3	4
11	4	5	6
11	4	7	6
11	4	9	7
11	4	13	2
11	4	15	16
11	4	17	12
11	4	19	10
11	4	21	13
11	5	2	3
11	5	3	2
11	5	4	5
11	5	6	5
11	5	7	4
11	5	8	9
11	5	9	2
11	5	12	5
11	5	13	9
11	5	14	11
11	5	16	17
11	5	17	15
11	5	18	11
11	5	19	3
11	5	21	11
11	6	5	4
11	6	7	2
11	6	13	3
11	6	17	18
11	6	19	15
11	7	2	3
11	7	3	4
11	7	4	3
11	7	5	3
11	7	6	7
11	7	8	3
11	7	9	10
11	7	10	3
11	7	12	7
11	7	13	10
11	7	15	13
11	7	16	11
11	7	17	4
11	7	18	19
11	7	19	8
11	7	20	3
11	8	3	2
11	8	5	2
11	8	7	5
11	8	9	5
11	8	13	4
11	8	15	2
11	8	17	7
11	8	19	20
11	8	21	5
11	9	2	3
11	9	4	5
11	9	5	6
11	9	7	3
11	9	8	5
11	9	10	11
11	9	13	11
11	9	14	3
11	9	16	5
11	9	17	10
11	9	19	13
11	9	20	21
11	10	3	4
11	10	7	8
11	10	9	4
11	10	13	5
11	10	17	13
11	10	19	6
11	12	5	3
11	12	7	4
11	12	13	6
11	12	17	2
11	12	19	11
11	13	2	3
11	13	3	4
11	13	4	5
11	13	5	2
11	13	6	7
11	13	7	2
11	13	8	9
11	13	9	7
11	13	10	7
11	13	12	13
11	13	14	9
11	13	15	7
11	13	16	9
11	13	17	5
11	13	18	7
11	13	19	4
11	13	20	17
11	13	21	16
11	14	3	2
11	14	5	6
11	14	9	2
11	14	13	7
11	14	15	11
11	14	17	8
11	14	19	16
11	15	2	3
11	15	4	3
11	15	7	5
11	15	8	3
11	15	13	14
11	15	14	5
11	15	16	3
11	15	17	11
11	15	19	9
11	16	3	4
11	16	5	4
11	16	7	3
11	16	9	10
11	16	13	8
11	16	15	4
11	16	17	14
11	16	19	2
11	16	21	10
11	17	2	3
11	17	3	2
11	17	4	5
11	17	5	3
11	17	6	5
11	17	7	8
11	17	8	5
11	17	9	5
11	17	10	3
11	17	12	5
11	17	13	2
11	17	14	15
11	17	15	8
11	17	16	13
11	17	18	5
11	17	19	14
11	17	20	13
11	17	21	8
11	18	5	2
11	18	7	6
11	18	13	9
11	18	17	3
11	18	19	7
11	19	2	3
11	19	3	4
11	19	4	3
11	19	5	6
11	19	6	7
11	19	7	4
11	19	8	7
11	19	9	4
11	19	10	11
11	19	12	7
11	19	13	3
11	19	14	11
11	19	15	16
11	19	16	7
11	19	17	6
11	19	18	13
11	19	20	11
11	19	21	4
11	20	3	2
11	20	7	2
11	20	9	8
11	20	13	10
11	20	17	9
11	20	19	12
11	20	21	2
11	21	2	3
11	21	4	5
11	21	5	4
11	21	8	9
11	21	10	9
11	21	13	4
11	21	16	17
11	21	17	12
11	21	19	5
11	21	20	9
12	5	7	6
12	5	11	6
12	5	13	5
12	5	17	18
12	5	19	17
12	7	5	4
12	7	11	4
12	7	13	7
12	7	17	15
12	7	19	20
12	11	5	2
12	11	7	2
12	11	13	11
12	11	17	9
12	11	19	7
12	13	5	6
12	13	7	3
12	13	11	9
12	13	17	6
12	13	19	10
12	17	5	4
12	17	7	5
12	17	11	5
12	17	13	4
12	17	19	16
12	19	5	3
12	19	7	6
12	19	11	3
12	19	13	6
12	19	17	14
13	2	3	4
13	2	5	6
13	2	7	2
13	2	9	4
13	2	11	10
13	2	15	16
13	2	17	9
13	2	19	13
13	2	21	16
13	3	2	3
13	3	4	5
13	3	5	4
13	3	7	3
13	3	8	9
13	3	10	9
13	3	11	4
13	3	14	3
13	3	16	17
13	3	17	5
13	3	19	10
13	3	20	9
13	4	3	2
13	4	5	2
13	4	7	4
13	4	9	8
13	4	11	9
13	4	15	2
13	4	17	18
13	4	19	7
13	4	21	11
13	5	2	3
13	5	3	4
13	5	4	3
13	5	6	7
13	5	7	5
13	5	8	7
13	5	9	10
13	5	11	3
13	5	12	7
13	5	14	5
13	5	16	7
13	5	17	14
13	5	18	19
13	5	19	4
13	5	21	19
13	6	5	3
13	6	7	6
13	6	11	8
13	6	17	10
13	6	19	20
13	7	2	3
13	7	3	2
13	7	4	5
13	7	5	6
13	7	6	5
13	7	8	5
13	7	9	5
13	7	10	11
13	7	11	2
13	7	12	5
13	7	15	11
13	7	16	13
13	7	17	6
13	7	18	5
13	7	19	17
13	7	20	21
13	8	3	4
13	8	5	4
13	8	7	8
13	8	9	7
13	8	11	7
13	8	15	4
13	8	17	2
13	8	19	14
13	9	2	3
13	9	4	3
13	9	5	2
13	9	7	2
13	9	8	3
13	9	10	7
13	9	11	12
13	9	14	9
13	9	16	3
13	9	17	15
13	9	19	11
13	9	20	7
13	10	3	2
13	10	7	3
13	10	9	2
13	10	11	6
13	10	17	11
13	10	19	8
13	10	21	17
13	11	2	3
13	11	3	4
13	11	4	5
13	11	5	3
13	11	6	7
13	11	7	4
13	11	8	9
13	11	9	4
13	11	10	3
13	11	12	13
13	11	14	11
13	11	15	13
13	11	16	9
13	11	17	7
13	11	18	13
13	11	19	5
13	11	20	13
13	11	21	4
13	12	5	6
13	12	7	5
13	12	11	5
13	12	17	3
13	12	19	2
13	14	3	4
13	14	5	2
13	14	9	10
13	14	11	4
13	14	15	7
13	14	17	12
13	14	19	15
13	15	2	3
13	15	4	5
13	15	7	8
13	15	8	5
13	15	11	9
13	15	14	15
13	15	16	5
13	15	17	8
13	15	19	12
13	16	3	2
13	16	5	3
13	16	7	2
13	16	9	5
13	16	11	3
13	16	15	8
13	16	17	4
13	16	19	9
13	16	21	2
13	17	2	3
13	17	3	4
13	17	4	3
13	17	5	6
13	17	6	7
13	17	7	3
13	17	8	3
13	17	9	7
13	17	10	11
13	17	11	8
13	17	12	7
13	17	14	3
13	17	15	16
13	17	16	11
13	17	18	7
13	17	19	6
13	17	20	11
13	17	21	10
13	18	5	4
13	18	7	4
13	18	11	2
13	18	17	13
13	18	19	3
13	19	2	3
13	19	3	2
13	19	4	5
13	19	5	2
13	19	6	5
13	19	7	5
13	19	8	9
13	19	9	2
13	19	10	7
13	19	11	7
13	19	12	5
13	19	14	5
13	19	15	2
13	19	16	17
13	19	17	9
13	19	18	11
13	19	20	17
13	19	21	5
13	20	3	4
13	20	7	6
13	20	9	4
13	20	11	12
13	20	17	5
13	20	19	16
13	20	21	13
13	21	2	3
13	21	4	3
13	21	5	3
13	21	8	7
13	21	10	3
13	21	11	6
13	21	16	7
13	21	17	18
13	21	19	13
13	21	20	3
14	3	5	3
14	3	11	10
14	3	13	10
14	3	17	18
14	3	19	12
14	5	3	2
14	5	9	8
14	5	11	2
14	5	13	8
14	5	17	13
14	5	19	20
14	9	5	4
14	9	11	8
14	9	13	4
14	9	17	3
14	9	19	17
14	11	3	2
14	11	5	6
14	11	9	5
14	11	13	2
14	11	15	11
14	11	17	15
14	11	19	6
14	13	3	4
14	13	5	3
14	13	9	10
14	13	11	3
14	13	15	13
14	13	17	10
14	13	19	14
14	15	11	6
14	15	13	11
14	15	17	5
14	15	19	3
14	17	3	2
14	17	5	2
14	17	9	2
14	17	11	9
14	17	13	9
14	17	15	2
14	17	19	11
14	19	3	4
14	19	5	4
14	19	9	7
14	19	11	12
14	19	13	7
14	19	15	4
14	19	17	12
15	2	7	5
15	2	11	5
15	2	13	12
15	2	17	18
15	2	19	10
15	4	7	3
15	4	11	10
15	4	13	11
15	4	17	2
15	4	19	20
15	7	2	3
15	7	4	3
15	7	8	7
15	7	11	12
15	7	13	3
15	7	16	7
15	7	17	12
15	7	19	16
15	8	7	6
15	8	11	9
15	8	13	9
15	8	17	4
15	8	19	2
15	11	2	3
15	11	4	3
15	11	7	3
15	11	8	3
15	11	13	14
15	11	14	3
15	11	16	11
15	11	17	14
15	11	19	17
15	13	2	3
15	13	4	5
15	13	7	8
15	13	8	5
15	13	11	5
15	13	14	15
15	13	16	13
15	13	17	15
15	13	19	8
15	14	11	2
15	14	13	6
15	14	17	7
15	14	19	13
15	16	7	5
15	16	11	7
15	16	13	5
15	16	17	8
15	16	19	4
15	17	2	3
15	17	4	5
15	17	7	4
15	17	8	9
15	17	11	4
15	17	13	11
15	17	14	11
15	17	16	17
15	17	19	9
15	19	2	3
15	19	4	3
15	19	7	2
15	19	8	3
15	19	11	9
15	19	13	10
15	19	14	9
15	19	16	3
15	19	17	18
16	3	5	2
16	3	7	2
16	3	11	6
16	3	13	12
16	3	17	3
16	3	19	20
16	5	3	4
16	5	7	8
16	5	9	7
16	5	11	10
16	5	13	7
16	5	17	5
16	5	19	8
16	7	3	2
16	7	5	3
16	7	9	8
16	7	11	3
16	7	13	2
16	7	15	8
16	7	17	7
16	7	19	15
16	9	5	6
16	9	7	6
16	9	11	7
16	9	13	10
16	9	17	9
16	9	19	3
16	11	3	4
16	11	5	4
16	11	7	5
16	11	9	10
16	11	13	5
16	11	15	4
16	11	17	11
16	11	19	10
16	11	21	19
16	13	3	2
16	13	5	2
16	13	7	4
16	13	9	2
16	13	11	4
16	13	15	2
16	13	17	13
16	13	19	17
16	13	21	11
16	15	7	3
16	15	11	8
16	15	13	8
16	15	17	15
16	15	19	5
16	17	3	4
16	17	5	3
16	17	7	2
16	17	9	4
16	17	11	12
16	17	13	3
16	17	15	13
16	17	19	12
16	17	21	16
16	19	3	2
16	19	5	6
16	19	7	8
16	19	9	5
16	19	11	5
16	19	13	11
16	19	15	11
16	19	17	2
16	19	21	8
16	21	5	4
16	21	11	9
16	21	13	6
16	21	17	4
16	21	19	7
17	2	3	2
17	2	5	4
17	2	7	4
17	2	9	2
17	2	11	7
17	2	13	6
17	2	15	14
17	2	19	20
17	2	21	11
17	3	2	3
17	3	4	5
17	3	5	6
17	3	7	6
17	3	8	5
17	3	10	11
17	3	11	5
17	3	13	9
17	3	14	13
17	3	16	13
17	3	19	11
17	3	20	21
17	4	3	4
17	4	5	3
17	4	7	8
17	4	9	4
17	4	11	3
17	4	13	12
17	4	15	13
17	4	19	2
17	5	2	3
17	5	3	2
17	5	4	3
17	5	6	5
17	5	7	3
17	5	8	3
17	5	9	5
17	5	11	12
17	5	12	11
17	5	13	2
17	5	14	3
17	5	16	11
17	5	18	5
17	5	19	12
17	5	21	17
17	6	5	2
17	6	7	5
17	6	11	10
17	6	13	5
17	6	19	3
17	7	2	3
17	7	3	4
17	7	4	5
17	7	5	4
17	7	6	7
17	7	8	9
17	7	9	7
17	7	10	9
17	7	11	8
17	7	12	13
17	7	13	8
17	7	15	4
17	7	16	9
17	7	18	7
17	7	19	13
17	7	20	9
17	8	3	2
17	8	5	6
17	8	7	2
17	8	9	8
17	8	11	6
17	8	13	11
17	8	15	11
17	8	19	4
17	8	21	2
17	9	2	3
17	9	4	3
17	9	5	3
17	9	7	4
17	9	8	7
17	9	10	3
17	9	11	4
17	9	13	14
17	9	14	11
17	9	16	7
17	9	19	14
17	9	20	3
17	10	3	4
17	10	7	6
17	10	9	10
17	10	11	2
17	10	13	4
17	10	19	5
17	10	21	13
17	11	2	3
17	11	3	2
17	11	4	5
17	11	5	2
17	11	6	5
17	11	7	8
17	11	8	5
17	11	9	2
17	11	10	7
17	11	12	5
17	11	13	7
17	11	14	15
17	11	15	2
17	11	16	5
17	11	18	11
17	11	19	15
17	11	20	17
17	11	21	8
17	12	5	4
17	12	7	3
17	12	11	9
17	12	13	10
17	12	19	6
17	13	2	3
17	13	3	4
17	13	4	3
17	13	5	6
17	13	6	7
17	13	7	5
17	13	8	3
17	13	9	4
17	13	10	11
17	13	11	7
17	13	12	7
17	13	14	5
17	13	15	16
17	13	16	3
17	13	18	13
17	13	19	16
17	13	20	11
17	13	21	19
17	14	3	2
17	14	5	3
17	14	9	5
17	14	11	5
17	14	13	3
17	14	15	8
17	14	19	7
17	15	2	3
17	15	4	5
17	15	7	2
17	15	8	9
17	15	11	3
17	15	13	6
17	15	14	9
17	15	16	17
17	15	19	17
17	16	3	4
17	16	5	2
17	16	7	4
17	16	9	7
17	16	11	12
17	16	13	9
17	16	15	7
17	16	19	8
17	16	21	4
17	18	5	6
17	18	7	8
17	18	11	8
17	18	13	2
17	18	19	9
17	19	2	3
17	19	3	4
17	19	4	5
17	19	5	3
17	19	6	7
17	19	7	3
17	19	8	5
17	19	9	10
17	19	10	3
17	19	11	6
17	19	12	13
17	19	13	5
17	19	14	3
17	19	15	13
17	19	16	13
17	19	18	19
17	19	20	13
17	19	21	10
17	20	3	2
17	20	7	5
17	20	9	2
17	20	11	4
17	20	13	8
17	20	19	10
17	20	21	5
17	21	2	3
17	21	4	3
17	21	5	2
17	21	8	3
17	21	10	7
17	21	11	2
17	21	13	11
17	21	16	11
17	21	19	20
17	21	20	7
18	5	7	4
18	5	11	4
18	5	13	12
18	5	17	12
18	5	19	5
18	7	5	6
18	7	11	10
18	7	13	9
18	7	17	10
18	7	19	7
18	11	5	3
18	11	7	6
18	11	13	3
18	11	17	6
18	11	19	11
18	13	5	4
18	13	7	2
18	13	11	6
18	13	17	4
18	13	19	13
18	17	5	6
18	17	7	8
18	17	11	7
18	17	13	7
18	17	19	17
18	19	5	2
18	19	7	4
18	19	11	2
18	19	13	4
18	19	17	15
19	2	3	4
19	2	5	2
19	2	7	8
19	2	9	7
19	2	11	8
19	2	13	4
19	2	15	7
19	2	17	16
19	3	2	3
19	3	4	3
19	3	5	3
19	3	7	5
19	3	8	7
19	3	10	3
19	3	11	12
19	3	13	6
19	3	14	5
19	3	16	15
19	3	17	7
19	3	20	3
19	4	3	2
19	4	5	4
19	4	7	2
19	4	9	5
19	4	11	5
19	4	13	8
19	4	15	14
19	4	17	15
19	4	21	2
19	5	2	3
19	5	3	4
19	5	4	5
19	5	6	7
19	5	7	6
19	5	8	9
19	5	9	4
19	5	11	9
19	5	12	13
19	5	13	10
19	5	14	13
19	5	16	9
19	5	17	6
19	5	18	13
19	5	21	13
19	6	5	6
19	6	7	3
19	6	11	2
19	6	13	12
19	6	17	14
19	7	2	3
19	7	3	2
19	7	4	3
19	7	5	2
19	7	6	5
19	7	8	3
19	7	9	2
19	7	10	7
19	7	11	6
19	7	12	11
19	7	13	14
19	7	15	2
19	7	16	3
19	7	17	5
19	7	18	11
19	7	20	7
19	8	3	4
19	8	5	3
19	8	7	4
19	8	9	10
19	8	11	10
19	8	13	3
19	8	15	13
19	8	17	13
19	8	21	4
19	9	2	3
19	9	4	5
19	9	5	4
19	9	7	8
19	9	8	5
19	9	10	9
19	9	11	3
19	9	13	5
19	9	14	15
19	9	16	13
19	9	17	4
19	9	20	9
19	10	3	2
19	10	7	5
19	10	9	8
19	10	11	7
19	10	13	7
19	10	17	12
19	10	21	5
19	11	2	3
19	11	3	4
19	11	4	3
19	11	5	6
19	11	6	7
19	11	7	2
19	11	8	7
19	11	9	7
19	11	10	11
19	11	12	7
19	11	13	9
19	11	14	9
19	11	15	16
19	11	16	7
19	11	17	3
19	11	18	7
19	11	20	11
19	11	21	16
19	12	5	2
19	12	7	6
19	12	11	4
19	12	13	11
19	12	17	11
19	13	2	3
19	13	3	2
19	13	4	5
19	13	5	3
19	13	6	5
19	13	7	3
19	13	8	9
19	13	9	5
19	13	10	3
19	13	11	8
19	13	12	5
19	13	14	3
19	13	15	8
19	13	16	17
19	13	17	2
19	13	18	5
19	13	20	13
19	13	21	17
19	14	3	4
19	14	5	4
19	14	9	4
19	14	11	12
19	14	13	2
19	14	15	4
19	14	17	10
19	15	2	3
19	15	4	3
19	15	7	4
19	15	8	3
19	15	11	5
19	15	13	4
19	15	14	11
19	15	16	11
19	15	17	18
19	16	3	2
19	16	5	6
19	16	7	8
19	16	9	2
19	16	11	9
19	16	13	6
19	16	15	11
19	16	17	9
19	16	21	8
19	17	2	3
19	17	3	4
19	17	4	5
19	17	5	2
19	17	6	7
19	17	7	5
19	17	8	5
19	17	9	10
19	17	10	7
19	17	11	2
19	17	12	13
19	17	13	8
19	17	14	5
19	17	15	7
19	17	16	5
19	17	18	19
19	17	20	17
19	17	21	19
19	18	5	3
19	18	7	2
19	18	11	6
19	18	13	10
19	18	17	8
19	20	3	4
19	20	7	3
19	20	9	7
19	20	11	3
19	20	13	14
19	20	17	7
19	20	21	10
19	21	2	3
19	21	4	5
19	21	5	6
19	21	8	9
19	21	10	11
19	21	11	7
19	21	13	3
19	21	16	9
19	21	17	15
19	21	20	21
20	3	7	3
20	3	11	7
20	3	13	7
20	3	17	16
20	3	19	16
20	7	3	4
20	7	9	10
20	7	11	9
20	7	13	12
20	7	17	9
20	7	19	12
20	9	7	2
20	9	11	10
20	9	13	8
20	9	17	14
20	9	19	10
20	11	3	2
20	11	7	4
20	11	9	8
20	11	13	4
20	11	17	2
20	11	19	8
20	11	21	11
20	13	3	4
20	13	7	6
20	13	9	7
20	13	11	12
20	13	17	7
20	13	19	6
20	13	21	13
20	17	3	2
20	17	7	3
20	17	9	5
20	17	11	3
20	17	13	5
20	17	19	2
20	17	21	17
20	19	3	4
20	19	7	5
20	19	9	4
20	19	11	4
20	19	13	14
20	19	17	5
20	19	21	19
20	21	11	5
20	21	13	10
20	21	17	10
20	21	19	17
21	2	5	3
21	2	11	2
21	2	13	3
21	2	17	8
21	2	19	18
21	4	5	6
21	4	11	4
21	4	13	6
21	4	17	16
21	4	19	17
21	5	2	3
21	5	4	3
21	5	8	7
21	5	11	5
21	5	13	14
21	5	16	15
21	5	17	3
21	5	19	7
21	8	5	2
21	8	11	8
21	8	13	12
21	8	17	15
21	8	19	15
21	10	11	10
21	10	13	2
21	10	17	6
21	10	19	14
21	11	2	3
21	11	4	5
21	11	5	4
21	11	8	9
21	11	10	9
21	11	13	10
21	11	16	17
21	11	17	10
21	11	19	4
21	11	20	9
21	13	2	3
21	13	4	3
21	13	5	2
21	13	8	7
21	13	10	7
21	13	11	2
21	13	16	7
21	13	17	18
21	13	19	3
21	13	20	7
21	16	5	4
21	16	11	5
21	16	13	11
21	16	17	13
21	16	19	11
21	17	2	3
21	17	4	3
21	17	5	3
21	17	8	3
21	17	10	3
21	17	11	6
21	17	13	6
21	17	16	3
21	17	19	20
21	17	20	3
21	19	2	3
21	19	4	5
21	19	5	6
21	19	8	9
21	19	10	11
21	19	11	8
21	19	13	9
21	19	16	9
21	19	17	8
21	19	20	21
21	20	11	9
21	20	13	4
21	20	17	12
21	20	19	9

Open in new window

0
 
InteractiveMindAuthor Commented:
Indeed. Unfortunately though, these numbers could be very large so I require a deterministic approach.
0
 
InteractiveMindAuthor Commented:
Ahh! It just occurred to me. There exists an s such that

at+b = sc

or

at - sc = -b

which is a standard linear Diophantine equation:
http://mathworld.wolfram.com/DiophantineEquation.html
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
GwynforWebCommented:
I just did it. (wasted my time?, gah)

A, B & C relatively prime

Find

Ax + B = 0  mod C

Using Euclids algorithm since A & C coprime then there is m & n st

 mA + nC = 1

Multiplying both sides by B

 (mB)A + (nB)C = B

 (-mB)A + B = (nB)C

 (-mB)A + B = 0  mod C

 (-mB mod C)A + B = 0  mod C

eg

5x + 7 = 0 mod 9

By Euclid

2*5  - 9 = 1

14* 5 - 63  = 7

(-14)* 5 + 7  = 0  mod 9

(-14 mod 9)* 5 + 7  = 0  mod 9

4*5 + 7 = 0 mod 9

x = 4
0
 
InteractiveMindAuthor Commented:
I solved it.
0
 
InteractiveMindAuthor Commented:
Gwynfor, I only just saw your solution now by chance. My points-bag is empty but thank you for the effort.
0

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

  • 4
Tackle projects and never again get stuck behind a technical roadblock.
Join Now