Wednesday, February 22, 2006

Divisibility. Topic: Number Theory. Level: Olympiad.

Problem: (Gabriel Carroll Original) Find all positive integers $ a,b,c $ such that $ a|(bc+1) $, $ b|(ca+1) $, $ c|(ab+1) $.

Solution: We first claim that they must all be pairwise relatively prime. Assume the opposite, that $ gcd(a,b) = k \neq 1 $. But then $ bc+1 $ is not divisible by $ k $ so $ a $ cannot divide it. Contradiction. So $ a,b,c $ are pairwise relatively prime.

Multiply the divisibilities together. We then have

$ abc|(ab+1)(bc+1)(ca+1) \Rightarrow abc|[(abc)^2+(a+b+c)(abc)+ab+bc+ca+1] \Rightarrow abc|(ab+bc+ca+1) $.

Suppose $ min(a,b,c) \ge 3 $. Then we clearly have $ a,b,c $ distinct (or they wouldn't be relatively prime), so assume WLOG that $ 3 \le a < b < c $.

Then $ abc \ge 3bc = bc+bc+bc \ge (ab+1)+bc+(ca+1) > ab+bc+ca+1 $. But if $ abc|(ab+bc+ca+1) $, we have $ abc \le ab+bc+ca+1 $. Contradiction. So $ min(a,b,c) < 3 $.

Then we check $ a = 1, 2 $. Again, we assume WLOG that $ a \le b \le c $.

$ a = 1 $: We have $ b|(c+1) $ and $ c|(b+1) $ so $ b \le c+1 $, $ c \le b+1 $. Then since $ b \le c $, we have $ b = c $ or $ b+1 = c $. If $ b = c $, we have $ b|(b+1) \Rightarrow b|1 \Rightarrow b = 1 $. If $ b+1 = c $, we have $ b|(b+2) \Rightarrow b|2 \Rightarrow b = 1, 2 $. This gives us $ (b,c) = (1,1); (1,2); (2,3) $.

$ a = 2 $: We have $ b|(2c+1) $ and $ c|(2b+1) $. Note that $ 2b+1 $ cannot have any divisors between $ b $ and itself. This is true because other than itself its next largest possible divisor is $ \frac{2b+1}{2} $ and the other ones are all less than $ b $. But since $ \frac{2b+1}{2} $ is never an integer, this is impossible. Therefore, since $ b \le c $, we have $ c = 2b+1 $. This gives us $ b|(4b+3) \Rightarrow b|3 \Rightarrow b = 3 $, so $ (b,c) = (3,7) $ is a solution.

Hence our solutions are $ (a,b,c) = (1,1,1); (1,1,2); (1,2,3); (2,3,7) $ and all permutations of them. QED.

--------------------

Comment: This problem required some messy casework and bounding, and it's really easy to miss solutions (especially the last one). Thorough and rigorous arguments must be maintained to find them all.

6 comments:

  1. Look at that not even Gabriel Carroll can stump you. Haha, hey did you find out abotu RSI yet?

    ReplyDelete
  2. Haha. Well this is one of the problems in his Easier-Moderate packet =P. But I haven't heard from RSI yet; they don't get back to us until March 31, which is a long ways from now still.

    ReplyDelete
  3. You know you want to go to SIMUW since it's soooo much cooler than any other summer program. Only loser people go to places like RSI.

    ReplyDelete
  4. hello,i am a math olympiad student in china.would you plase tell me if i could post in your blog?i love your blog style very much.and my blog cannot post math quations.

    sorry for my bad english.^_^

    ReplyDelete
  5. Umm, I'd rather keep my blog to myself, but it's pretty easy to set up your own blog to post math stuff... in fact, you can find instructions here: http://wangsblog.com/content/view/10/25/. This works with any WordPress blog.

    ReplyDelete
  6. [...] all the solutions: for instance, permutations of and work as well. I have a full solution posted here. This entry was posted in math. Bookmark the permalink. ← park&go Video(Used with [...]

    ReplyDelete