
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
January 5th, 2017, 05:50 AM  #1 
Member Joined: Dec 2016 From: USA Posts: 46 Thanks: 11  USAMTS  Year 28 (20162017)  Round 3  problem 5/3/28
Here are the proofs I promised ... The problem at hand is problem "5/3/28" from round 3 http://usamts.org/Tests/Problems_28_3.pdfof this year's USAMTS online competition. Since the submission deadline for round 3 was yesterday (January 3, 2017), the problem is no longer "live", so posting a solution now should be OK. The problem: Let $S = \left\{u + \frac{1}{u} \mid u \in {\mathbb Q}^{+}\right\}$.A solution to the "if" direction of part (a) was previously posted by "romsek" in the Calculus forum  see the recent thread 3 Problems I am really stuck onby "Rachel1234". In this post, I'll do the "only if" direction of part (a), and I'll also do part (b). Part (a), "only if" direction: Let $n$ be an integer which can expressed as a sum of two elements of $S$. Then $$n = \left(u + \dfrac{1}{u}\right) + \left(v + \dfrac{1}{v}\right) \tag{1}$$ where $u,v \in {\mathbb Q}^{+}$. Write $u = \dfrac{p}{q}$, $v = \dfrac{r}{s}$, where $p,q,r,s$ are positive integers such that $\text{gcd}(p,q) = 1$ and $\text{gcd}(r,s) = 1$. Then from equation (1), we get $$n = \bigg(\frac{p}{q} + \frac{q}{p}\bigg) + \bigg(\dfrac{r}{s} + \dfrac{s}{r}\bigg)$$ which simplifies to $$n(pq)(rs) = (rs)(p^2 + q^2) + (pq)(r^2 + s^2) \tag{2}$$ Now $\text{gcd}(p,q) = 1 \implies \text{gcd}(pq,p^2 + q^2) = 1$, and $\text{gcd}(r,s) = 1 \implies \text{gcd}(rs,r^2 + s^2) = 1$, so from equation (2), we get $(pq)(rs)$ and $(rs)(pq)$, hence $pq = rs$. Let $x = \dfrac{p}{s}$ and let $y = \dfrac{q}{r}$. Then $$u = \dfrac{p}{q} = \dfrac{p^2}{pq} = \dfrac{p^2}{rs} = \bigg(\dfrac{p}{s}\bigg)\bigg(\dfrac{p}{r}\bigg)= xy$$ and $$v = \dfrac{r}{s} = {\left(\dfrac{p}{s}\right) \over \left(\dfrac{p}{r}\right)} = \dfrac{x}{y}$$ Then \begin{align} n &= \left(u + \dfrac{1}{u}\right) + \left(v + \dfrac{1}{v}\right)\\ &= \left(xy + \dfrac{1}{xy}\right) + \left(\dfrac{x}{y}+ \dfrac{y}{x}\right)\\ &= \left(x + \dfrac{1}{x}\right) \left(y + \dfrac{1}{y}\right) \end{align} hence $n$ is the product of two elements of $S$, as was to be shown. This completes the proof of the "only if" direction of part (a). Next, part (b): It will suffice to show that if $n$ is a positive integer which is a multiple of 8, then $n$ is not the sum of two elements of $S$. Let $n$ be a positive integer which is a multiple of 8, and suppose $n$ is the sum of two elements of S. From our analysis of the "only if" direction of part (a), it follows that $$n(pq)(rs) = (rs)(p^2 + q^2) + (pq)(r^2 + s^2) \tag{3}$$ where $p,q,r,s$ are positive integers such that $$\text{gcd}(p,q) = 1\text{, gcd}(r,s) = 1\text{, }pq = rs$$ If we divide equation (3) by $rs$, then since $pq = rs$, we get $$npq = p^2 + q^2 + r^2 + s^2 \tag{4}$$ Then $8 \mid n$ implies $$p^2 + q^2 + r^2 + s^2 \equiv 0 \text{ }(\text{mod }8)$$ which of course implies $$p^2 + q^2 + r^2 + s^2 \equiv 0 \text{ }(\text{mod }4)$$ But since $\text{gcd}(p,q) = 1$ and $\text{gcd}(r,s) = 1$, at most two of $p,q,r,s$ are even. Equivalently, at least two of $p,q,r,s$ are odd. Then, since even squares are congruent to 0 (mod 4), and odd squares are congruent to 1 (mod 4), the congruence $$p^2 + q^2 + r^2 + s^2 \equiv 0 \text{ }(\text{mod }4)$$ implies that $p,q,r,s$ are all odd. Now consider the situation mod 8. Since odd squares are congruent to 1 (mod 8), $$p^2 + q^2 + r^2 + s^2 \equiv 0 \text{ }(\text{mod }8) \implies 4 \equiv 0 \text{ }(\text{mod }8)$$ contradiction. It follows that $n$ cannot be expressed as the sum of two elements of $S$. This completes the proof of part (b). 

Tags 
congruences, contest problem, diophantine equation, divisibility, usamts 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
USAMTS round 3 problem (20062007)  johnny  Math Events  1  August 31st, 2009 07:31 AM 
USAMTS round 1 problem (20062007)  johnny  Math Events  2  August 10th, 2009 09:14 PM 
USAMTS round 2 problem (20042005)  johnny  Math Events  5  August 10th, 2009 08:05 PM 
USAMTS round 1 problem (20042005)  johnny  Math Events  7  August 10th, 2009 03:09 PM 
USAMTS round 2 problem (20062007)  johnny  Math Events  1  August 10th, 2009 12:57 PM 