Remainders Unlocked : Special cases

This is the final post on remainders wherein I will look to bring all the question specific concepts relating to remainders into this. So, let's start straight away..

Using Binomial Theorem :

(a + b)^n = C(n,0)*a^n + C(n,1)*a^(n-1)*b + C(n,2)*a^(n-2)*b^2 + .... C(n,n)*b^n

example : Find the remainder when 7^25 is divided by 36.
7^25 = (6 + 1)^25 = C(25,0)*6^25 + C(25,1)*6^24 + ... + C(25,23)*6^2 + C(25,24)*6 + C(25,25)
All terms except last two terms will be divisible by 36.
So, 7^25 mod 36 = [C(25,24)*6 + C(25,25)] mod 36 = (25*6 + 1) mod 36 = 151 mod 36 = 7.


Using factor theorem and remainder theorem :


If g(x) divides f(x), we say that f(x) is divisible by g(x) or g(x) is a factor of f(x).
Also, when a polynomial f(x) is divided by (x - a) then remainder is given by f(a)

example 1 : What is the remainder when x^4 - 3x^2 + 1 is divided by (x - 2)
Let f(x) = x^4 - 3x^2 + 1. Then, remainder = 2^4 - 3*2^2 + 1 = 5

example 2 : What is the largest value of n for which n^3 + 100 is divisible by (n  + 10).
We substitute n = -10 in the polynomial to get (-10)^3 + 100 = -900
(n + 10) must be now a factor of 900
k(n + 10) = 900
For largest value of n, k = 1
n = 890


Using Divisibility Rules :

Divisibility by 2 , 4(=2^2) , 8(=2^3) , 16(2^4) , ...

You check divisibility and remainder by last n digits of the number when number divided by 2^n.

Divisibility by 3

You check divisibility and remainder by calculating sum of digits of the number and dividing that by 3 or 9.

Divisibility by 5, 25(=5^2) , 125(=5^3) , ...

You check divisibility and remainder by last n digits of the number when divided by 5^n

Divisibility by numbers of the form 10^n + 1 : 11, 101, 1001 , ...

Break the number in groups of n digits starting from the right and add the n-digit groups with alternate + and - signs. If the sum is divisible by 10^n + 1, then the number is divisible by 10^n + 1

Why this happens?

Any number abcd(say) can be written as : a*10^3 + b*10^2 + c*10 + d
Now let us take remainder by 11.
Since 10 mod 11 = 10 or -1. 
We have 10^n mod 11 = -1 when n is odd and 10^n mod 11 = 1 when n is even
Hence we get, abcd mod 11 = (-a + b - c + d) mod 11

Divisibility by numbers of the form 10^n - 1 : 9, 99, 999, ..


Break the number in groups of n digits starting from the right and add the n-digit groups. If the sum is divisible by 10^n - 1, then the number is divisible by 10^n - 1

Why this happens?
 
Since 10 mod 9 = 100 mod 99 = 1000 mod 999 = 1 and so on,
So writing a number say abcd as ab*10^2 + cd, we can find remainder by 99 as :
(ab*10^2 + cd) mod 99 = (ab + cd) mod 99 which is nothing but groups of 2 from the right.


Divisibility by any prime greater than 5 : Seed number method

How to find seed number ?

We need to find a multiple of prime number that ends up in 10k +/- 1 form. Usually this would happen within the first 10 multiples of the prime.
example : Let 13 be the prime.
13*3 = 39 = 4*10 - 1 form => Seed number = 4
13*7 = 91 = 9*10 + 1 form => Seed number = (-9) 

NOTE : Seed number method is applicable to other base systems too with the only change that you look for bk +/- 1 format for a given base b

How to use seed number for divisibility ?

Break the number into unit digit,denoted by B and remaining digits,denoted by A.
Now if the seed number is N, then check for divisibility for A + NB and if the seed number is (-N) then check for divisibility for A - NB.


This brings us to close of the topic of remainders with the only discussion left in context of cyclicity and base systems other than decimal(base 10). These topics are independently big enough so will discuss them in separate articles some other day.

Rate,Like and Share the posts if the blog helps you understand things better.


Cheers!
AS