Primes and relatively primes.

[xilman]

This challenge is in two parts, the first quite easy and the second harder.

12 has the property that all natural numbers less than it and relatively prime to it are themselves prime.

a) What is the largest integer with this property?

b) Why?


Paul

[hyh1048576]

30 is the largest.
First,if p^2<S(the largest integer with this property),then p|S.(Otherwise p^2 is relatively prime to S but not prime).So if 7|S,we get 2|S,then 3|S,5|S,......
It's easy to prove that p1*p2*p3*...*pn>pn+1^2,where pn is the nth prime and n>3.This means 7|S will lead to "All the primes divides S", which is impossible!!!
So 7 doesn't devide S,then S<49.JUST VERIFY IT :)

[xilman]

Originally Posted by hyh1048576

It's easy to prove that p1*p2*p3*...*pn>pn+1^2,where pn is the nth prime and n>3.

If it's easy to prove, then you should prove it. Until you have provided a valid proof, I don't think you have fully answered the question.

Of course, if you can prove it's false then you certainly haven't answered the question!

Paul

[hyh1048576]

Originally Posted by xilman

If it's easy to prove, then you should prove it. Until you have provided a valid proof, I don't think you have fully answered the question.

Paul

Really easy:
Using Chebyshev's theorem, pn+1<2pn.So p1*p2*p3*...*pn>2*5*pn-1*pn>5*pn^2>4pn^2>pn+1^2,when n>4.When n=4,2*3*5*7>11^2. :)
It can also be proved without Chebyshev's theorem,but it's a little messy ;)