# Divisibility rules for CAT exam

Divisibility rules
A number is divisible by 2 if and only if the last digit is divisible by 2.
A number is divisible by 3 if and only if the sum of the digits is divisible by 3.
A number is divisible by 4 if and only if the last 2 digits is a number divisible by 4.
A number is divisible by 5 if and only if the last digit is divisible by 5.
A number is divisible by 6 if and only if it is divisible by 2 and 3.
A number is divisible by 8 if and only if the last 3 digits is a number divisible by 8.
A number is divisible by 9 if and only if the sum of the digits is divisible by 9.
A number is divisible by 10n if and only if the number ends in n zeros.
A number is divisible by 11 iff the sum of every other digit minus the sum of the rest of the digits is divisible by 11.

To find out if a number is divisible by seven, take the last digit, double
it, and subtract it from the rest of the number.

Example: If you had 203, you would double the last digit to get six, and
subtract that from 20 to get 14. If you get an answer divisible by 7
(including zero), then the original number is divisible by seven. If you
don't know the new number's divisibility, you can apply the rule again.

Number Theory:
The greatest common divisor is found by looking at the prime factorizations or using the Euclidean algorithm.

The least common multiple of a and b is found by looking at the prime factorizations or (ab)/gcd(a,b).

Two numbers are said to be relatively prime in the greatest common factor is 1.

If gcd(a, b)=d, then there exist integers x and y so that ax+by=d.

If d divides both a and b, then d divides a+b and d divides a-b.
a=b mod m iff m divides a-b iff a and b both have the same remainder when divided by m.

ap-1 = 1 mod p (a is not a multiple of p)
af(m)=1 mod m ( gcd(a, m) =1)
If a probability experiment is repeated n times and the probability of success in one trial is p, then the
probability of exactly r successes in the n trials is nCr (p)r(1-p)(n-r).

Rules of Logarithms:
loga(M)=y if and only if M=ay
loga(MN)=loga(M)+loga(N)
loga(M/N)=loga(M)-loga(N)
loga(Mp)=p*loga(M)
loga(1)=0
loga(ap)=p
loga(M)=logb(M)/logb(a)

The number of zeros at the end of n! is determined by the number of 5’s. To find this you do the following
process: n/5 = n1 and some remainder. Drop the remainder and compute n1/5 = n2 plus some remainder.

Drop the remainder and compute n2/5 = n3 plus some remainder, etc. The number of zeros is n1+n2+n3+n4...

The sum of any consecutive integers k through n, with n being the larger,
simply use this equation:
(n+k)(n-k+1)