Question

Is the difference of ${\mathbf{5}}^{\mathbf{30}\mathbf{,}\mathbf{000}}\mathbf{}\mathbf{and}\mathbf{}{\mathbf{6}}^{\mathbf{123}\mathbf{,}\mathbf{456}}$a multiple of$\mathbf{31}$ ?

Short answer

The difference of$5^{30,000}\mathrm{and}{6}^{123,456}$ a multiple of 31 is 0, i.e. it is multiple of $31$.

Step-by-step solution

Fermat’s Little Theorem

Fermat’s Little Theorem can be used as to calculate the power of the given integers with the help of modulo of prime numbers.

i.e.

${\mathrm{x}}^{\mathrm{n}}–\mathrm{x}$ is divisible by$\mathrm{n}$ .

where,

$\mathrm{x}=$any integer

$\mathrm{n}=$prime number.

Calculation for 530,000

As$31$ is a prime number, that can be written as $30+1$.

Then,

For $5^{30,000},30000$can be divisible by$30$ .

So ,$5^{30,000}\mathrm{mod}31$ is 1.

Calculation for 6123,456

Here,$123456$is not divisible by $30$.

Then,

$123456\mathrm{as}123450+6\mathrm{and}123450\mathrm{is}\mathrm{divisible}\mathrm{by}30.$

So,

$\begin{array}{c}{6}^{123,456}\mathrm{mod}31=6^{123,450}*6^6\left(\mathrm{mod}31\right)\\ =6^6\left(\mathrm{mod}31\right)\\ =36*36*36\left(\mathrm{mod}31\right)\end{array}$

By dividing$36\mathrm{by}31$ , the remainder will be$5$ .

Then,

$\begin{array}{c}5*5*5\mathrm{mod}31=125\mathrm{mod}31\\ =1\end{array}$

Therefore, by subtracting the final answers of step$2$ and step$3$ we get the answer equal to $0$. So, the difference of $5^{30,000}\mathrm{and}{6}^{123,456}$a multiple of$31\mathrm{is}0$ i.e. it is multiple of $31$.