Maths Olympiad Prep

Library / /301 of 520

Number theory Difficulty 6.9 National olympiad Prove it

2.97 Let a,b,ca, b, c be pairwise coprime positive integers, prove: 2abcabbcca2abc - ab - bc - ca is the largest integer that cannot be expressed in the form xbc+yca+zabxbc + yca + zab (where x,y,zx, y, z are non-negative numbers).

Solution

[Proof] If
2abcbccaab=xbc+yca+zab,2 a b c-b c-c a-a b=x b c+y c a+z a b,

where x0,y0,z0x \geqslant 0, y \geqslant 0, z \geqslant 0, then we have
2abc=bc(x+1)+ca(y+1)+ab(z+1).2 a b c=b c(x+1)+c a(y+1)+a b(z+1).

Thus a(x+1)bca \mid (x+1) b c and since (a,bc)=1(a, b c)=1, it follows that a(x+1)a \mid (x+1). Therefore, ax+1a \leqslant x+1.
Similarly, we have by+1,cz+1b \leqslant y+1, c \leqslant z+1, hence
3abc=bca+cab+abcbc(x+1)+ca(y+1)+ab(z+1)=2abc, a contradiction. \begin{aligned} 3 a b c & =b c a+c a b+a b c \\ & \leqslant b c(x+1)+c a(y+1)+a b(z+1) \\ & =2 a b c, \text{ a contradiction. } \end{aligned}

Therefore, 2abcbccaab2 a b c-b c-c a-a b cannot be expressed in the form xbc+yca+zabx b c+y c a+z a b.
Next, to prove that any number nn greater than 2abcbccaab2 a b c-b c-c a-a b can be expressed in the form xbc+yca+zabx b c+y c a+z a b, we will prove a simple result to be used below:

Let a,ba, b be positive integers and (a,b)=1(a, b)=1, then any number greater than ababa b-a-b can be expressed in the form ax+by(x0,y0)a x+b y (x \geqslant 0, y \geqslant 0).

Since (a,b)=1(a, b)=1, every integer mm can be expressed as
m=ua+vb,u,vZ.m=u a+v b, u, v \in \mathbb{Z}.

Clearly, such an expression is not unique, but all expressions can be written as
m=(ukb)a+(v+ka)b,kZ.m=(u-k b) a+(v+k a) b, k \in \mathbb{Z}.

Choose k0k_0 such that 0uk0b<a0 \leqslant u-k_0 b < a. Let u0=uk0bu_0 = u - k_0 b and v0=v+k0av_0 = v + k_0 a. Then 0u0<a0 \leqslant u_0 < a and m=u0a+v0bm = u_0 a + v_0 b.

Since m>ababm > a b - a - b, we have
u0a+v0b>abab.u_0 a + v_0 b > a b - a - b.

This implies v0b>bv_0 b > -b, so v0>1v_0 > -1, i.e., v00v_0 \geqslant 0. This proves the above proposition.
Finally, we use the above proposition to prove that when n>2abcbccaabn > 2 a b c - b c - c a - a b, nn can be expressed in the form xbc+yca+zab(x0,y0,z0)x b c + y c a + z a b (x \geqslant 0, y \geqslant 0, z \geqslant 0).
Since
n>2abcbccaab=(abcabca+a)+(abcabc)=a(b1)(c1)+(abcabc)abcabc.\begin{aligned} n & > 2 a b c - b c - c a - a b \\ & = (a b c - a b - c a + a) + (a b c - a - b c) \\ & = a (b - 1) (c - 1) + (a b c - a - b c) \\ & \geqslant a b c - a - b c. \end{aligned}

And since (a,bc)=1(a, b c) = 1, nn can be written as n=aw+xbcn = a w + x b c with xa1x \leqslant a - 1. Thus,
aw=nbcxnbc(a1)>abcabca,a w = n - b c x \geqslant n - b c (a - 1) > a b c - a b - c a,

i.e., w>bcbcw > b c - b - c. Since (b,c)=1(b, c) = 1, we have w=cy+bz(y0,z0)w = c y + b z (y \geqslant 0, z \geqslant 0). Therefore,
n=aw+bcx=bcx+cay+abz.\begin{aligned} n & = a w + b c x \\ & = b c x + c a y + a b z. \end{aligned}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.