Mathematics

 In Theorem we saw that if $a \equiv b ~(mod ~n)$, then $c \cdot a \equiv c \cdot b ~(mod ~n)$ for any integer $c$. What about converse $?$ i.e. if $c \cdot a \equiv c \cdot b ~(mod ~n)$ for any integer $c$ does it implies  $a \equiv b ~(mod ~n) ~ ?$  we give answer to this question as No. Here is an example $2 \cdot 4  \equiv 2 \cdot 1 ~(mod~6)$, but $4 \not\equiv 1 ~(mod ~6)$. In brief: One cannot unrestrictedly cancel a common factor in the arithmetic of congruences.  Theorem:   If $c \cdot a \equiv c \cdot b ~(mod ~n)$, then $a \equiv b ~(mod ~\frac{n}{d} )$, where $d = gcd(c, n)$.  Proof:   Suppose that $c \cdot a \equiv c \cdot b ~(mod ~n)$. Therefore by definition of congruences $c \cdot a ~-~ c \cdot b = n \cdot k$ for some integer $k$. Since  $gcd(c, n) = d$, there exist relatively prime integers $r$ and $s$ such that  $c = d \cdot r,~ n = d \cdot s$. We put $c = d \cdot r,~ n = d \cdot s$ in $c \cdot a - c \cdot b = n \cdo...

  Example:   Determine all solutions in the integers of the Diophantine equation $56x + 72y = 40$. Proof:  Firstly, we will find $gcd(56,72)$ using Euclidean Algorithm. We use Euclidean Algorithm and we find that $72 = 56 ~\cdot~ 1 + 16$ $56 = 16 ~\cdot~ 3 + 8$ $16 = 8 ~\cdot~ 2 + 0$ $8$ is the least nonzero remainder obtained in this Algorithm, so $gcd(56,72) = 8$. Since $8 ~ | ~ 40$,  a solution to this equation exists. To obtain  the integer $8$ as a linear combination of $56$ and $72$, we work backward through the previous calculations, as follows:  $8 = 56 - 16 ~\cdot~ 3$ $8 = 56 - (72 - 56 ~\cdot~ 1) ~\cdot~ 3$ $8 = 56 - 72 ~\cdot~ 3 + 56 ~\cdot~ 3$ $8 = 56 ~\cdot~ 4 - 72 ~\cdot~ 3$ $8 = 56 ~\cdot~ 4 + 72 ~\cdot~ (-3)$ We multiply both side of above equation by $5$. Hence we will get  $40 = 56 ~\cdot~ 20 + 72 ~\cdot~ (-15)$ so that $x = 20$ and $ y = - 15$ is a one so...

 Definition:  An equation in one or more variables is said to be a Diophantine equation if it has integer  solution. Example:  Consider the linear equation  $2 x + 8 y = 16$. Linear equation $2 x + 8 y = 16$ has $x = 4, y = 1$ as a integers solution. Therefore $2 x + 8 y = 16$ is a linear Diophantine equation in two variables $x, y$. The Diophantine equation can have a number of solutions. As $x = 8, y = 0$ and $x = 0, y = 2 $ are also integers solution of equation $2 x + 8 y = 16$. Example:  Consider the linear equation  $5 x + 8 y = 16$. Linear equation $5 x + 8 y = 16$ has no integers solution (Why $?$ (We will see in the following Theorem)). Therefore $5 x + 8 y = 16$ is  not a  Diophantine equation. Theorem: The linear  equation $ax +by = c$ has a integers solution if and only if $d$ divides $c$, where $d = gcd(a,b)$.  Moreover, if $x_{0}, ~y_{0}$ is any particular solution of this equation, then all other solutions are...

Example: Use Euclidean Algorithm to find $gcd(42823,6409) $ and find the values of integer $x$ and $y$ satisfying $gcd(42823,6409) = 42823 \cdot x + 6409 \cdot y$. Answer:  To find  $gcd(42823,6409) $ using Euclidean Algorithm. We have to apply Division Algorithm to integers $42823$ and $6409$. Firstly we divide $42823$ by $6409$. When we divide $42823$ by $6409$, we get $q = 6$ (i.e. $6$ is a quotient) and $r = 4369$ (i.e. $4369$ is a remainder). So we get following system of equations in  Euclidean Algorithm. $42823 = 6409~ \cdot ~6 + 4369$ $6409 = 4369 ~\cdot ~1 + 2040$ $4369 = 2040 ~\cdot ~2 + 289$ $2040 = 289 ~\cdot~ 7 + 17$ $289 = 17 ~\cdot ~17 + 0$ $17$ is the last nonzero remainder obtained in this Algorithm, so  $gcd(42823,6409)  = 17$. From the above equations, putting value of remainder (eliminating remainder i.e. $17, ~289,~2040,~ 4369$) and simplifying we can find value of integers $x$ and $y$ such that $gc...

 Example:   Use the Euclidean Algorithm to find the values of integer $x$ and $y$ satisfying $gcd(24,138) = 24 \cdot x + 138 \cdot y$. Solution:  Firstly, we find $gcd(24,138)$ using Euclidean Algorithm. We apply Division Algorithm to integers $24$ and $138$. Firstly, we divide $138$ by $24$. When we divide $138$ by $24$, we get $q = 5$ (i.e. $5$ is a quotient) and $r = 18$ (i.e. $18$ is a remainder). So we get following system of equations in  Euclidean Algorithm. $138 = 24~ \cdot ~5 + 18$  $24 = 18 ~\cdot~ 1 + 6$ $18 = 6 ~\cdot ~3 + 0$ $6$ is the last nonzero remainder obtained in this Algorithm, \linebreak so  $gcd(24, 138)  = 6$. From the above equations, $gcd(24,138) = 6$ can be written as follows $6 = 24 ~-~ 18 ~\cdot~ 1$ we put $18 = 138 ~-~ 24 ~\cdot~ 5$ in above equation, so we get $6 = 24 ~-~ (138 - 24 ~\cdot~ 5) ~\cdot~ 1$ $6 = 24 ~-~ 138  ~\cdot~ 1 + 24 ~\cdot~ 5 $ $6 = 24...

Example: Find $gcd(56,72) $ using Euclidean Algorithm. Solution:   To find  $gcd(56,72) $ using Euclidean Algorithm. We have to apply Division Algorithm to integers $56$ and $72$. Firstly we divide $72$ by $56$. When we divide $72$ by $56$, we get $q = 1$ (i.e. $1$ is a quotient) and $r = 16$ (i.e. $16$ is a remainder). So we get following system of equations in  Euclidean Algorithm. $72 = 56~ \cdot ~1 + 16$  $56 = 16 ~\cdot~ 3 + 8$ $16 = 8 ~\cdot ~2 + 0$ $8$ is the last nonzero remainder obtained in this Algorithm, so  $gcd(72, 56)  = 8$.

  Let $a$ and $b$ be two integers, not both of them are zero. Then  Euclidean  Algorithm to find  greatest common divisor of $a$ and $b$ is as follows. Since $gcd(|a|,|b|) = gcd(a,b)$, without loss of generality, assume that $0 < b \leq a$. Step $(1)$ Apply Division Algorithm for integers $a$ and $b$, so there exist integers $q_{1}$ and $r_{1}$ such that  $a = b \cdot  q_{1} + r_{1}$, where $0 \leq r_{1} < b$.   If $r_{1} = 0$, then $b ~|~ a$ and hence $b = gcd(a,b)$. If $r_{1} \not = 0$,  then go to step $(2)$. Step $(2)$ Apply Division Algorithm for integers $b$ and $r_{1}$, so there exist integers $q_2$ and $r_2$ such that  $b = r_{1}  \cdot q_2 + r_2$, where $0 \leq r_2 < r_{1}$.  If $r_2 = 0$, then stop.  If $r_2 \not = 0$, then go to step $(3)$. Step $(3)$ Apply Division Algorithm  for integers $r_{1}$ and $r_2$, so there exist integers $q_3$ and $r_3$ such that  $r_{1} = r_2 \cdot q_3 + ...

  Lemma:  Let $a, ~b, ~q, ~r $ be integers such that $a = b \cdot q +r$, where $0< r < b$, then $gcd(a,b) = gcd(b,r)$.  Proof:  Let $gcd(a,b) = d$. Firstly, we show that $d$ is a common divisor of both $b$ and $r$. Since $gcd(a,b) = d$, $d ~|~ a$ and $d ~|~ b$. Therefore by part $7.$ of Theorem , $d ~|~ (a~ -~ b \cdot q)$, i.e. $d ~|~ r$. Thus, $d$ is a common divisor of both $b$ and $r$. Now, we show that $d$ is greatest among all common divisors of both $b$ and $r$. Let $c$ be  an arbitrary common divisor of $b$ and $r$, then by part $7.$ of Theorem , $c ~|~ (b \cdot q + r)$, i.e. $c ~|~ a$. This implies that  $c$ is a common divisor of $a$ and $b$, so that $c \leq d$. This gives $d$ is greatest among all common divisors of both $b$ and $r$ and so  $gcd(b,r ) = d $.

  Lemma:   If $a ~|~ b \cdot c$, with $ gcd(a, b) = 1$, then $a ~|~ c$. Proof:  Since $gcd(a, b) = 1$, by Theorem , there exist integers $x$ and $y$ such that $a \cdot x + b \cdot y = 1$. Multiplying this equation by $c$, we get  $c = c \cdot 1 = c~(a \cdot x + b \cdot y) = a \cdot c \cdot x + b \cdot c \cdot y$. As $ a ~|~ a \cdot c$ and  $ a ~|~ b \cdot c$, by part $7.$ of Theorem , $d ~|~ (a \cdot c \cdot x + b \cdot c \cdot y)$. Therefore $d ~|~ c$.

Corollary:  If $a ~|~ c$ and $b ~|~ c$, with $gcd(a, b) = 1$, then $a \cdot b ~|~ c$. Proof: Suppose that $a ~|~ c$ and $b ~|~ c$. Therefore there exist integers $r$ and $s$  such that $c = a \cdot r = b \cdot s$. Since $gcd(a, b) = 1$ By Theorem , there exist integers $x$ and $y$ such that $a \cdot x + b \cdot y = 1$. Multiplying this equation by $c$, we get $c = c \cdot 1 = c~(a \cdot x + b \cdot y) = a \cdot c \cdot x + b \cdot c \cdot y$. By putting appropriate value of $c$ on the right-hand side, we get $c = a~(b \cdot s)~x + b~(a \cdot r)~y = a \cdot b~(s \cdot x + r \cdot y)$. Since $s \cdot x+r \cdot y$ is an integer, we get $a \cdot b ~|~ c$. 

Corollary: If $gcd(a, b) = d$, then $gcd(\frac{a}{d}, \frac{b}{d}) = 1$. Proof:  Since $d = gcd(a,b)$, we have  $d ~|~ a$ and $d ~|~ b$. Hence $\frac{a}{d},~ \frac{b}{d}$ are integers. Since $d = gcd(a,b)$, Theorem , there exist integers $x$ and $y$ such that $d = gcd(a, b) = a \cdot x+ b \cdot y$. By dividing both side of this equation by $d$, we get $1 = \frac{a}{d} \cdot x + \frac{b}{d} \cdot y$. By Theorem , $gcd(\frac{a}{d}, \frac{b}{d}) = 1$.

  Definition:  Two integers $a$ and $b$, not both of which are zero, are said to be relatively prime integers   if and only if $gcd(a, b) = 1$.   Theorem:  If $a$ and $b$ are any integers, not both them are zero, then $a$ and $b$ are relatively prime integers if and only if there exist integers $x$ and $y$ such that $a \cdot x +  b \cdot y = 1$. Proof:  Suppose that $a$ and $b$ are relatively prime integers, so that $gcd(a, b) = 1$. By Theorem , there exist integers $x$ and $y$ such that $a \cdot x + b \cdot y = 1$. conversely, suppose that there exist integers $x$ and $y$ such that $a \cdot x + b \cdot y = 1$ and that $d = gcd(a, b )$. Since $d = gcd(a,b)$, we have  $d ~|~ a$ and $d ~|~ b$. By part $7.$ of Theorem ,  $d ~|~ (a  \cdot x + b \cdot y)$ for all integers $x, ~y$. So in particular  $d ~|~  (a \cdot x + b \cdot y) = 1$. Since $d$ is a positive  integer and $d ~|~ 1$,  $d$ must be equal to $1$. Therefor...