Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2013-01-06 05:13:36

Registered: 2012-08-23
Posts: 324

Prime numbers.

Hi, just a simple question here : Let's say I have two composite numbers factorized in to prime numbers.

12= 2.2.3

20= 2.2.5

And the question is : If I want a number to be divisible by both 12 and 20, I will re arrange the prime numbers.



Which I think works perfectly, but it bothers me to know that we aren't using the two other 2's.



Why isn't that done ? Am I too complicating things for nothing ? (It's just I would want to understand why ^^)

Thanks for your answer


#2 2013-01-06 06:19:18

Registered: 2009-11-13
Posts: 224

Re: Prime numbers.

That's because you're calculating the LCM of the two numbers, and when you're calculating the LCM you want to be as economical as possible with their common prime divisors. In general, suppose

where the

are distinct primes and the
are non-negative integers some of which may be zero. Then



For your example,


Last edited by scientia (2013-01-06 06:24:59)


#3 2013-01-06 07:35:36

Registered: 2012-08-23
Posts: 324

Re: Prime numbers.

Ok, I didn't make the link with the LCM, so it's really for economical reason.

Could you just explain that part and the rest, not sure if i understood correctly


#4 2013-01-06 07:53:31

Registered: 2009-11-13
Posts: 224

Re: Prime numbers.

is the larger of the two numbers a and b. For example:


#5 2013-01-06 10:16:30

Registered: 2012-07-20
Posts: 236

Re: Prime numbers.

Hi Al-Allo! smile

Given a positive integer M>1 let PM denote the set of all prime factors of M.  As in your example
if M=12 then PM={2,2,3} and if M=20 then PM={2,2,5}.  As a further example consider M=105 so
PM={3,5,7}.  The first two (for 12 and 20) are multisets because they have more than one copy of
a prime factor (two 2's in each).  {3,5,7} is a typeset because it has only one copy of each prime

The union of two sets whether multisets or typesets is obtained by choosing each type of
prime seen and scanning all the sets for the maximum number occurring in any
ONE of the sets.

Then using "u" for union we get
I:     If M=12, N=20 then PMuPN = {2,2,3}u{2,2,5} = {2,2,3,5}.
II:    If M=12, N=18, L=30 then PMuPNuPL = {2,2,3}u{2,3,3}u{2,3,5} = {2,2,3,3,5}.
III:   If M=56, N=9, L=250 then PMuMPuPL = {2,2,2,7}u{3,3}u{2,5,5,5} = {2,2,2,3,3,5,5,5,7}.

The lcm of any two, three or more numbers is the PRODUCT of all the elements of this UNION.
For example I:    lcm(12,20) = X{2,2,3,5} = 2x2x3x5 = 60
                  II:   lcm(12,18,30) = X{2,2,3,3,5} = 2x2x3x3x5 = 180
                 III:  lcm(56,9,250) = X{2,2,2,3,3,5,5,5,7} =  2x2x2x3x3x5x5x5x7 = 63000

These products produce the smallest positive integer that each of the given numbers divides into
with NO REMAINDER because one can choose from the union a set looking like each of the sets
obtained from the numbers M, N, etc.

Example:  In the third example above:   the union:  {2,2,2,3,3,5,5,5,7}
                                                                      M:  {2,2,2,             7}
                                                                      N:  {2      3,3           }
                                                                      L:   {2,          5,5,5   }

If we replace the commas in these sets with "x" then we get lcm/M =  2x2x2x3x3x5x5x5x7
                                                                                                     2x2x2        x         7
which is 3x3x5x5x5=9x125=1125 which is an integer. 
Doing likewise for N and L we get  lcm/N=3500 and lcm/L=252.

If we leave out just one factor from the union, then at least one of M, N and L will NOT
divide into the product of the union with zero remainder.

NOTE:  In a similar fashion the highest common factor hcf (or greatest common divisor gcd) of two
or more numbers is the PRODUCT of the INTERSECTION of the prime factor sets:

                   hcf(M,N,L) = X(PMnPNnPL)   ( and lcm(M,N,L) = X(PMuPNuPL) as above)

where "n" represents intersection which is based on choosing minimums (instead of maximums)
from the scanning of each of the sets.  Be careful though.  If at least one of the sets has NONE of
a prime that OCCURS IN ANOTHER  set, then the minimum is ZERO for that type of prime.

For the three given examples: I:  PMnPN = {2,2}
                                           II:  PMnPNnPL = {2,3}  no 5's since 5 is missing from another set.
                                          III:  PMnPNnPL  = { }    empty since each type of prime is missing
                                                                              from at least one of the sets.
( NOTE:  X{ } = 1 by definition since X{a,b,c} means 1xaxbxc.  Always start with a 1 factor.)

So hcf(12,20) = X{2,2} = 4
     hcf(12,18,30) = X{2,3} = 6
     hcf(56,9,250) = X{ } = 1. 

The hcf is the largest integer with divides into each of the given numbers with no remainder.

I hope this will help you, though it may be more information than you wanted.  smile

P.S. The edit was just to get some spelling corrected and to make the wording a little clearer.

Last edited by noelevans (2013-01-06 18:00:38)

Writing "pretty" math (two dimensional) is easier to read and grasp than LaTex (one dimensional).
LaTex is like painting on many strips of paper and then stacking them to see what picture they make.


Board footer

Powered by FluxBB