I’ve recently been learning about modulo calculations and methods like the “Chinese remainder theorem” for solving systems of congruences.
Now it strikes me that all methods to solve systems of congruences are developed in such a way that they only work when the divisor is known.
Now I was wondering if there are also methods to solve systems of congruences when the divisor is unknown, for example;
7 mod A = 2
9 mod A = 4
I know the answer to this question is 5, but I only know this by testing different values. If this is solvable, is it also possible to solve equations where even the rest is unknown?
for example: 7 mod B = B-2
Again I know that there are different solutions here (namely 3 and 9) but again I got this by trying out different values.
In other words, is there a general solution method for the two problems above?
Answer
If a mod b = c, then a = c + nb (with n>= 0, n natural number)
So 7 mod A = 2 –> 7 = 2 + n A –> 5 = n A
Since the prime factorization of 5 = 5 and A > 1 it follows that n=1 and A=5
Analogous for 9 mod A = 4 –> 5 = n A –> n=1 and A=5
7 mod B = B-2 –> 7 = B-2 + nB –> 9 = (n+1) B
Since the prime factorization of 9 = 3 . 3 and B > 1 it follows that
B=3 and n=2
or
B=9 and n=0
Greetings,
Veerle
Answered by
Veerle Ungenae
Informatics – Software development – Web
Jozef Kluyskensstraat 2 B-9000 Ghent
http://www.hogent.be/
.