My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
January 5th, 2017, 04:50 AM   #1
Member
 
Joined: Dec 2016
From: USA

Posts: 46
Thanks: 11

USAMTS -- Year 28 (2016-2017) -- 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.pdf
of 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) Let $n$ be a positive integer. Prove that $n$ is the sum of two elements of $S$ if and only if $n$ is the product of two elements of $S$.

(b) Show that there exist infinitely many positive integers $n$ which cannot be expressed as the sum of two elements of $S$.

(c) Show that there exist infinitely many positive integers $n$ which can be expressed as the sum of two elements of $S$.
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 on
by "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).
quasi is offline  
 
Reply

  My Math Forum > College Math Forum > Number Theory

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 (2006-2007) johnny Math Events 1 August 31st, 2009 07:31 AM
USAMTS round 1 problem (2006-2007) johnny Math Events 2 August 10th, 2009 09:14 PM
USAMTS round 2 problem (2004-2005) johnny Math Events 5 August 10th, 2009 08:05 PM
USAMTS round 1 problem (2004-2005) johnny Math Events 7 August 10th, 2009 03:09 PM
USAMTS round 2 problem (2006-2007) johnny Math Events 1 August 10th, 2009 12:57 PM





Copyright © 2017 My Math Forum. All rights reserved.