My Math Forum International Mathematical Olympiad, year 1971

 Math Events Math Events, Competitions, Meetups - Local, Regional, State, National, International

 August 7th, 2009, 07: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 $2^k-3(k=2,\,3,\,...)$ contains an infinite subset in which every two members are relatively prime.
 August 10th, 2009, 12: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, 03: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, 08: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:
 Originally Posted by johnny 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...
Honestly this one baffles me. I think it's one of the harder ones, unless I'm missing some simple trick.

 August 10th, 2009, 09: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 10th, 2009, 11:41 PM   #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:
 Originally Posted by johnny 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.
I'm not used to working on contest problems so I'm not good at finding tricks. Most of my methods on these problems have been fairly standard approaches, I think -- though the reciprocal problem turned out to be much simpler than I expected (because the problem was chosen to be unusually approachable, no doubt).

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, 04: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 ${n_i}$ that ${q_i= 2^{n_i} - 3}$ - are relatively prime to each other. I show how to find $n_{i + 1}$ that sequence ${q_{i + 1}}$ is a sequence where all are relatively prime. Let $P= \prod_{k = 1}^{i}(q_k)$ Put $n_{i + 1}= \varphi(P)$ - Euler function, then $2^{n_{i + 1}} - 1 \equiv 0 (mod(P))$ and $q_{i + 1}= 2^{n_{i + 1}} - 3$ is relatively prime with all $q_i$
 August 31st, 2009, 04:40 PM #8 Senior Member   Joined: Apr 2007 Posts: 2,140 Thanks: 0 zolden, are you like mathematically gifted or something. . .?
 September 1st, 2009, 10: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, 03: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 Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Eminem_Recovery Math Events 9 January 23rd, 2011 04:36 AM johnny Math Events 1 September 2nd, 2009 07:55 AM johnny Math Events 4 September 2nd, 2009 06:06 AM johnny Math Events 5 July 23rd, 2009 02:12 PM Eminem_Recovery Algebra 1 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top