
Math Events Math Events, Competitions, Meetups  Local, Regional, State, National, International 
 LinkBack  Thread Tools  Display Modes 
August 7th, 2009, 08:48 PM  #1 
Senior Member Joined: Apr 2007 Posts: 2,140 Thanks: 0  International Mathematical Olympiad, year 1971
1971/3. Prove that the set of integers of the form contains an infinite subset in which every two members are relatively prime.

August 10th, 2009, 01:45 PM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: International Mathematical Olympiad, year 1971
Hmm. If a  2^n  3, then a divides 2^(n + a  1)  3 because the period of 2^k  3 mod a divides a  1. So unless a < 5 (and even then it should work out, only a few cases must be tested) you have a does not divide 2^(n + a)  3. Not quite enough, but it feels like it's a step toward an answer. 
August 10th, 2009, 04:22 PM  #3 
Senior Member Joined: Apr 2007 Posts: 2,140 Thanks: 0 
Good solution to start out with, CRGreathouse. Honestly, I am a total beginner to the field of number theory. It would be a ways off until I can master number theory and tackle such IMO number theory problems...

August 10th, 2009, 09:07 PM  #4  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Quote:
 
August 10th, 2009, 10:22 PM  #5 
Senior Member Joined: Apr 2007 Posts: 2,140 Thanks: 0 
IMO problems are supposed to be hard problems. But, when you take a look at the solution of a IMO problem without solving it, you will be amazed how simple the solution is, so like you have said, there could be a simple trick that goes along with the above problem.

August 11th, 2009, 12:41 AM  #6  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Quote:
Hint on the problem: the approach of choosing congruence classes recursively by primes doesn't work (if the prime divides one less than the current modulus); I need a less restrictive approach.  
August 31st, 2009, 05:47 AM  #7 
Senior Member Joined: Dec 2008 Posts: 160 Thanks: 0  Re: International Mathematical Olympiad, year 1971
Honestly, I do not see how tip from CG lead to the solution. Here is a solution I propose: Let we already have a sequence of that  are relatively prime to each other. I show how to find that sequence is a sequence where all are relatively prime. Let Put  Euler function, then and is relatively prime with all 
August 31st, 2009, 05:40 PM  #8 
Senior Member Joined: Apr 2007 Posts: 2,140 Thanks: 0  zolden, are you like mathematically gifted or something. . .?

September 1st, 2009, 11:51 AM  #9 
Senior Member Joined: Dec 2008 Posts: 160 Thanks: 0  Re: International Mathematical Olympiad, year 1971
I am just hanging around. Sometimes, interesting problems get posted.

September 1st, 2009, 04:44 PM  #10 
Senior Member Joined: Apr 2007 Posts: 2,140 Thanks: 0 
Well, it's good to have good people on the forum! Stick around if you want, and we will discuss things, indeed! 

Tags 
1971, international, mathematical, olympiad, year 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Some questions about International Mathematical Olympiad  Eminem_Recovery  Math Events  9  January 23rd, 2011 05:36 AM 
A problem from 32nd International Mathematical Olympiad  johnny  Math Events  1  September 2nd, 2009 08:55 AM 
A problem from 31st International Mathematical Olympiad  johnny  Math Events  4  September 2nd, 2009 07:06 AM 
The 8th Korean Mathematical Olympiad  johnny  Math Events  5  July 23rd, 2009 03:12 PM 
Some questions about International Mathematical Olympiad  Eminem_Recovery  Algebra  1  December 31st, 1969 04:00 PM 