MathLinks Forum LaTeX Help AoPS Classes Books Classroom MathLinks Contest Math Resources
The time now is Fri Nov 20, 2009 11:47 pm
All times are UTC + 2
View posts since last visit
View unanswered posts
A 9
View previous topicView next topic
 
8 Posts • Page 1 of 1
Author Message
Peter
Birch & Swinnerton Dyer
Birch & Swinnerton Dyer


Offline
Joined: 05 May 2004
Posts: 5202
Location: Ghent
Belgium

To rate posts you must be logged in
#1
A 9
[IHH, pp. 211]

Prove that among any ten consecutive positive integers at least one is relatively prime to the product of the others.

PostPosted: Fri May 25, 2007 2:24 am
Ilthigore
Riemann Hypothesis
Riemann Hypothesis


Offline
Joined: 31 Dec 2005
Posts: 305
Location: Bristol, UK
United Kingdom

To rate posts you must be logged in
#2
Clearly the only common prime factors amongst 10 consecutive positive integers will be 2,3,5,7.

5 of them will be divisible by 2, at least one of which must also be divisible by 3 and at least one of which must also be divisible by 5, and, if two of the numbers are divisible by 7, one of them will be even.

This leaves two multiples of 3, one multiple of 5, and one multiple of 7 unaccounted for, enough factors to dish out to 4 more of our integers.

But this still leaves one integer not divisible by 2,3,5,7, and therefore co-prime with all other integers of the set, and so coprime with their product.

PostPosted: Fri May 25, 2007 2:24 am
manjil
Riemann Hypothesis
Riemann Hypothesis


Offline
Joined: 29 Jun 2008
Posts: 254
Location: Tezpur
India

To rate posts you must be logged in
#3
Generalisation?

Can we replace 10 by n?

I have found that this fails for 25, although I am not sure of the other values. Can anyone give anything?
_________________
Manjil P. Saikia

PostPosted: Fri Aug 15, 2008 5:40 pm
Peter
Birch & Swinnerton Dyer
Birch & Swinnerton Dyer


Offline
Joined: 05 May 2004
Posts: 5202
Location: Ghent
Belgium

To rate posts you must be logged in
#4
Can you post your example for 25? Maybe that gives us a clue.
_________________
Boo!

PostPosted: Fri Aug 15, 2008 8:20 pm
MayankM
New Member
New Member

Offline
Joined: 04 Jul 2005
Posts: 14
Location: New Delhi
India

To rate posts you must be logged in
#5
I have read some where that this result is true for n up to 16 consecutive integers. I'll look up the source and post soon.
_________________
Imposible Nothing

PostPosted: Tue Aug 26, 2008 6:48 pm
manjil
Riemann Hypothesis
Riemann Hypothesis


Offline
Joined: 29 Jun 2008
Posts: 254
Location: Tezpur
India

To rate posts you must be logged in
#6
Re:Generalisation

peter wrote:
Can you post your example for 25? Maybe that gives us a clue.


Well my example is the natural numbers from 1 to 25.

MayankM wrote:

I have read some where that this result is true for n up to 16 consecutive integers. I'll look up the source and post soon.


The source of the problem said IHH pp.211 and so I took that out and I found what MayankM had siad to be true.
_________________
Manjil P. Saikia

PostPosted: Sun Aug 31, 2008 11:03 am
Peter
Birch & Swinnerton Dyer
Birch & Swinnerton Dyer


Offline
Joined: 05 May 2004
Posts: 5202
Location: Ghent
Belgium

To rate posts you must be logged in
#7
Re:Generalisation

manjil wrote:
peter wrote:
Can you post your example for 25? Maybe that gives us a clue.


Well my example is the natural numbers from 1 to 25.
Really? I think 23 is relatively prime to the product of the others though... Wink
_________________
Boo!

PostPosted: Sun Aug 31, 2008 11:48 am
Jure the frEEEk
Poincare Conjecture
Poincare Conjecture


Offline
Joined: 12 Aug 2007
Posts: 144
Location: Ljubljana, Slovenija

To rate posts you must be logged in
#8
MayankM wrote:
I have read some where that this result is true for n up to 16 consecutive integers. I'll look up the source and post soon.

it's true. 16 can be done and 17 can't. the counterexample for n=17 are consecutive numbers of which the first equals 27830.
(in fact the first can be 27830+30030k for a natural k, mybe there exists a smaller example that i missed but the point is that there are infinitely many)
u can proove it for n=16 basicaly same as ilthigore has done for n=10 above only a bit more complicated.

n=17
let a_1,...a_{17} be these consecutive numbers. if we set a_1 to be devisable by 2,5,11, a_2 devisable by 3, a_3 by 7 and a_4 by 13. it's easy to check thet none of them is than relatively prime to all others. we can calculate 27830 with china reminder theorem now.

what is left to do is to show that if there is a counter wxample for n than we can also find a counter example for n+1. im working on this now.
_________________
Archimedes will be remembered when Aeschylus is forgotten, because languages die and mathematical ideas do not!

PostPosted: Mon Sep 01, 2008 3:32 pm
Display posts from previous:   Sort by:   
8 Posts • Page 1 of 1
View previous topicView next topic
Jump to:  

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum
You cannot post calendar events in this forum

Created and Maintained by Valentin Vornicu - (c) AoPS Inc. 2004-2008