A Guide to some important mathematical theorems

Cutting the chase lets start with what we are gonna cover in this post.
1. Modulo Arithmetic
2. Euclidian algorithmn for finding gcd
3. Fermat’s little theorem
4. Wilson’s theorem

Some basic questions before jumping straight in :

1. What does modulo means ?
   In computing, the modulo operation , represented as % , finds the remainder after division of one number by another ( wiki ).
   Given two positive numbers, a and n, a % n gives the remainder when a is divided by n.
   eg: 19%4=3 , 28%7=0 ..
2. What is gcd ?
   Greatest common divisor, aka gcd of two number is nothing but the highest common factor ( hcf )of two numbers you might have studied in highschool, which is the largest number which divides both of the numbers
   eg: gcd(14,12)=2 , gcd(14,35)=7, gcd(18,24)=6 …
3. Is it the same wilson from House MD ?
   Nope, the only thing they both have in common is that they are dead.

Modular Arithmetic

In the clock, yes the one hanging in the wall , after every 12 hours the hour hand of the clock resets . Now a simple question for you , if the hour hand is at 5 currently , where will it be after 8 hours ?
Obviously it will be at 1, but the crux is how did you calculate it ? you didn’t simply add 8 and 5, but did something different ? what was it ?
What you did there wasn’t some kind of sorcery, but was a basic application modular arithmetic as, (8+5)%12 = 13%12 = 1 ( why % 12 though ? because the clock resets after 12 hours )

Enough of the clock analogy .

Just like multiplication oprator ( * ) , modulo opeator also has distributive property , which are as follows :
1. (a+b) % m = ( a%m + b%m )%m ,
2. (a-b) % m = ( a%m -b%m +m )%m , ( why is m added ? )
3. (a*b)%m = ( ( a%m)*(b%m) )% m
4. (a/b)%m = ( to be discussed later in the article )

Lets take a simple example on these properties
( 1234567*987654 + 23166)% 13 = ( (1234567*987654)%13 + 23166%13 )%13 = ( ( (1234567%13) * (987654%13) )%13 + 23166%13 ) %13
(skipping steps) = 6

But what is use of these properties, when we can always apply modulo operator at the the final expression after multiplying or adding ?
Certainly you can do that, but these properties are useful when you smell overflow in your program ( i.e. the numbers are so large you cannot contain them in memory after multiplying ), after taking modulo the number gets smaller .
NOTE:
a%b= a- [a/b]*b , where [ ] is the floor function or greatest integer function you might have studied
( this realisation comes in handy in many proofs )

Euclidean algorithm

Back in school times we all leaned this amazing method known as long division method for finding hcf ( or gcd), the method tells that the last divisor is the gcd of the numbers ( if you are dont remember then see the example below ).
If you remember the principle then rejoice you already know the principle of euclid algorithm.

If you remember the long division method,
then it becomes trivial that gcd(a,b)= gcd(b,a%b) …….. // (as a%b <b)
Now this definition can be applied recursively until the smaller value becomes 0, at that point the larger value will be the gcd .

Enough of this gibberish lets take examples :

Using long division

using recusive definition:

A simple recursive definition is as follows :

function gcd(a, b)
    if b = 0
       return a; 
    else
       return gcd(b, a%b);

Brief intro : Euclidean algorithm is used to find the gcd of two numbers efficiently, by using the fact that gcd of two numbers does not change if larger number is replaced by its differnce with smaller number ( taking succesive difference results in modulo) .

NOTE:
There is an extended version of this algorithm, known as Extended euclid algorithm, which works on same principle and along with finding gcd can be used to find solution of equation ax+by=c ( with certain conditions ) .
( To be taught in classes taken by codeschool ).

Fermat’s little theorem

Fermat’s little theorem

Fermat’s little theorem states that if p is a prime number, then for any integer a, the number a^p -a is an integer multiple of p. In the notation of modular arithmetic, this is expressed as above . ( wiki )

This property is comes in handy in calculating larger power of a value using modular exponentiaion ( possibly to be discussed in next blog ).

For now lets go back to the question we left earlier ,
WHAT is (a/b) %p , where p is any prime number ?

Phewww ….

Unfortunate for you, this isn’t the endgame yet.
As far as calculation of b^(p-2) goes, it can be done using binary exponentiation efficiently… ( to be discussed in next article ).

Ps: There is another way of finding inverse of a number under modulo using [ (1/a)%p ], which is using extended euclid algorithm. More on inverse will be talked later.

Wilson’s Therorem

A positive integer n, n>1 is a prime iff , (n−1)! ≡ −1 ( mod n)
or , (n−1)! ≡ n−1 ( mod n) .
In easier terms any natural number ‘n’ following { (n-1)! +1 }%n = 0,
is prime.
The proof is the theorem is based on fermat’s little theorem, and is skipped here -.-

PS: This article is not written in any specific order, i just wrote what i felt like writing( and what i found in wiki XD ).