Marcos

Posted on Friday, 17 October, 2003 - 01:57 pm:

What is the minimum n (if it exists), such that given a sequence of distinct naturals (a_n) (each a_i being the product of at most 2 primes and greater than 1) we can be sure that (regardless of the choice of a_i's) all sufficiently large integers can be written as

a_i x_i

for some suitably chosen x_i's?

Thanks
Marcos

David Loeffler

Posted on Friday, 17 October, 2003 - 03:31 pm:

No matter what n is, we can take all the a_i's to have a common factor d > 1, and thus

n
å
i=1

a_i x_i

must be a multiple of d. (Conversely, if the a_i's are coprime, there exist x_i such that

n
å
i=1

x_i a_i = 1

, and we can obviously now express all integers by multiplying this through.)

David

Marcos

Posted on Friday, 17 October, 2003 - 09:02 pm:

Thanks,
I noticed the first point shortly after I posted.
For the second point what happens if we restrict ourselves to x_i > 0?

David Loeffler

Posted on Friday, 17 October, 2003 - 11:30 pm:

Still works for all sufficiently large integers. Obviously if you can do any integer between 1 and a=min a_i, you can do everythin by adding copies of a; this is a finite number of cases, so there is some fixed lower bound -M on all the x_i's you are ever going to want to use in representing an arbitrary positive number.

Define
K=M å
a_i

. Then for any m > K, we can write m=K+m ' . If
m ' = å
x_i a_i

then
m= å
(M+x_i)a_i

and M+x_i ³ 0.

Obviously we can sharpen this upper bound a great deal. In case n=2 there is a rather neat formula that gives the size of the largest m that you can't represent in this way; for n > 2 it gets a bit messy as you have various cases according to which subsets of the a_i have common factors.

David

Marcos

Posted on Saturday, 18 October, 2003 - 12:15 pm:

Thanks,

I'm not sure I fully understand.

How can we be sure that
m ' = å
x_i a_i

?

And did you mean "this lower bound" in the last paragraph or am I more confused than I think?

Marcos

David Loeffler

Posted on Saturday, 18 October, 2003 - 06:02 pm:

OK. I'll rephrase that. There exist x_i such that

x_i a_i = m '

and x_i > -M all i.

And yes, I did mean 'lower bound'!

David

Marcos

Posted on Sunday, 19 October, 2003 - 08:33 am:

Thanks I understand it now (actually it seems my problem was that -M)

Marcos

Marcos

Posted on Sunday, 19 October, 2003 - 08:38 am:

One last thing: Can I have some hints on discovering/deriving the neat formula for the n=2 case?

Marcos

David Loeffler

Posted on Sunday, 19 October, 2003 - 09:53 pm:

trial and error is often a good approach!