# Solve the set of congruences 2x -= 1(mod 5) x -= 3(mod 4)

Question
Congruence
Solve the set of congruences
$$\displaystyle{2}{x}\equiv{1}{\left(\text{mod}{5}\right)}$$
$$\displaystyle{x}\equiv{3}{\left(\text{mod}{4}\right)}$$

2021-03-08
Step 1
Here, we have to solve for congruences
2x=1 mod 5
x=3 mod 4
To solve such questions, we apply chinese remainder theorem.
Chinese Remainder Theorem- Let m, n are relatively prime integers. Then the system of simultaneous congruences $$\displaystyle{x}\equiv{a}_{{1}}{\left(\text{mod}{m}\right)}{x}\equiv{a}_{{2}}{\left(\text{mod}{n}\right)}$$ has a unique solution modulo M = mxn, for any given integers $$\displaystyle{a}_{{1}},{a}_{{2}}$$.
Step 2
$$\displaystyle{2}{x}={1}\text{mod}{5}\Rightarrow{2}\times{3}={3}\text{mod}{5}\Rightarrow{x}={3}\text{mod}{5}$$
and we have x = 3 mod 4
Here, 4 and 5 are co-prime, therefore By chinese remainder theorem, it has unique solution module 20.
So, only possibilty is x=23 which satisfy the given congruences.
Step 3
x=23

### Relevant Questions

To determine: The smallest nonnegative integer x that satisfies the given system of congruences.
$$\displaystyle{x}\equiv{3}\pm{o}{d}{\left\lbrace{1917}\right\rbrace}$$
$$\displaystyle{x}\equiv{75}\pm{o}{d}{\left\lbrace{385}\right\rbrace}$$
To determine: The smallest nonnegative integer x that satisfies the given system of congruences.
$$\displaystyle{x}\equiv{3}\pm{o}{d}{5}$$
$$\displaystyle{x}\equiv{7}\pm{o}{d}{8}$$
To determine: The smallest nonnegative integer x that satisfies the given system of congruences.
$$\displaystyle{x}\equiv{3}\pm{o}{d}{5}$$
$$\displaystyle{x}\equiv{3}\pm{o}{d}{7}$$
To determine: The smallest nonnegative integer x that satisfies the given system of congruences.
$$\displaystyle{x}\equiv{1}\pm{o}{d}{\left\lbrace{4}\right\rbrace}$$
$$\displaystyle{x}\equiv{8}\pm{o}{d}{\left\lbrace{9}\right\rbrace}$$
$$\displaystyle{x}\equiv{10}\pm{o}{d}{\left\lbrace{25}\right\rbrace}$$
To determine: The smallest nonnegative integer x that satisfies the given system of congruences.
$$\displaystyle{x}\equiv{1}\pm{o}{d}{4}$$
$$\displaystyle{x}\equiv{8}\pm{o}{d}{9}$$
To determine: The smallest nonnegative integer x that satisfies the given system of congruences.
$$\displaystyle{x}\equiv{1003}\pm{o}{d}{\left\lbrace{17},{369}\right\rbrace}$$
$$\displaystyle{x}\equiv{2974}\pm{o}{d}{\left\lbrace{5472}\right\rbrace}$$
To determine: The smallest nonnegative integer x that satisfies the given system of congruences.
$$\displaystyle{x}\equiv{6}\pm{o}{d}{8}$$
$$\displaystyle{x}\equiv{17}\pm{o}{d}{\left\lbrace{25}\right\rbrace}$$
Solve the system of congruence's
$$\displaystyle{x}\equiv{1}{\left(\text{mod}{3}\right)},{x}\equiv{4}{\left(\text{mod}{5}\right)},{x}\equiv{6}{\left(\text{mod}{7}\right)}$$
Find all solutions to the following system of linear congruences: $$\displaystyle{x}\equiv{1}\text{mod}{2},{x}\equiv{2}\text{mod}{3},{x}\equiv{3}\text{mod}{5},{x}\equiv{4}\text{mod}{7},{x}\equiv{5}\text{mod}{11}$$.
Use the construction in the proof of the Chinese remainder theorem to find all solutions to the system of congruences $$\displaystyle{x}\equiv{2}{\left(\text{mod}{3}\right)},{x}\equiv{1}{\left(\text{mod}{4}\right)},{\quad\text{and}\quad}{x}\equiv{3}{\left(\text{mod}{5}\right)}$$.