Friday, December 22, 2006

Logarithms, Divisibility rules & Number theory

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)

No comments: