Show that to find Rem(n,4) one just needs to replace n e N with the last two digits of n.

Why is it that only the last three digits of n e N need to be considered when calculating Rem(n,8)?

Printable View

- Mar 19th 2009, 10:13 PMjzelltDividing
Show that to find Rem(n,4) one just needs to replace n e N with the last two digits of n.

Why is it that only the last three digits of n e N need to be considered when calculating Rem(n,8)? - Mar 19th 2009, 11:07 PMNokio720
Hi jezllt,

I am not sure if you are familiar with modulos. The solution relies on the use of it.

Show that for the Rem(n,4) you will just need to observe the last two digits of an n digit number. (I'm assuming Rem stands for remainder)

Part 1:

First note that any n digit number can be rewritten using the linear combination of place digits (i.e ones, tens,etc.) multiplied by some power to the 10 ( note the power of 10 is one less the the place of the digit).

Ex: $\displaystyle 439 = 4(10^2)+3(10^1)+9(10^0)$

let x be your n digit number then in the form $\displaystyle x=a_na_{n-1}...a_1a_0 \; n\geq2$ the $\displaystyle a_i 's$ are natural numbers

Then noting the earlier observation

$\displaystyle x= a_n(10^{n-1}) +a_{n-1}(10^{n-2})+...+a_2(10^2)+a_1(10)+a_0$

factoring a $\displaystyle 10^2$ from every term except the last 2 (this is possible since $\displaystyle n \geq3$)

$\displaystyle x= 10^2[ a_n(10^{n-3} +a_{n-1}(10^{n-4})+...a_2] +a_1(10)+a_0$

Note $\displaystyle (10)^2 = (2*5)^2=2^2*5^2=4*5^2$

So,

$\displaystyle x(Mod4)= \{4*5^2[ a_n(10^{n-3} +a_{n-1}(10^{n-4})+...a_2] +a_1(10)+a_0\} (Mod4)$ ( The '=' should be replaced with the congruent symbol)

$\displaystyle = 4*5^2[ a_n(10^{n-3} +a_{n-1}(10^{n-4})+...a_2] (Mod4) + [a_1(10)+a_0] (Mod4)$

$\displaystyle x(Mod4) = 0(Mod4) + [a_1(10)+a_0] (Mod 4) = [a_1(10)+a_0] (Mod4)= (a_1a_0) (Mod 4)$

Thus evaluation of the remainder of an n digit number when divided by 4 is equivalent to the the remainder of the last two digits divided by 4:

For Rem (n,8) try the same technique but factor a 10^3 from all digits except the last 3 and apply (Mod 8).

Hope this helps.