You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**Al-Allo****Member**- Registered: 2012-08-23
- Posts: 324

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

Offline

**scientia****Member**- Registered: 2009-11-13
- Posts: 224

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

for .For your example,

Therefore

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

Offline

**Al-Allo****Member**- Registered: 2012-08-23
- Posts: 324

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

Offline

**scientia****Member**- Registered: 2009-11-13
- Posts: 224

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

Offline

**noelevans****Member**- Registered: 2012-07-20
- Posts: 236

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)*

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.

Offline

Pages: **1**