Dividing

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: $439 = 4(10^2)+3(10^1)+9(10^0)$

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

Then noting the earlier observation
$x= a_n(10^{n-1}) +a_{n-1}(10^{n-2})+...+a_2(10^2)+a_1(10)+a_0$

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

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

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

So,
$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)

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

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