G.C.D of more than 2 numbers: Number Theory #GCD #of #numbers #theory #2

                                 

Greatest Common Divisor for more than two numbers :

                                 The greatest common divisor of three numbers ab,c is denoted by

   ( a, b, c ) and is defined by gcd { a,b,c } = (a,b,c)

                                                                    = ( a, ( b,c) )

                                                                    = ( (a,b) , c).

               i.e g.c.d depends only on numbers a,b,c and not on the order in which they are

              arranged.

Similarly , 

            the gcd of n integers  (a₁,a₂,…,a_n) = (  a₁, (a₂,…,a_n) )

            Again this number is independent of the order in which the ai is appear.

   If d= (a₁,a₂,…,a_n) ,  it is easy to verify that d divides each of the a_i and that every                    common divisor divides d. Moreover , d is a linear combination of the a_i. That                is, there exist integers  x₁,x₂,…,x_n such that d = a₁ x₁+ a₂ x₂+ … + a_n x_n

   If d = 1 then the numbers are said to be relatively prime. For example 2,3,10 are                      relatively prime for gcd { 2,3,10} = ( 2,3,10 ) = 1.

   If (ai,aj ) = 1 for different i and j the numbers a₁,a₂,…,a_n are called pairwise                            relatively prime numbers.

Properties of GCD :

     1. If (a,b) = 1 and if c\a and d\b then (c,d) = 1

     2. If (a,b) = (a,c) =1 ,then (a,bc) =1.

     3. If (a,b) = 1 then ( am , bk ) = 1 for all n > 1 and k > 1.

     4. If (a,b)=1 ,then (a+b ,a-b ) is either 1 or 2

     5. If (a,b) =1 then ( a+b, a²-ab+ b² ) is either 1 or 3.

     6. If (a,b) =1 and if d\(a+b) then (a,d) = (b,d) = 1

     7. If (a ,b )= 1 and (a\b)m = n then b=1.

     8. If ( a, b ) = 1 and ab = cn then a = xn and b =yn for some x and y.

     9. If (a,b) = 1 then for every n > ab there exist a positive x and y such that

           n= ax+by.

     10. If (a,b) =1 there are no positive x and y such that ab = ax+by.

     11. If (a,b) = 1 there exist x > 0 and y > 0 such that ax – by =1.

     12. If (a,b)=1 and xa = yb then x = nb and y = na for some n.

     13. If x and y and let m= ax+by , n = cx+dy where ad-bc =±1 then (m,n) = (x,y).

     14. Multiplicative property of gcd :

                          (ah,bk ) = (a,b)(h,k) (a\(a,b) , k\ (h,k) )( b\ (a,b), h\(h,k) ).

     15. If a > 1 then( a^m-1, aⁿ-1) = a^(m,n) – 1.

 Note  : 

          The properties above from 1 to 12 are exist only for relatively prime integers.

 * Euclidean Algorithm

 * Fundamental Theorem of Arithmetic

 *  Properties of Numbers

 * Historical Introduction to Number Theory

* The Mobius Function μ (n) 

  #GCD #of #numbers #theory #2