Question

Show that if $\mathbf{a}\mathbf{\equiv }\mathbf{b}\mathbf{\left(}\mathbf{modN}\mathbf{\right)}\mathbf{}$and if $\mathbf{M}$ Divides $\mathbf{N}\mathbf{}\mathbf{then}\mathbf{}\mathbf{a}\mathbf{\equiv }\mathbf{b}\mathbf{\left(}\mathbf{modM}\mathbf{\right)}$

Short answer

It is proved that if $\mathrm{a}=\mathrm{b}\left(\mathrm{modN}\right)$and$\mathrm{M}$ divides$\mathrm{N}$ then $\mathrm{a}=\mathrm{b}\left(\mathrm{modM}\right)$.

Step-by-step solution

Introduction

For,

$\mathrm{a}=\mathrm{b}\left(\mathrm{modN}\right)$

And$\mathrm{M}$ divides $\mathrm{N}$.

To prove, $\mathrm{a}=\mathrm{b}\left(\mathrm{modN}\right)$.

To prove a≡b(modM) 

Assume that,

$\mathrm{a}=\mathrm{b}\left(\mathrm{modN}\right)$

Then,

For some $\mathrm{k}\in \mathrm{Z}$,

By using division algorithm,

$\mathrm{a}\mathrm{and}\mathrm{b}$can be defined as,

$\begin{array}{l}\mathrm{a}=\mathrm{nx}+\mathrm{y}\\ \mathrm{b}=\mathrm{nx}\text{'}+\mathrm{y}\text{'}\end{array}$

For$0\le \mathrm{y}$ and$\mathrm{y}\text{'}<\mathrm{n}$.

Then,

$\begin{array}{c}\mathrm{a}=\mathrm{b}+\mathrm{nk}\\ =(\mathrm{nx}\text{'}+\mathrm{y}\text{'})+\mathrm{nk}\\ =\mathrm{n}(\mathrm{x}\text{'}+\mathrm{k})+\mathrm{y}\end{array}$

Comparing the above equations,

$\begin{array}{l}\mathrm{a}=\mathrm{nx}+\mathrm{y}0\le \mathrm{y}<\mathrm{n}\\ \mathrm{a}=\mathrm{n}(\mathrm{x}\text{'}+\mathrm{k})+\mathrm{y}0\le \mathrm{y}\text{'}<\mathrm{n}\end{array}$

After division, $\mathrm{a}\mathrm{and}\mathrm{b}$leaves the same remainder when it is divided by $\mathrm{n}$then,

$\begin{array}{l}\mathrm{a}=\mathrm{nx}+\mathrm{y}\\ \mathrm{b}=\mathrm{nx}\text{'}+\mathrm{y}\text{'}\end{array}$

Subtracting these two equations,

$\mathrm{a}-\mathrm{b}=\mathrm{n}(\mathrm{x}-\mathrm{x}\text{'})$

Thus,

$\mathrm{a}=\mathrm{b}\left(\mathrm{modn}\right)$

Therefore, if$\mathrm{a}=\mathrm{b}\left(\mathrm{modN}\right)$ and$\mathrm{M}$ divides $\mathrm{N}$then $\mathrm{a}=\mathrm{b}\left(\mathrm{modM}\right)$.