
Math Events Math Events, Competitions, Meetups  Local, Regional, State, National, International 
 LinkBack  Thread Tools  Display Modes 
September 1st, 2009, 01:45 AM  #1 
Senior Member Joined: Apr 2007 Posts: 2,140 Thanks: 0  A problem from 31st International Mathematical Olympiad
3. Determine all integers such that is an integer.

September 1st, 2009, 07:48 AM  #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: A problem from 31st International Mathematical Olympiad
Well, for starters, n must be odd. Clearly, n = 3 works. I think that's the only solution, but I'm not sure how to show it. (There are no other small solutions.) I can show worthless facts like 'such n are not divisible by 5' with modular arithmetic, but that's no help. 
September 1st, 2009, 11:49 AM  #3 
Senior Member Joined: Dec 2008 Posts: 160 Thanks: 0  Re: A problem from 31st International Mathematical Olympiad
Let , where 3 and q are relatively prime, and q is odd Then (1) Clearly is divisible by if , and is divisible by if. Did I miss something? Yes, I did. In the expression (1) figure in brackets is not integer (prove or disprove). Statement about s=1 is still correct if we move q inside the brackets  there are enough 3s there to compensate, but statement about q still need to be proved. 
September 1st, 2009, 06:50 PM  #4 
Senior Member Joined: Apr 2007 Posts: 2,140 Thanks: 0 
Right, CRGreathouse. n = 3 is clearly a solution to the problem. There could possibly be other solutions as well, but again we have to prove whether there is or not an another set of solutions.

September 2nd, 2009, 07:06 AM  #5 
Senior Member Joined: Dec 2008 Posts: 160 Thanks: 0  Re: A problem from 31st International Mathematical Olympiad
Let's take another way. If n = p, p  odd prime (n is odd, obviously), then: , so if n  prime it is 3. Let , where q  smallest prime, divided n. Then exists smallest r:. It is true, because q is a divisor of n. Let , then: If a  even: r  is not the smallest  contradiction if a  odd: :  for some m and :  r is not the smallest. So r divides n. Let's show that : If : , then , so , and r is not smallest again. So n cannot be composite and n = 3 is the only solution. Is it messy? Personally, I do not like this solution. Can somebody come up with the more elegant one? 

Tags 
31st, international, mathematical, olympiad, problem 
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 
International Mathematical Olympiad, year 1971  johnny  Math Events  9  September 1st, 2009 04:44 PM 
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 