Mathematics

Example: Solve the linear congruence $18x \equiv 30 ~(mod ~42)$.   Answer: Since $gcd(18, 42) = 6$ and $6$ divides $30$, by  Theorem , given linear congruence $18x \equiv 30 ~(mod ~42)$ has $6$ mutually incongruent solutions modulo $42$.  We will find first solution by trial and error method. We will consider simple values of $x$ as $1, ~-1,~ 2,~ -2,~ \cdots $ and check which value satisfy given linear congruence $18x \equiv 30 ~(mod ~42)$. When we take $x = 1, ~-1,~ 2,~ -2,~3, ~ -3$, we observe that $x =1, ~-1,~ 2,~ -2,~3$ are not a solution of $18x \equiv 30 ~(mod ~42)$. Now, we take $x = -3$, we observe that $x = -3$ is  a solution of $18x \equiv 30 ~(mod ~42)$. But $-3 \equiv 39 ~ (mod~ 42)$, So $x_{0} = 39$ is a solution of a given  linear congruence $18x \equiv 30 ~(mod ~42)$.  By Theorem , other solutions of given linear congruence $18x \equiv 30 ~(mod ~42)$  are given by  $x_{1} = 39 + \frac{42}{6} = 39 + 7 = 46 \equiv 4~ (mod ~ 42)$,...

 Example:  Solve the linear congruence $9x \equiv 21 ~(mod ~ 30)$. Answer: Since $gcd(9, 30) = 3$ and $3$ divides $21$, by  Theorem , given linear congruence $9x \equiv 21 ~(mod ~30)$ has $3$ mutually incongruent solutions modulo $30$.  We will find first solution by trial and error method. We will consider simple values of $x$ as $1, ~-1,~ 2,~ -2,~ \cdots $ and check which value satisfy given linear congruence $9x \equiv 21 ~(mod~ 30)$. When we take $x = 1$, we observe that $x =1$ is not a solution of $9x \equiv 21 ~(mod ~30)$. Now, we take $x = - 1$, we observe that $x = - 1$ is  a solution of $9x \equiv 21 ~(mod ~30)$. But $-1 \equiv 29 ~(mod ~30) $, therefore $x_{0} = 29$ is a solution of a given  linear congruence $9x \equiv 21 ~(mod ~30)$.  By Theorem , other solutions of given linear congruence $9x \equiv 21 ~(mod ~30)$  are given by $x_{1} = 29 + \frac{30}{3} = 29 + 10 = 39 \equiv 9~ (mod ~ 30), ~ x_2 = 29 + (\frac{30}{3}) ~2 = 29 + 10 \...

  Definition:   Let $a, ~b,  ~n > 0$ be integers and $x$ be a variable then  an equation of the form $ax \equiv b ~(mod ~n)$  is called a linear congruence, and an integer $x_{0}$ for which $a x_{0} \equiv b ~(mod ~n )$ is called a solution of an equation  $ax \equiv b ~(mod ~n)$.  By definition, $a ~x_{0} \equiv b ~(mod~ n)$ if and only  if $n ~|~ a x_{0} - b $ i.e. $a x_{0} - b = n y_{0} $ for some integer $y_{0}$· Thus, the problem of finding all integers that will satisfy the linear congruence $a x \equiv b ~(mod ~n)$ is identical with that of obtaining all solutions of the linear Diophantine equation $ax - ny = b$. Theorem:   The linear congruence $ax \equiv b ~(mod ~n)$ has a solution if and only if $d ~|~ b$, where $d = gcd(a, n)$. If $d ~|~ b$, then it has $d$ mutually incongruent solutions modulo $n$. P roof: In last para, we have observed that the given linear congruence $ax \equiv b ~(mod ~n)$ is equivalent to the linea...