Question

Find all solutions to the system of congruences
x ≡ 6 (mod 7), and
x ≡ 4 (mod 8)

Answer 1

~ Number Theory

Hi There ! Hope this can help you :

x ≡ 6 (mod 7)

x ≡ 4 (mod 8)

Notice that (7 , 8) = 1 is relatively prime , so we can find integers a and b such that 7a + 8b = 1 . In fact by inspection we find a = -1 and b = 1 since 7(-1) + 8(1) = 1 . We claim :

$x = 6(7)( - 1) + 4(8)(1) = - 10$

is solution to both linear congruence equations. More specifically, we will say, x ≡ -10 (mod 56) is the solution to the system where 56 = (7)(8) . This strategy and the uniqueness is justified in the following the Chinese remainder theorem.

-India -Indonesia