Lesson Find the remainder of division

Find the remainder of division

Problem 1

Notice that the remainder of the number 44427 divided by 36 is 3:  44427 = 36*1234 + 3.


In other words,  44427 == 3  (mod 36).


Therefore,  44427 modulo 36  is 3,  and any degree   modulo 36  is equal to the same degree of 3 modulo 36.


Now,   == 9    mod 36

       ==   mod 36 == 27 mod 36

       ==  mod 36 == 3*27 mod 36 == 81 mod 36 == 9 mod 36.

       ==  mod 36 == 3*9 mod 36  == 27 mod 36.

       ==  mod 36 == 3*27 mod 36 == 81 mod 36 == 9 mod 36.



You see that the degrees   modulo 36 form  a cyclic sequence 


    n              1   2    3    4    5    6    7    8    9

     mod 36     3   9   27    9   27   9    27    9   27


Thus for n > 1,   mod 36  is 9 for EVEN VALUES of n  and is  27 for ODD VALUES of n.

Problem 2

It is easy to check directly that  567288133  gives the remainder  5  when divided by  8.

By the way, for it, only three last digits of a number are important.


    We write  567288133 == 5 mod 8.


It means that   gives the remainder   when divided by 8.


    Next,   = 15625.


It is also easy to check directly that the remainder  {15625 mod 8}  is the same as  {1 mod 8}.

    (and again, for it, only three last digits of the number 15625 do matter).


ANSWER.  When the number  is divided by 8, the remainder is 1.

Problem 3

    The remainder of divisibility by 9 of the number N is the same,
    as the remainder of the sum of digits of the number N when divided by 9.

The number  274563358  has the sum of its digits  2+7+4+5+6+3+3+5+8 = 43.


So, the number 274563358  itself,  when divided by 9, gives the same remainder 
as the sum of its digits 43 divided by 9, i.e. 43 mod 9 = 7.


Hence,  when divided by 9 gives the same remainder as the number  = 16807 when divided by 9.


Again, the number 16807 has the sum of the digits  1+6+8+7 = 22.

Therefore, the answer to the problem's question is 22 mod 9 = 4.

Problem 4

Following this idea, I write  40 = 36 + 4,

     = .


Next we should apply the Newtonian binomial formula.


It will give the sum of the terms  ,  k = 0, 1, 2, 3, . . . , 13.


All the terms with k >= 2  will be zero by modulo 81, since 36 = 9*4.


Therefore, we can exclude all these terms from our consideration.


So, the terms under our consideration are the terms with k= 0 and k= 1, or

     +  =  + .


This expression is easy to calculate using a regular calculator or Excel spreadsheet; 
its value is 7918845952.


Finally,  7918845952 mod 81 is 22  (use long division or Excel function mod)


So, the  ANSWER  is 22.