5
$\begingroup$

I gave this problem my best attempt and am now trying to understand the solution for it. This is problem #1 to the 79th William Lowell Putnam Math Competition. This is the given solution by Kiran Kedlaya and Lenny Ng:

By clearing denominators and regrouping, we see that the given equation is equivalent to $(3a−2018)(3b−2018) = 2018^2$. Each of the factors is congruent to $1 \text{ (mod } 3)$. There are $6$ positive factors of $2018^2 = 2^2 · 1009^2$ that are congruent to $1\text{ (mod } 3)$: $1$, $2^2$ , $1009$, $2^2 · 1009$, $1009^2$, $2^2 · 1009^2$. These lead to the 6 possible pairs: $(a,b)$ $= (673,1358114)$, $(674,340033)$, $(1009,2018)$, $(2018,1009)$, $(340033,674)$, and $(1358114,673)$. As for negative factors, the ones that are congruent to $1\text{ (mod }3)$ are $−2$, $−2 · 1009$,$−2 · 1009^2$. However, all of these lead to pairs where $a ≤ 0$ or $b ≤ 0$.

I don't fully understand these things:

  1. Each of the factors is congruent to $1\text{ (mod }3)$: I think congruence means the ability to translate into something else using some rules, so it seems like they are saying that $(3a-2018) = 1$ and $(3b-2018) = 1$. I'm also not sure why they wrote $1\text{ (mod }3)$ because 1 % 3 = 1, so why not just say $1$?
  2. There are $6$ positive factors of $2018^2 = 2^2·1009^2$ that are congruent to $1\text{ (mod }3)$: $1$, $2^2$, $1009$, $2^2·1009$, $1009^2$, $2^2·1009^2$: Here it seems like they are listing all of the ways to make $2018^2$, but if they are saying that $1$ is a possible factor then wouldn't $2018^2$ be its pair and therefore must be in this list? Why wouldn't they put it into this list?
  3. These lead to the 6 possible pairs:$(a,b) = (673,1358114)$, $(674,340033)$, $(1009,2018)$,$(2018,1009)$, $(340033,674)$, and $(1358114,673)$: How did they get these pairs?
$\endgroup$
  • $\begingroup$ Are you aware of the definition of congruence modulo $n$? We say $x$ is congruent to $y$ modulo $n$, i.e $x\equiv y \text{ (mod }n)$, if and only if, $x-y=kn$ for some $k\in \mathbb{Z}$. $\endgroup$ – Benjamin Feb 23 at 19:54
  • $\begingroup$ @Benjamin ah, I didn't know that. Ok so then how do you just realize that when working on this problem? The author stated this in the solution without explaining how he came to that conclusion. $\endgroup$ – whatwhatwhat Feb 23 at 20:18
  • $\begingroup$ If you are asking how you were supposed to know what congruence modulo $n$ means, then all I can say is that it is likely to be assumed knowledge (as it is a standard definition). Perhaps you may be able to find a document from those that run the competition that outlines all expected knowledge. To clarify the meaning of congruence modulo $n$, you should think of it as meaning remainder of division. For instance $5 \equiv 2 \text{ (mod }3)$ since $1$ "lots" of $3$ goes into $5$ with $2$ remaining. $\endgroup$ – Benjamin Feb 23 at 20:22
  • $\begingroup$ @Benjamin sorry, I was unclear - I'm primarily asking about how to come to that conclusion, not what knowledge is required for the exam. Using your definition, the statement reads that 1 "lots" of 3 goes into $(3a-2018)$ with 1 remaining. How do you know this to be true? We don't know the value of $a$. $\endgroup$ – whatwhatwhat Feb 23 at 20:44
  • $\begingroup$ That's not correct, actually. It could be any number of "lots" of 3 goes into $(3a-2018)$. It doesn't say anything about how many "lots" go into the number, it only tells you the amount remaining. I'm afraid I don't know how to answer the problem as a whole, but saw that you didn't seem to be familiar with the meaning of congruence, so clarified at least this point for you. I don't think I'm able to be of much more help than that, I'm afraid. $\endgroup$ – Benjamin Feb 23 at 20:51
1
$\begingroup$

We need to solve $$3ab=2018(a+b)$$ or $$9ab-3\cdot2018(a+b)+2018^2=2018^2$$ or $$(3a-2018)(3b-2018)=2018^2$$ or $$(3a-2018)(3b-2018)=2^21009^2.$$ Now, let $a\leq b$.

We obtain: $$3a-2018=1,$$ which gives $a=673$ and $b=1358114$ or $$3a-2018=2,$$ which is impossible because $2+2018$ is not divisible by $3$ or $$3a-2018=4,$$ which gives $a=674$ and $b=340033$ or $$3a-2018=1009,$$ which gives $a=1009$ and $b=2018$ or $$3a-2018=2\cdot1009,$$ which is impossible because $2\cdot1009+2018$ is not divisible by $3$.

Can you end it now?

$\endgroup$
  • $\begingroup$ Wait, why is $3a-2018 = 2$ impossible? If that were true, then $3b-2018 = 2*1009^2$ $\endgroup$ – whatwhatwhat Feb 23 at 19:26
  • 1
    $\begingroup$ @whatwhatwhat Because $2018+2$ is not divisible by $3$. $\endgroup$ – Michael Rozenberg Feb 23 at 19:38
  • $\begingroup$ $\bf \color{#c00}{-1}\ $ You didn't answer any of the OP's questions. Did you even read the question? $\endgroup$ – Bill Dubuque Feb 23 at 20:01
  • $\begingroup$ @Bill Dubuque I don't agree with you. I explained how we can get the answer. Read please better the question. $\endgroup$ – Michael Rozenberg Feb 23 at 20:03
  • 1
    $\begingroup$ @Bill Dubuque See please a last line of the question.I just restored a full solution before. $\endgroup$ – Michael Rozenberg Feb 23 at 20:10
1
$\begingroup$
  1. Saying a number is congruent to $1 \bmod 3$ means that when you divide it by $3$ you have a remainder of $1$. The point is that $3a-2018$ is congruent to $1 \bmod 3$ because $3a$ is a multiple of $3$ and $2018$ has a remainder of $2$ when divided by $3$.
  2. $2018^2$ is on the list as $2^2\cdot 1009^2$
  3. They used each factorization and solved for $a$ and $b$. The factorization $1 \cdot 2018^2$ gives us $3a-2018=1,a=673, 3b-2018=2018^2,b=\frac 13(2018^2+2018)=1358114$
$\endgroup$
  • $\begingroup$ Wait, but for point #1 I don't see how the factor is congruent to 1 mod 3 if the 2018 term has a remainder of 2. It would make more sense if the number was something like 2017 because this number would have a remainder of 1 when divided by 3, thus fulfilling the author's statement. $\endgroup$ – whatwhatwhat Feb 24 at 23:26
  • $\begingroup$ @whatwhatwhat: but the $2018$ is subtracted. $3a-2018 \equiv -2 \equiv 1 \pmod 3$ $\endgroup$ – Ross Millikan Mar 29 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.