Primes, LCM, GCD and Addition of Fractions, Reducing Fraction

 

Motivation:

                        As we know,

                                            42 = 7  6

                                            42 = 21  2

                                            42 =  14  3

                                            42 = 42  1

 

                         We would like to find if there exits a method to uniquely represent a number via the product of several other natural numbers.  It is natural for the people to consider using the numbers that can not be represented by the product of other numbers under some constraints.  That is why we would like to explore the properties of numbers by decomposing them into the product of some smaller numbers.

 

 

Definition ( Divisor )

              If a natural number n has the following relationship with other integers p and q

                                           n = pq

              then we say that  p is a divisor of n ( q is a divisor of n ) .  Usually, the relationship is denoted as

                             p | n ,  q | n  .

 

 Example:    2 is a divisor of 42;  3 is also a divisor of  42 because

                                  42 = 2  21

                                  42 = 3  14

 

Definition ( Prime )

               If a natural number p ( p > 1 ) has no other divisor except 1 and itself, then we say that p is a prime ( or prime number ).

 

              With this definition, we should notice that 1 is not a prime.

 

Example:   2, 3, 5, 7, 11, 13 are primes.

 

Definition ( Prime Factorization )

    The process to represent a natural number as the product of prime numbers is called “prime factorization” .

 

Example:   42 = 2  3  7

 

 

 

 

 

 

Definition ( Common Divisor )

                  If   r | m  and r | n,  then we call  r is a common divisor of m and n.

 

Definition ( GCD, Greatest Common Divisor )

                  If there exists a number  g such that

                              g | m,  g | n, and g is larger than any other common divisors of m and n,

                 then we call that g is gcd ( Greatest Common Divisor ) of m and n. We denoted it as

                                   g = gcd(m,n)

 

 

Example:   gcd(12,8) = 4 .

                 The common divisors for 12 and 8 are 1, 2, 4.  4 is the largest one.

 

Definition (  Relatively Prime )

              Two positive integers m and n are relatively prime  if   gcd(m,n) = 1 .

 

Example: 3 and 5 are relatively prime.

 

 

Definition ( LCM, least common multiple )

              The lcm of two natural numbers m and n is defined as the smallest number such that  m and n are its divisors.  We denote it as

                                      lcm( m, n)

 

 

             Is it useful to know this?  In the application of computer network,  some  data encryption algorithms will use very large prime numbers to implement them. It is because finding prime numbers usually involves intensive computation.

 

            The immediate application of those concepts here is as follows:

 

 

Addition of Fractions ( Review )

 

                  How do we deal with the following problem

 

                                     = ?

 

                  The lcm of 3 and 7 is 21.  Thus,  the problem turns out to be

                                    =   .

 

 

 

Reducing Fraction to the lowest term

                      What is the difference between   and   ?   From the way we define fraction, you know that they are all equal to 2 .  When we come up with an answer for an arithmetic expression, we need to reduce the fraction to the simplest form such that the gcd ( greatest common divisor ) of numerator and denominator is 1.  Otherwise, the answer would be confusing that  it could not be recognized by people immediately.

 

                    Reducing Fraction to the lowest term can be done by finding gcd of numerator and denominator, and divide both by its gcd to get the simplest form.

 

 

Example:   

 

                    lcm( 3,51 ) = 51

                  So,  we have

                                   ( denominator and numerator being multiplied by 17 )

 

                +  =

 

                      gcd( 39, 51) = 3,  let’s reduce it to the lowest term:

                        

                          =      (  numerator and denominator being divided by 3 )

 

               Thus,

                              = 

 

 

              From this, you would notice that  gcd and lcm will be involved all the time when you handle some problems – although the problems do not ask you to find gcd and lcm explicitly.  There exist some skills for finding gcd and lcm while dealing with large numbers.   For smaller numbers,  the job can be done via prime factorization.

 

 

Finding gcd and lcm via Prime Factorization

 

            If  you finish the prime factorization for two numbers, how do you find the gcd and lcm for them?  Let’s consider the following

 

            

                         A = 2³²  3¹²  5⁷

                         B =  2⁵  3²³  7⁵⁵

 

                Let’s find the gcd and lcm of  the two numbers .

              

                First, consider  if  2⁵  can be divided by the two number.  The answer is yes because A is with 2³²  and B is with 2⁵ .   For gcd, you need to watch for the terms appearing on both:

 

                           gcd ( A, B ) = 2⁵  3¹²

 

               For lcm, you just choose the largest terms because you try to find the multiples for both:

                           lcm ( A, B ) = 2³²  3²³  5⁷  7⁵⁵

 

 

               Euclid’s algorithm  can be used to find gcd  of two numbers without doing prime factorization.  That will be introduce in the future.