Thread: 3x = 2y

When counting by 2s and by 3s, how can I find out how many times the numbers intersect?
For example:

counting by 2s:
2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24...

counting by 3s:
3, 6, 9, 12, 15, 18, 21, 24...


One Half of all numbers counting by 3s are also counting by 2s (bold numbers).

When counting by 5s what ratio of numbers are divisible by 2 and 3?
5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80...
there is obviously a pattern here. 1/3 of all numbers divisible by 5 are also divisble by 2 and 3.

Is there a general formula to tell what ratio are already divisible by some other number?

Originally Posted by DivideByZero

When counting by 5s what ratio of numbers are divisible by 2 and 3?
5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80...

Be careful with your language. The numbers in the list above divisible by 2 and 3 are the multiples of 30. The numbers you put in bold are those divisible by 2 or 3.

Let a and b be integers. A number n is divisible by a and b if and only if it is divisible by their least common multiple (lcm), which I denote [a,b]. So if I list out the multiples of a (i.e., if I count by a) and ask which ones are divisible by b, I obtain the multiples of [a,b]. Now it shouldn't be too hard to see that the ratio of multiples of [a,b] to multiples of a is a/[a,b].

We can extend this further. For example, for three integers a, b, and c, let's list out the multiples of a. Which ones are also divisible by b and c? Precisely the ones divisible by [b,c]. So then the ones divisible by a, b, and c are the multiples of [a,[b,c]] = [a,b,c], the least common multiple of a, b, and c. Then the ratio of numbers divisible by a, b, and c to those divisible by a is a/[a,b,c].

We can also answer the question: given the multiples of a, which ones are also divisible by b or c (or both)? Well, we know that a/[a,b] of them are divisible by a and b and a/[a,c] of them are divisible by a and c. If I add these numbers together, I count some numbers too many times. To be precise:

-if m is divisible by a and b but not c, it's only counted in a/[a,b]
-if m is divisible by a and c but not b, it's only counted in a/[a,c]
-if m is divisible by a, b, and c, it's counted in both a/[a,b] and a/[a,c]--i.e., it's counted twice

So to get the right answer, we have to subtract the numbers divisible by a, b, and c to account for them being counted twice. But we just figured this out. So our answer is:

a/[a,b]+a/[a,c]-a/[a,b,c]

I just realized--this means your 1/3 is wrong. If we count just numbers divisible by 2 and 3 out of those divisible by 5, we should get 5/[2,3,5] = 5/30 = 1/6. If we count numbers divisible by 2 or 3 out of those divisible by 5, we get:

5/[2,5]+5/[3,5]-5/[2,3,5] = 5/10+5/15-5/30 = 1/2+1/3-1/6 = 2/3

and this matches up with your list.

Originally Posted by serpicojr

Originally Posted by DivideByZero

When counting by 5s what ratio of numbers are divisible by 2 and 3?
5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80...

Be careful with your language. The numbers in the list above divisible by 2 and 3 are the multiples of 30. The numbers you put in bold are those divisible by 2 or 3.

Let a and b be integers. A number n is divisible by a and b if and only if it is divisible by their least common multiple (lcm), which I denote [a,b]. So if I list out the multiples of a (i.e., if I count by a) and ask which ones are divisible by b, I obtain the multiples of [a,b]. Now it shouldn't be too hard to see that the ratio of multiples of [a,b] to multiples of a is a/[a,b].

We can extend this further. For example, for three integers a, b, and c, let's list out the multiples of a. Which ones are also divisible by b and c? Precisely the ones divisible by [b,c]. So then the ones divisible by a, b, and c are the multiples of [a,[b,c]] = [a,b,c], the least common multiple of a, b, and c. Then the ratio of numbers divisible by a, b, and c to those divisible by a is a/[a,b,c].

We can also answer the question: given the multiples of a, which ones are also divisible by b or c (or both)? Well, we know that a/[a,b] of them are divisible by a and b and a/[a,c] of them are divisible by a and c. If I add these numbers together, I count some numbers too many times. To be precise:

-if m is divisible by a and b but not c, it's only counted in a/[a,b]
-if m is divisible by a and c but not b, it's only counted in a/[a,c]
-if m is divisible by a, b, and c, it's counted in both a/[a,b] and a/[a,c]--i.e., it's counted twice

So to get the right answer, we have to subtract the numbers divisible by a, b, and c to account for them being counted twice. But we just figured this out. So our answer is:

a/[a,b]+a/[a,c]-a/[a,b,c]

I just realized--this means your 1/3 is wrong. If we count just numbers divisible by 2 and 3 out of those divisible by 5, we should get 5/[2,3,5] = 5/30 = 1/6. If we count numbers divisible by 2 or 3 out of those divisible by 5, we get:

5/[2,5]+5/[3,5]-5/[2,3,5] = 5/10+5/15-5/30 = 1/2+1/3-1/6 = 2/3

and this matches up with your list.

Holy cow! Thats amazing! I forgot all about using lcm!

but yeah 1/3 is wrong. I meant to count the bold numbers: 4/6 = 2/3.

I like the way you explained it to me, thanks!
It makes a lot of sense how to find the ratio.

that general formula you deduced just looks so beautiful!

so, do you have a masters in math or something?

So for a,b,c, and d is it:

a/[a,b] + a/[a,c] + a/[a,d] - (a/[a,b,c] + a/[a,c,d] + a/[a,b,c,d])

It should be...

a/[a,b] + a/[a,c] + a/[a,d] - (a/[a,b,c] + a/[a,c,d] + a/[a,b,d]) + a/[a,b,c,d]

The reasoning is you count anything divisible by a and exactly two of b, c, and d twice, so you have to subtract them as before. But you also counted everything divisible by all of a, b, c, and d three times and then subtracted them three times, so you have to add them back in, hence the last term.

(In general, it will be an alternating sum of things looking like a/[a,...] where the ... runs over combinations as above, and the sign is -1 raised to the number of things in the lcm bars. I wouldn't be surprised if there were a nicer formula than the one I give.)

Originally Posted by serpicojr

It should be...

a/[a,b] + a/[a,c] + a/[a,d] - (a/[a,b,c] + a/[a,c,d] + a/[a,b,d]) + a/[a,b,c,d]

The reasoning is you count anything divisible by a and exactly two of b, c, and d twice, so you have to subtract them as before. But you also counted everything divisible by all of a, b, c, and d three times and then subtracted them three times, so you have to add them back in, hence the last term.

(In general, it will be an alternating sum of things looking like a/[a,...] where the ... runs over combinations as above, and the sign is -1 raised to the number of things in the lcm bars. I wouldn't be surprised if there were a nicer formula than the one I give.)

ok thanks

I presume that you haven't spoken about a, b, c etc being mutually prime or otherwise because it is a less general case, but it seems to me that if they're mutually prime then the lcm is simply a x b x c...

And therefore if you're counting the ratio of multiples of a that are divisible by b, c etc then it would simply be 1/(b x c...)

When not mutually prime, of course (say taking 6, 8 and 9 and finding the ratio of mutual divisibility in multiples of 12, then the full lcm formula as you described would need to be used.

Is that about right?

Indeed--the lcm of relatively prime numbers is just their product.