# Calculating the minimum element of an intersection of countable sets.

Discussion in 'Recreational Math' started by Guest, Jan 30, 2006.

1. ### GuestGuest

Hi - I have solved this (I think), using brute-force. However, I can't
help but think there must be a better way!

Let's call my sets A(n) = {t(n) + k.w(n) | k is 0,1,2,3...}
I wish to calculate min(intersect(A(n), for all n))

Fortunately, in my application, n is only 5: t(n)=2,3,4,7,9 and
w(n)=7,13,17,19,23. My minimum common element comes out as 477,857 - a
prime. (Calculated by software.)
Originally I thought the answer would be related to the least common
multiple of the t(n)s and/or w(n)s, but this doesn't seem the case.

Any number theorists about? Thanks Christopher Harrison

Guest, Jan 30, 2006
1. ### Advertisements

2. ### Chip EasthamGuest

Hi, Christopher:

The cases you describe, at least with finitely many values of n,
are solved by what is commonly called the Chinese Remainder
Theorem if the values w(n) are pairwise coprime. That is:

X = t(n) mod w(n) for all n

has a unique solution X modulo the least common multiple of
the w(n)'s. But since we assume their pairwise coprimality,
the least common multiple is the product of all w(n)'s.

If the w(n)'s are not coprime, then there may be no solution.
For example {0,6,12,18,...} and {2,11,20,29,...} have no
intersection, due to the common factor between "strides"
6 and 9. If there is a solution, then it is unique modulo the
least common multiple of the w(n)'s, even if these are not
coprime.

The theory above one says that the least _positive_
solution X lies between 1 and 7*13*17*19*23 = 676,039.
Obviously this accords with the solution you gave being
smaller than this. The fact that the solution turned out
to be prime is a bit of coincidence, helped in particular
by the requirement that none of the five w(n)'s will be
divisors (since the corresponding t(n)'s are nonzero).

Without some requirement on the solution other than
being an integer, there is no minimum value because
the modulus 7*13*17*19*23 = 676,039 could be
subtracted from any solution to give a "lesser" one.

Did you have a more specific question than whether
the solution is "related" to the least common multiple
of the w(n)'s ?

regards, (IANANT) chip

Chip Eastham, Feb 4, 2006
1. ### Advertisements

3. ### Christopher HarrisonGuest

Thanks very much Chip IANANTE I really should remember the
Chinese Remainder Theorem, though: I'm a mathematics graduate, and it
was mentioned several times - never had a use for it until now...
Thanks for reminding me!

I didn't have any specific questions as to how my solution was related
- I just needed a solution (which I've got) and thought there might
have been a neater way to find it than brute force. Mind you, I guess
putting a restriction on my sets makes things a little easier.

Thanks Christopher Harrison

Christopher Harrison, Feb 6, 2006

Ask a Question

## Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.