# Stuk with simple problem-Help!

1. Mar 30, 2004

### quddusaliquddus

for what values of n (where n is >=2) is there a sequnce of integers-positive so that the greatest num in the set divides the LCM of all the numbers left?

2. Mar 30, 2004

### matt grime

Suppose n is prime, is there anyway of finding numbers less than n whose product is divisible by n? If n is not prime could you find some constraint on its prime factors?

3. Mar 31, 2004

### quddusaliquddus

Question 1) Im not sure, but whatever number <= n e.g. M, multiplied by n e.g. M*n should give you a number. Any number divisable by n (prime) would have to have n as a factor wouldn't it? Does this mean you can't have numbers <=n when n is prime whose products are divisable by n?
Question 2) I'll have a look at that.

4. Mar 31, 2004

### matt grime

Well, you initial question starts off by mentioning n, and then doesn't use n at all in the second part when you set up the problem, so it's a little vague. And what sequences are allowed?

I took it to mean: suppose S is some set of numbers between 1 and n (not inclusive of n) wthout repetition. When can the lcm of the elements of S be divisible by n.

If n is prime, there is no subset of 1...n whose lcm is divisible by n, as there is no subset whose product is divisible by n, and the lcm divides the product.

Try it for some examples of n, and please clear up what you mean.

Examples,
n=6 S={2,3} the lcm is divisible by 6
n=9 there is no subset whose lcm is divisible by 9.

5. Mar 31, 2004

### quddusaliquddus

ok.............................

6. Mar 31, 2004

### matt grime

But do you admit that you say: let n be an integer greater than 2, and then go on to ask a question that is independent of n? Could you rewrite the question?

7. Mar 31, 2004

### quddusaliquddus

there's nothing to admit other than i might've done mistakes

8. Mar 31, 2004

### matt grime

Sorry, just trying to get you to say if n is tha largest number in the sequence or if it is the number of terms in the sequence. I couldn't decide what "ok......." meant.

9. Mar 31, 2004

### quddusaliquddus

i tried to type "ok" but it didint lemme...i typed some fullstops to satisfy the 12-letter rule (spaces also dont work)

10. Apr 5, 2004

### quddusaliquddus

I dont know if you guys wanna see the answer. But i think i've got it....bty...i didnt do it. Someone else helped me. if anyone's interested in seeing the answer....lemme know. I ask cos its a little long.

11. Apr 5, 2004

### matt grime

You're stilll not to my mind cleared up the question - is n the number of terms in the sequence or the largest term in the sequence? The answer is relatively straight forward in either case.

12. Apr 5, 2004

### quddusaliquddus

I wish i could say its easy...lol. n is the number of numbers.

13. Apr 5, 2004

### matt grime

But then unless you define the concept of 'sequence' oddly the answer is all n>2:

let p_i i =1,...n-1 be a set of n-1 distinct primes (this forms a sequence), then p_1, p_2...P_{n-1},q will do where q is the product of p_1...p_{n-1}

14. Apr 5, 2004

### quddusaliquddus

This is an answer i got somewhere else. Thought you might like to look at it:

" suppose n=p*q is composite, p,q>1, gcd(p,q)=1. then consider S={1,2,...,n}

then p,q belongs to S
hence p|LCM{1,2,...,n-1}
q|LCM{1,2,...,n-1}

since gcd(p,q)=1, then n=p*q|LCM{1,2,...,n-1}

suppose n=p^k, where p is odd prime
by Catalan's Theorem, then only two powers (greater than 1) differ by 1 is 2^3+1=3^2
and we have p^k+1 is divisible by 2 hence non prime
for the case p=2 k=3, we take {3,4,5,6,7,8,9,10}
otherwise
S={2,...,p^k,p^k+1} has p^(2k+1)+1 factors to u,v such that u*v=1 and we are done.

still think about the case where n=p... and n=2^k "

15. Apr 6, 2004

### matt grime

So it looks as though you mean n conescutive numbers then.

16. Apr 6, 2004

yeah.sorry.