Prime numbers.

Al-Allo · 2013-01-06 05:13:36

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.

So,

60=2.2.3.5

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

So,

240=2.2.2.2.3.5

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

scientia · 2013-01-06 06:19:18

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 and are non-negative integers some of which may be zero. Then

where

for .

For your example,

Therefore

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

Al-Allo · 2013-01-06 07:35:36

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

scientia · 2013-01-06 07:53:31

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

noelevans · 2013-01-06 10:16:30

Hi Al-Allo!

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
factor.

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.

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)

Math Is Fun Forum

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

Prime numbers.

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

Re: Prime numbers.

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

Re: Prime numbers.

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

Re: Prime numbers.

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

Re: Prime numbers.

Board footer