Prove that 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$.

 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$.

Proof: In last para, we have observed that the given linear congruence $ax \equiv b ~(mod ~n)$ is equivalent to the linear Diophantine equation $ax - ny = b$. From Theorem, The linear  equation $ax - ny = b$   has a integers solution if and only if $d$ divides $b$, where $d = gcd(a,n)$.  Moreover, if $x_{0},~ y_{0}$ is any particular solution of this equation, then all other solutions are 

$x = x_{0} + (\frac{n}{d}) \cdot t$,  $y = y_{0} - (\frac{a}{d}) \cdot t$, where $t$ is an arbitrary integer.

We will take values of $t$ from $0$ to $d-1$, i.e. $t = 0, ~ 1, ~2, ~3, ~ \cdots ~ d-1$, then we will get values of $x$ as follows

$x = x_{0} , ~x = x_{0} + (\frac{n}{d}), ~ x = x_{0} + (\frac{n}{d}) \cdot 2,  ~x = x_{0} + (\frac{n}{d}) \cdot 3, \cdots\cdots,~~x = x_{0} + (\frac{n}{d}) \cdot (d -1 )$

We claim that these integers are incongruent modulo $n$. Suppose on the contrary that there are two integers which are congruent modulo $n$. Say 

$x_{0} + (\frac{n}{d}) \cdot t_{1} \equiv  x_{0} + (\frac{n}{d}) \cdot t_2 ~ (mod~ n)$

where $0 \leq t_1 < t_2 \leq (d - 1)$, then we would have 

$(\frac{n}{d}) \cdot t_{1} \equiv   (\frac{n}{d}) \cdot t_2 ~ (mod~ n)$

Since $gcd(\frac{n}{d}, n) = \frac{n}{d}$ by Theorem  we can cancel the factor n/d  and we will get the congruence $t_{1} \equiv  t_2 ~ (mod~ \frac{n}{\frac{n}{d}})$, i.e. $t_{1} \equiv  t_2 ~ (mod~ d)$.

This gives  that $ d ~|~ t_2 - t_{1}$, But this is impossible in view of the inequality 

$0 < t_{1} - t_2 < d$. 

Now, we show that any other solution $x_{0} + \frac{n}{d} \cdot t$ is congruent modulo $n$ to one of the $d$ integers listed above. We apply the Division Algorithm to $t, ~d$ therefore there exist a  quotient $q$ and  remainder $r$, so we can write $t$ as 

$t = q \cdot d + r$, where $0 \leq r \leq d - 1$. Hence 

$x_{0} + (\frac{n}{d}) \cdot t = x_{0} + (\frac{n}{d}) \cdot (q ~d + r)$ 

$= x_{0} + n \cdot q + (\frac{n}{d}) \cdot r$

$\equiv x_{0} + (\frac{n}{d}) \cdot r ~(mod ~ n) $

with $xo + \frac{n}{d} \cdot r $ being one of our $d$ selected solutions.  This ends the proof. 

Popular posts from this blog

Definition of divisibility and Theorem on divisibility

  Definition: An integer $b$ is said to be divisible by an integer $a \not = 0$, if there exists some integer $c$ such that $ b = a \cdot c$. An integer $b$ is  divisible by an integer $a \not = 0$, is denoted by $a ~|~ b$.  We write $a \nmid b$ to indicate that $b$  is not divisible by $a$. Theorem: For integers $a, ~b, ~c$ the following hold: $1.$ $a ~|~ 0, ~ 1 ~|~ a, ~ a ~|~ a $. $2.$  $ a ~|~ 1 $ if and only if $a =  1$ or $a = -1$. $3.$  If $a ~|~ b$ and $c ~|~ d$, then $a \cdot c ~|~ b \cdot d$. $4.$   If $a ~|~ b$ and $b ~|~ c$, then $a ~|~ c$. $5.$  If $a ~|~ b$ and $b ~|~ a$ if and only if $a =  b$ or $a = -b$. $6.$  If $a ~|~ b$ and $b \not = 0$, then $|a| \leq |b|$. $7.$  If $a ~|~ b$ and $a ~|~ c$, then $a~ |~ (b \cdot x + c \cdot y)$ for arbitrary integers $x$ and $y$. Proof: $1.$ For any integer $a$, we can write $0 = a \cdot 0$, $a = 1 \cdot a$ and $a = a \cdot 1$. Theref...
Read more

The Division Algorithm / Prove that given integers $a$ and $b$, with $b > ~ 0$, there exist unique integers $q$ and $r$ such that $a = b \cdot q +r$, where $0 \leq r < b$. The integer $q$ is called the $\textbf{quotient}$ and the integer $r$ is called $\textbf{remainder}$.

Image
State and prove Division Algorithm theorem.  Theorem:  Given integers $a$ and $b$, with $b > ~ 0$, there exist unique integers $q$ and $r$ such that $a = b \cdot q +r$, where $0 \leq r < b$. The integer $q$ is called the $\textbf{quotient}$ and the integer $r$ is called $\textbf{remainder}$. Proof : Firstly, we will show that the set $S = \{a - x \cdot b \;|\; x \in \mathbb{Z}$ and $  a -x \cdot b \geq 0\}$ is nonempty.  For this purpose, we have to find value of $x$ such that $a -x \cdot b \geq 0$. Given that integer $b > 0$, i.e. $b \geq 1$. Multiply $b \geq 1$ by $|a|$, we get $|a|\cdot b \geq |a|$ and so $a - ( - |a|) \cdot b = a + |a| \cdot b \geq a + |a| \geq 0$. If we take $x = |a|$, then, $a -x \cdot b \in S$. This show that $S$ is nonempty subset of nonnegative integers. By the Well-Ordering Principle (for more details see  Well-Ordering Principle  ) , set $S$ contains a least integer; say it $r$. Since $r \in S$, there exists an i...
Read more

Define Greatest Common Divisor and Prove that if $a$ and $b$ are any integers, not both of them are zero. Then there exist integers $x$ and $y$ such that $gcd(a, b) =a \cdot x + b \cdot y$.

Image
Definition: Let $a$ and $b$ be any integers, with at least one of them is not zero. The greatest common divisor of $a$ and $b$, denoted by $gcd(a, b)$, is the positive integer $d$ satisfying the following: $1.$  $d ~|~ a$ and $d ~|~ b$. $2.$ If $c ~|~ a$ and $c ~|~ b$, then $c \leq d$. Theorem:  If $a$ and $b$ are any integers, not both of them are zero. Then there exist integers $x$ and $y$ such that $gcd(a, b) =a \cdot x + b \cdot y$. Proof:   Let  $a$ and $b$ be any integers, not both of them are zero. Consider the set $S = \{a \cdot u + b \cdot  v \;|\; a \cdot  u + b \cdot  v > 0$ and $ u, v \in \mathbb{Z}\}$, that is  $S$ is the set of all positive linear combinations of $a$ and $b$. Firstly, we will show  that $S$ is nonempty set. We have taken integers $a$ and $b$ such that not both of them are zero. Without loss of generality, suppose that $a \not = 0$. Then the integer $|a| = a \cdot u + b \cdot 0 \in S$ for the v...
Read more