Divisibility by 2, 4, 8, 16

• A number is divisible by 2 if the last digit of the number is divisible by 2 i.e. last digit is 0, 2, 4, 6 or 8

• A number is divisible by 4 if the last two digits of the number are divisible by 4. For eg. 1348 is divisible by 4 because 48 is divisible by 4.

• A number is divisible by 8 if the last three digits of the number are divisible by 8. For eg. 21348 is not divisible by 8 because 348 is not divisible by 8.

• A number is divisible by 16 if the last four digits of the number are divisible by 16. For eg. 1,134,224 is divisible by 16 because 4224 is divisible by 16.

Divisibility by 3, 9, 27

• A number is divisible by 3 if the sum of all digits of the number are divisible by 3. Hence 729 (sum of digits = 7+2+9=18) is divisible by 3

• A number is divisible by 9 if the sum of all digits of the number are divisible by 9. Hence 62172 (sum of digits = 6+2+1+7+2=18) is divisible by 9.

• A number is divisible by 27 if the sum of blocks of 3 from left to right are divisible by 27. Hence 134433 (sum of blocks = 134+433=567) is divisible by 27.

Divisibility by 7

• Remove the last digit, double it and subtract it from the truncated original number. For example: 1638, 163-16=147 is divisible by 7 hence 1638 is divisible by 7. This process should be repeated for larger numbers.

Divisibility by 11

• Take sum of all even digits and subtract it from the sum of all odd digits. If the difference is a multiple of 11 the original number will be a multiple of 11. Example 23452 (sum odd = 2+4+2=8 sum even=3+5=8) difference=8-8=0 is divisible by 11 hence 23452 is divisible by 11.

Divisibility properties

• For composite divisors, check if the number is divisible by the factors individually. Hence to check if a number is divisible by 6 it must be divisible by 2 and 3.

• The equation $$a^n-b^n$$ is always divisible by a-b. If n is even it is divisible by a+b. If n is odd it is not divisible by a+b.

• The equation $$a^n+b^n$$ is never divisible by a-b. If n is odd it is divisible by a+b. If n is even it is not divisible by a+b.

Quick Recap

• Divisibility by 2: Last digit divisible by 2

• Divisibility by 4: Last two digits divisible by 4

• Divisibility by 8: Last three digits divisible by 8

• Divisibility by 16: Last four digit divisible by 16

• Divisibility by 3: Sum of digits divisible by 3

• Divisibility by 9: Sum of digits divisible by 9

• Divisibility by 27: Sum of blocks of 3 (taken right to left) divisible by 27

• Divisibility by 7: Remove the last digit, double it and subtract it from the truncated original number. Check if number is divisible by 7

• Divisibility by 11: (sum of odd digits) - (sum of even digits) should be 0 or divisible by 11

Cyclicity

• To find the last digit of $$a^n$$ find the cyclicity of a. For eg. if a=2, we see that

  $$2^1 = 2$$

  $$2^2 = 4$$

  $$2^3 = 8$$

  $$2^4 = 16$$

  $$2^5 = 32$$

  Hence, the last digit of 2 repeats after every 4 th power. Hence cyclicity of 2 =4. Hence if we have to find the last digit of $$a^n$$, the steps are:

  1. Find the cyclicity of a, say it is x

  2. Find the remainder when n is divided by x, say remainder r

  3. Find $$a^{r}$$ if r>0 and $$a^{x}$$ when r=0

• For example, find the last digit of $$4^{102}$$ * $$6^{39}$$

  The cyclicity of 4 is as follows:

  $$4^1 = 4$$

  $$4^2 = 16$$

  $$4^3 = 64$$

  Hence, cyclicity of 4 is 2 and of 6 is 1. Last digit of $$4^{102}$$ is 6 and that of $$6^{39}$$ is 6. Thus 6*6 would give 6 as the last digit.

• HCF * LCM of two numbers = Product of two numbers

• The greatest number dividing a, b and c leaving remainders of $$x_1$$, $$x_2$$ and $$x_3$$ is the HCF of (a-$$x_1$$), (b-$$x_2$$) and (c-$$x_3$$).

• The greatest number dividing a, b and c (a<b<c) leaving the same remainder each time is the HCF of (c-b), (c-a), (b-a).

• LCM of fractions = LCM of Numerators ÷ HCF of Denominators.

Remainder Theorem

• If a, b, c are the prime factors of N such that N= $$a^p$$ * $$b^q$$ * $$c^r$$

  then the number of numbers less than N and co-prime to N $$ \phi (N) $$= N (1-1/a) (1 - 1/b) (1 - 1/c). This function is known as the Euler's totient function.

Euler's theorem

• If M and N are co-prime to each other then remainder when $$M ^ {\phi (N)} $$ is divided by N is 1.

Factors

Number of factors

• To find the number of factors of a number, convert the number into the product of its prime factors. Prime factors of a number are the divisors that are prime numbers. Hence 720 can be represented as

  720 = 16 * 9 * 5 = $$2^4$$ * $$3^2$$ * 5

• The individual factors of 720 can be constructed by taking 2 0 times, 1 time, 2 times . . 4 times = 5 ways

  Similarly 3 can be taken 0 times, 1 time or 2 times = 3 ways

  Similarly 5 can be taken 0 times or 1 time= 2 ways

  Hence the number of factors of 720 are = number of combinations of factors = (4+1) * (2+1) * (1+1) = 5*3*2=30.

• In general if the number can be represented as N = $$a^{p}$$ ∗ $$b^{q}$$ ∗ $$c^{r}$$ . . . then number of factors is (p+1) * (q+1) * (r+1) . . .

• If the number of factors are odd then N is a perfect square.

• If there are n factors, then the number of pairs of factors would be n/2. If N is a perfect square then number of pairs (including the square root) is (n+1)/2.

Number of even and odd factors

• To get even factors of 720, we must take 2 as a factor at least once.

  Hence 2 can be taken 1 time, 2 times, 3 times, 4 times = 4 ways

• If the number can be expressed as N = $$2^{p}$$ ∗ $$a^{q}$$ ∗ $$b^{r}$$ . . . where the power of 2 is p,

  1. Then the number of even factors of N = p (1+q) (1+r) . . .

  2. The number of odd factors of N = (1+q) (1+r) . . .

     Hence the number of even factors of 720 (as shown above) = 4 * (2+1) * (1+1) =4 * 3 * 2 = 24

     Hence the number of odd factors of 720 (as shown above) = (2+1) * (1+1) = 3 * 2 = 6

Sum of factors

• If the number can be represented as N = $$a^{p}$$ \∗ $$b^{r}$$ \∗ $$c^{q}$$ . . .

  Then sum of factors is

  $$\frac{a^{p+1} -1}{a-1}$$ * $$\frac{b^{q+1} -1}{b-1}$$ * $$\frac{c^{r+1} -1}{c-1}$$ . . .

  Hence sum of factors of 720 = $$\frac{2^{5} -1}{2-1}$$ * $$\frac{3^{2+1} -1}{3-1}$$ * $$\frac{5^{1+1} -1}{5-1}$$ = 31 * 13 * 6 = 2418

Highest power of a number in a Factorial

• The factorial of n is represented as n! = 1 * 2 * 3 . . . * (n-1) n

• The highest power of a number p in a factorial n! if p is prime:

• Lets take the example of highest power of 5 in 30!

  To find the highest power of 5 in 30, find the number of multiples of 5 in 30 + find the number of multiples of 25 in 30 + so on

  Hence, highest power of 5 in 30= 6+1 = 7

• In general, highest power of p in n is sum = number of multiples of p + number of multiples of $$p^2$$ + number of multiples of $$p^3$$ and so on.

• The highest power of a number c in a factorial n! if c is composite:

• If c is a composite, find its highest prime factor. The power of the composite in n! is the same as the power of its highest prime factor. Hence the highest power of 21 in 100! is the highest power of 7 in 100!. Hence, highest power of 7 in 100! = 14+2=16. Hence the highest power of 21 in 100! is 16.

Recap of Formulae

• If N = $$a^{p}$$ ∗ $$b^{q}$$ ∗ $$c^{r}$$ . . . then number of factors is (p+1)(q+1)(r+1) . . .

• If the number of factors are odd then N is a perfect square.

• If there are n factors, then the number of pairs of factors would be n/2. If N is a perfect square then number of pairs (including the square root) is (n+1)/2.

• If the number can be expressed as N = $$2^{p}$$ ∗ $$a^{q}$$ ∗ $$b^{r}$$ . . . where the power of 2 is p,

• Then the number of even factors of N = p (1+q) (1+r) . . .

• The number of odd factors of N = (1+q) (1+r) . . .

• If the number can be represented as N = $$a^{p}$$ ∗ $$b^{q}$$ ∗ $$c^{r}$$ . . .

  Then sum of factors is

  $$\frac{a^{p+1} -1}{a-1}$$ * $$\frac{b^{q+1} -1}{b-1}$$ * $$\frac{c^{r+1} -1}{c-1}$$ . . .

• In general, highest power of a prime p in n is sum = number of multiples of p + number of multiples of $$p^2$$ + number of multiples of $$p^3$$ and so on

Number of trailing zeros of n! in base b(b=$$p^m$$, where p is a prime number) is for $$k\ge1$$ $$\frac{1}{m}\left(\Sigma\left[\frac{n}{p^k}\right]\ \right)$$

Properties of Remainders

1. The value of remainders can be from 0 to d-1, where d is the divisor. For example, 24 divided by 5 has a remainder of 4, and when any number is divided by 5, the remainder can be from 0 to 4.

2. If N < d, the given number is less than the divisor, then the remainder will be equal to N. For ex, if 5 is divided by 7, the remainder will be 5.

3. (M + N) mod d = (M mod d + N mod d) Mod d

4. (M - N) mod d = (M mod d - N mod d) Mod d

5. (M x N) mod d = (M mod d  X N mod d ) Mod d

Chinese Remainder Theorem: When a divisor can be split into two co-prime factors a and b such that N = a x b , then by dividing the given number M with individual factors such that remainder in each case is p and q that is M mod a = p and M mod b = q and two variables are introduced and an equation is formed such that ax+by = 1, it is important to note that x and y can only take integral values. So after finding the individual remainders of M when divided by factors a and b, this equation is solved to get integral values of x and y.

Thus, the Chinese remainder states that

M mod N = (aqx+ bpy) mod N

Where a and b are factors of divisors and are co-prime

p and q are individual remainders when M is divided by a and b

M mod a = p and M mod b = q

x and y are integers that satisfy the equation ax+by = 1

Fermat's Theorem - For any integer $$a$$ and prime number $$p$$, $$a^p-a$$ is always divisible by $$p$$

Wilson's Theorem - For a prime $$p$$, remainder when $$(p-1)!$$ i divided by $$p$$ is $$(p-1)$$

Euler's Theorem - If M and N are co-prime to each other then the remainder when $$M^{\phi(N)}$$ is divided by N is 1