In this blog we will see theory and practical application to some of the more common mathematical constructs. The topics covered are: primes, GCD, Quadratic Equations, Permutation and Combinations basics, Modular Arithmetic.
Primes
A number is prime if it is only divisible by 1 and itself. So for example 2, 3, 5, 79, 311 and 1931 are all prime, while 21 is not prime because it is divisible by 3 and 7. To find if a number n is prime we could simply check if it divides any numbers below it. We can use the modulus (%) operator to check for divisibility. I have already discussed two methods for finding prime number 1. Sieve of Eratosthenes and 2. Sieve of Atkin . For better understanding please go through it.
GCD
The greatest common divisor (GCD) of two numbers a and b is the greatest number that divides evenly into both a and b. Naively we could start from the smallest of the two numbers and work our way downwards until we find a number that divides into both of them:
1: for (int i=Math.min(a,b); i>=1; i–)
2: if (a%i==0 && b%i==0)
3: return i; Although this method is fast enough for most applications, there is a faster method called Euclid’s algorithm. Euclid’s algorithm iterates over the two numbers until a remainder of 0 is found. For example, suppose we want to find the GCD of 2336 and 1314. We begin by expressing the larger number (2336) in terms of the smaller number (1314) plus a remainder:
2336 = 1314 x 1 + 1022
We now do the same with 1314 and 1022:
1314 = 1022 x 1 + 292
We continue this process until we reach a remainder of 0:
1022 = 292 x 3 + 146
292 = 146 x 2 + 0
The last non-zero remainder is the GCD. So the GCD of 2336 and 1314 is 146. This algorithm can be easily coded as a recursive function:
1: //assume that a and b cannot both be 0
2: public int GCD(int a, int b)
3: {
4: if (b==0) return a;
5: return GCD(b,a%b);
6: }
Using this algorithm we can find the lowest common multiple (LCM) of two numbers. For example the LCM of 6 and 9 is 18 since 18 is the smallest number that divides both 6 and 9. Here is the code for the LCM method:
1: public int LCM(int a, int b)
2: {
3: return b*a/GCD(a,b);
4: }
As a final note, Euclid’s algorithm can be used to solve linear Diophantine equations. These equations have integer coefficients and are of the form:
ax + by = c
Quadratic Equation
A quadratic equation is a second-order polynomial equation of a variable say x. The general form of a quadratic equation is given as:
a*x2 + b*x + c = 0
Where a,b and c are real known values and,
a can't be zero.
Roots of an Equation: The roots of an equation are the values for which the equation satisfies the given condition. For Example, the roots of equation x2 - 7x - 12 = 0 are 3 and 4 respectively. If we replace the value of x by 3 and 4 individually in the equation, the equation will evaluate to zero.
A quadratic equation has two roots. The roots of a quadratic equation can be easily obtained using the quadratic formula:
roots = (-b ± √(b2 - 4ac))/2a
Derivation:
ax2 + bx + c = 0
or, ax2 + bx = -c
or, x2 + (b/a)x = -(c/a)
or, x2 + (b/a)x + (b2/4a2) - (b2/4a2) = -(c/a)
or, x2 + (b/a)x + (b2/4a2) = -(c/a) + (b2/4a2)
or, (x + b/2a)2 = -(c/a) + (b2/4a2)
or, (x + b/2a)2 = (b2 - 4ac) /4a2
or, (x + b/2a) = ± √(b2 - 4ac) /2a
or, x = (-b ± √(b2 - 4ac))/2a
There arises three cases as described below while finding the roots of a quadratic equation:
If b2 < 4ac, then roots are complex
(not real).
For example roots of x2 + x + 1, roots are
-0.5 + i1.73205 and -0.5 - i1.73205
If b2 = 4ac, then roots are real
and both roots are same.
For example, roots of x2 - 2x + 1 are 1 and 1
If b2 > 4ac, then roots are real
and different.
For example, roots of x2 - 7x - 12 are 3 and 4
Permutation and Combination
Permutation is the different arrangements of a given number of elements taken one by one, or some, or all at a time. For example, if we have two elements A and B, then there are two possible arrangements, AB and BA.
Number of permutations when 'r' elements are arranged out of a total of 'n' elements is nPr = n! / (n - r)!. For example, let n = 4 (A, B, C and D) and r = 2 (All permutations of size 2). The answer is 4!/(4-2)! = 12. The twelve permutations are AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB and DC.
Important Properties of Permutation:
- nPn = n*(n-1)*(n-2)*......*1 = n!.
- nP0 = n!/n!= 1
- nP1 = n
- P(n,n-1) = n!.
- P(n,r)/P(n,r-1) = n-r+1.
Permutation with duplicates: The number of permutations or arrangements of N objects of which p1 are of one kind, p2 are of second kind, ..., pk are of k-th kind and the rest if any, are of different kinds is: N! / (p1! * p2! *....*pk!).
Combination is the different selections of a given number of elements taken one by one, or some, or all at a time. For example, if we have two elements A and B, then there is only one way to 00select two items, we select both of them.
Number of combinations when 'r' elements are selected out of a total of 'n' elements is n C r = n! / [ (r !) * (n - r)! ]. For example, let n = 4 (A, B, C and D) and r = 2 (All combinations of size 2). The answer is 4!/((4-2)!*2!) = 6. The six combinations are AB, AC, AD, BC, BD, CD.
Important Properties of Combination:
- nC0 = nCn =1.
- nCr = nCn-r.
- nCr + nCr-1 = n+1Cr
- n*C(n-1,r-1) = (n-r+1)*C(n,r-1)
Modular Arithmetic
Most of the time we have noticed that some questions, typically combinatorial and probability questions, have this funny habit of asking you to calculate a huge number, then tell you that "because this number can be huge, please output it modulo 10^9 + 7". Like, it's not enough that they ask you to calculate a number they know will overflow basic integer data types, but now you need to apply the modulo operation after that? Even worse are those that say you need to calculate a fraction p/q and ask you to output r where r⋅q≡p(mod m)... not only do you have to calculate a fraction with huge numbers, how in the world are you going to find r?
Actually, the modulo is there to make the calculation easier, not harder. This may sound counterintuitive, but once you know how modular arithmetic works, you'll see why too. Soon you'll be solving these problems like second nature.
"Basic" arithmetic
Basic rules and properties that can be applied in Modular Arithmetic(Addition, Subtraction, Multiplication etc.). Consider numbers a and b operated under modulo M.
- (a + b) mod M = ((a mod M) + (b mod M)) mod M.
- (a - b) mod M = ((a mod M) - (b mod M)) mod M.
- (a * b) mod M = ((a mod M) * (b mod M)) mod M.
The above three expressions are valid and can be performed as stated. But when it comes to modular division, there are some limitations.
There isn't any formula to calculate:
(a / b) mod M
For this we have to learn modular inverse.
The modular inverse is an integer 'x' such that.
a x ≡ 1 (mod M)
The value of x should be in {0, 1, 2, ... M-1}, i.e., in the ring of integer modulo M.
The multiplicative inverse of "a modulo M" exists if and only if a and M are relatively prime (i.e., if gcd(a, M) = 1).
Methods of finding Modular Inverse: There are two very popular methods of finding modular inverse of any number a under modulo M.
- Extended Euclidean Algorithm: This method can be used when a and M are co-prime.
- Fermat Little Theorem: This method can be used when M is prime.
Extended Euclidean algorithm that takes two integers 'a' and 'b', finds their gcd and also find 'x' and 'y' such that,
ax + by = gcd(a, b)
To find modulo inverse of 'a' under 'M', we put b = M in the above formula. Since we know that a and M are relatively prime, we can put value of gcd as 1.
So, the formula becomes:
ax + My = 1
If we take modulo M on both sides, we get:
ax + My ≡ 1 (mod M)
We can remove the second term on left side, as 'My (mod M)' would always be 0 for an integer y.
Therefore,
ax ≡ 1 (mod M)
So the 'x' that we can find using Extended Euclid Algorithm is modulo inverse of 'a'.
Fermat Little Theorem: The Fermat’s little theorem states that if M is a prime number, then for any integer a, the number a^M – a is an integer multiple of M.
That is,
aM ≡ a (mod M).
Since, a and M are co-prime to each other then aM-1 is an integral multiple of M.
That is,
a^M-1 ≡ 1 (mod M)
If we multiply both sides by a-1, we get:
a^-1 ≡ a^M-2 mod M
Therefore, if M is a prime number to find modulo inverse of a under M, find modular exponentiation of a^M-2 under modulo M.
Comments
Post a Comment