Question

Show that $\mathbf{6}\mathbf{x}\mathbf{+}\mathbf{5}\equiv \mathbf{7}\left(\mathrm{mod}3\right)$ has no solutions.[Hint: Exercise 2]

Short answer

The result is proved using proof of contradiction. Substituting$x=1$and$x\mathbf{=}0$in equation (1), it is derived that both the left hand side and the right hand side of the congruence equation have different values, thus, it can be concluded that$x=1$and$x\mathbf{=}0$is not a solution of equation (1).

Thus, our assumption is wrong and it implies that there is no solution of the congruence equation (1).

Step-by-step solution

Define congruence

Congruence: An integer $a$is said to be congruent to$b$modulo$n$, where the number$b$is an integer and$n$is a positive integer, if$n$divides the expression$\left(a-b\right)$.

If congruence equation $6x+5\equiv 7\left(\mathrm{mod}n\right)$ has a solution, then one of the following integers $1,2,3,\mathrm{...},\left(n-1\right)$ is also the solution the solution of the congruence equation. …(*)

Reduce the given congruence equation.

The given congruence relation is

$6x+5\equiv 7\left(\mathrm{mod}3\right)$ …… (1)

That means 7 leaves remainder 1 when divided by 3.

Thus, the congruence equation can be reduced to,

$6x+5\equiv 1\left(\mathrm{mod}3\right)$

Prove the desired result by using contradiction

Assume that the given congruence relation (1) has a solution.

Thus, according to the statement (*), one of the integersormust be the solution of equation (1).

Substitute1 for X in equation (1).

$\begin{array}{l}6\left(1\right)+5\equiv 7\left(\mathrm{mod}\text{3}\right)\\ 6+5\equiv 7\left(\mathrm{mod}\text{3}\right)\\ 11\equiv 7\left(\mathrm{mod}\text{3}\right)\\ 2\left(\mathrm{mod}\text{3}\right)\cancel{\equiv }7\left(\mathrm{mod}\text{3}\right)\end{array}$

Since the result is different from the right-hand side of the congruence equation, thus, it can be concluded that X = 1 is not a solution of equation (1).

Substitute 0 for X in equation (1).

$\begin{array}{c}6\left(1\right)+5\equiv 7\left(\mathrm{mod}\text{3}\right)\\ 6+5\equiv 7\left(\mathrm{mod}\text{3}\right)\\ 11\equiv 7\left(\mathrm{mod}\text{3}\right)\\ 2\left(\mathrm{mod}\text{3}\right)\cancel{\equiv }7\left(\mathrm{mod}\text{3}\right)\end{array}$

Since the result is different from the right-hand side of the congruence equation, thus, it can be concluded that X = 0 is not a solution of equation (1).

Thus, our assumption is wrong and it implies that there is no solution of the congruence equation (1). Hence, the required result is proved.