+0

# Number Theory

0
132
1

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
+9461
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