Primes and relatively primes.
 

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

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 p[size=7]1[/size]*p[size=7]2[/size]*p[size=7]3[/size]*...*p[size=7]n[/size]>p[size=7]n+1[/size]^2,where p[size=7]n[/size] 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 :)

Primes and relatively primes: proposed answer.
 

[quote="hyh1048576"]It's easy to prove that p[size=7]1[/size]*p[size=7]2[/size]*p[size=7]3[/size]*...*p[size=7]n[/size]>p[size=7]n+1[/size]^2,where p[size=7]n[/size] is the nth prime and n>3.[/quote]


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

Re: Primes and relatively primes: proposed answer.
 

[quote="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[/quote]Really easy:
Using [url=http://mathworld.wolfram.com/BertrandsPostulate.html]Chebyshev's theorem[/url], p[size=8]n+1[/size]<2p[size=8]n[/size].So p[size=8]1[/size]*p[size=8]2[/size]*p[size=8]3[/size]*...*p[size=8]n[/size]>2*5*p[size=8]n-1[/size]*p[size=8]n[/size]>5*p[size=8]n[/size]^2>4p[size=8]n[/size]^2>p[size=8]n+1[/size]^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 ;)