0

This question comes from the 2018 Putnam and can be found in the following link:

https://kskedlaya.org/putnam-archive/

So far, I got the following two equations using simple algebra:

(1) $2018a = b(3a - 2018)$

(2) $2018b = a(3b - 2018)$

Then, I divide (1) by $b$ and I divide (2) by $a$ to get

(3) $\frac{2018a}{b} = (3a - 2018)$

(4) $\frac{2018b}{a} = (3b - 2018)$

Multiplying (3) and (4) together, I get $(2018)^2 = (3a - 2018)(3b-2018)$

So $(2018\mod3)$ is congruent to $(2\mod3)$ and $(2\mod3)^2$ is congruent to $(1 \mod3)$. In the answer provided, I'm told that each of the factors is congruent to $(1\mod3)$. Do we not consider the case when both factors are congruent to $(2\mod3)$ because only $2$ satisfies this requirement, and

$2$ x $2 = 4$ is definitely not equal to $2018$?

Skm
  • 2,296

4 Answers4

1

You want to look at factorizations of $2018^2$ where each term $\equiv -2018 \equiv 1 \mod 3$. Since $2018 = 2 \times 1009$ with $1009$ prime, there are not too many solutions.

Robert Israel
  • 448,999
1

Do we not consider the case when both factors are congruent to (2mod3) ...?

There is no such case since both factors in $(3a-2018)(3b-2018)$ are congruent to $1$ (mod $3$) whatever integers you take for $a$ and $b$: $$ 3n-2018=-2018=1\pmod{3},\quad \forall n\in{\mathbb{Z}}. $$

That's why the solution says so:

enter image description here

  • you're correct, each of the factors is congruent to $(1\mod3)$ by the logic you've used above. But I'm not sure if the reasoning I used in my explanation is incorrect, perhaps inefficient? – Skm Dec 24 '18 at 17:24
  • @K.M "because only 2 satisfies this requirement" does not make sense in that $(3a-2018)(3b-2018)$ can never be $2$. Then why would you consider $2$ in the first place? Also, I'm not sure what you mean by "this requirement". –  Dec 24 '18 at 17:59
  • well, I meant to say that each factor respectively could be congruent to $(2 \mod 3)$. Since we have that $(2 \mod 3)(2\mod 3)$=($2$ x $2$ $\mod 3$) = $(1 \mod 3)$. But it is incorrect to say that only $2 \equiv 2\mod 3$. – Skm Dec 24 '18 at 18:29
  • and yes, $(2 \mod 3)$ does not equal $(1 \mod 3)$. I apologize for ruining mathematics. – Skm Dec 24 '18 at 18:34
0

Take $d=gcd(a,b)$, with $a=da_2$, $b=db_2$. Then $\frac 1 a + \frac 1 b = \frac 1 {da_2} + \frac 1 {db_2}$. $a_2$ and $b_2$ are by definition coprime, so $\frac {b_2+a_2}{da_2b_2}$ is a fraction in simplest form that is equal to $\frac 3 {2018}$. Since $da_2b_2=2018$, and $1009$ is a prime factor of $2018$, it follows that of $d$, $a_2$, and $b_2$, one of them must be $1009$, and clearly that would be $d$ (otherwise the numerator $b_2+a_2$ would contain a $1009$, which is more than $3$). It then follows that of $a_2$ and $b_2$, one of them is $2$, and then it follows that the other is $1$.

Acccumulation
  • 12,210
0

More generally, if $\dfrac1{a}+\dfrac1{b} =\dfrac{u}{v}$, then $v(a+b) =abu $ or

$\begin{array}\\ 0 &=abu^2-uv(a+b)\\ &=abu^2-uv(a+b)+v^2-v^2\\ &=(au-v)(bu-v)-v^2\\ \end{array} $

so $(au-v)(bu-v)=v^2 $.

In particular, either $au\gt v, bu \gt v$ or $au\lt v, bu \lt v$.

We can assume that $a \ge b$.

If $a=b$ then $(au-v)^2=v^2 $ so $au-v = \pm v$ so that $a = \frac{2v}{u}$ (which gives $\frac1{a}=\frac{u}{2v}$) or $a=0$ , which not be. For there to be a solution here, we must have $u | 2v$.

So we can assume from now on that $a > b$.

For each factorization $v^2 = rs$ with $r \le s$, for a solution we must have either $au-v=r, bu-v = s $, $au-v=s, bu-v = r $, $au-v=-r, bu-v = -s $, or $au-v=-s, bu-v = -r$.

Since $a > b$ and $r \le s$, the first and third cases can not hold, so either $a = \frac{v+s}{u}, b = \frac{v+r}{u} $ or $a = \frac{v-r}{u}, b = \frac{v-s}{u} $.

For these to be integers, we must have either $u | (v+s), u | (v+r)$ or $u | (v-r), u | (v-s)$. In either case, we must have $u | (s-r)$.

By looking at $v \bmod u$ we can quickly decide which $r$ and $s$ will work.

marty cohen
  • 107,799