My Math Forum A problem from 31st International Mathematical Olympiad

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

 September 1st, 2009, 12:45 AM #1 Senior Member   Joined: Apr 2007 Posts: 2,140 Thanks: 0 A problem from 31st International Mathematical Olympiad 3. Determine all integers $n\,>\,1$ such that $\frac{2^n\,+\,1}{n^2}$ is an integer.
 September 1st, 2009, 06: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, 10:49 AM #3 Senior Member   Joined: Dec 2008 Posts: 160 Thanks: 0 Re: A problem from 31st International Mathematical Olympiad Let $n= 3^sq$, where 3 and q are relatively prime, and q is odd Then $R= 2^n + 1 = (3 - 1)^n + 1 = 3^{3^sq} + 3^{s + 1}q(3^{n - 2} + ... + 1)$ (1) Clearly $R$ is divisible by $n$ if $q= 1$, and $R$ is divisible by $n^2$ if$q= 1, s = 1$. 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, 05: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, 06: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: $2^p + 1= 2(2^{p - 1} - 1) + 3 = 3 (mod(p))$, so if n - prime it is 3. Let $n= qt$, where q - smallest prime, divided n. Then exists smallest r:$2^r + 1= 0(mod(q))$. It is true, because q is a divisor of n. Let $n= ar + b$, $b < r$ then: $-1= 2^n = (-1)^a 2^b (mod(q))$ If a - even: r - is not the smallest - contradiction if a - odd: $2^b - 1= 0 (mod(q))$: $r= mb + s$ - for some m and $s < r$: $2^s + 1= 0 (mod(q))$ - r is not the smallest. So r divides n. Let's show that $r < q$: If $r > q-1$: $r= c(q-1) + d, d < q-1=$, then $-1= 2^r = 2^d (mod(q))$, so $r>q-1>d$, 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 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 9 September 1st, 2009 03:44 PM 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