+0  
 
0
85
1
avatar

Find all numbers r for which the system of congruences

x = r (mod 6)

x = 3 (mod 20)

x = 13 (mod 45)

has a solution.

 Apr 16, 2022
 #1
avatar+9459 
0

Since \(x \equiv 3 \pmod{20}\), let x = 20k + 3 for some integer k.

 

\(20k + 3 \equiv 13\pmod{45}\\ 20k \equiv 10 \pmod{45}\\ 4k \equiv 2 \pmod{9}\\ 4k \equiv 20 \pmod{9}\\ k \equiv 5 \pmod 9\)

 

Then we can let k = 9n + 5 for some integer n. Substituting this into x = 20k + 3 gives x = 180n + 103.

Therefore, taking (mod 6), we have:

\(x \equiv 180n + 103\pmod 6\\ x \equiv 103 \pmod 6\\ x \equiv 1 \pmod 6\)

 

It turns out the system has a solution if and only if \(r \equiv 1 \pmod 6\), i.e., \(r = 6p + 1\) for some integer p.

 Apr 16, 2022

5 Online Users

avatar