Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is related to the question If a finite set of rational numbers sums to one, does one of the rationals have a denominator equal to the LCM of all the denominators?

Suppose $1 = \sum\limits_{i=1}^n \frac{p_i}{q_i}$, where $p_i,q_i$ are positive integers, and $\gcd(p_i,q_i)=1$.

Let $k = \max_{i=1}^n \{ q_i\}$. $m=\operatorname{lcm}(q_1,\ldots,q_n)$.

Can we bound $m$ by $k$ and $n$? The obvious bound is $m\leq k^n$; however, I feel that there exists better bounds.

share|improve this question
4  
Well, $m\leq k!/(k-n)!$; but you want something more intelligent than that, I think... (The inequality holds because if $q_1\gt\cdots\gt q_n$ then $m\leq q_1q_2\cdots q_n \leq k(k-1)\cdots(k-n+1)$; and if $q_i=q_{i+1}$, you can omit $q_{i+1}$ from the inequalities) –  Arturo Magidin Jan 2 '12 at 4:12
add comment

2 Answers

up vote 2 down vote accepted
+100

Let $\Pi$ be the product of the $q_i$'s. If $r$ is a prime dividing $m$, $r$ must divide some $q_i$, so let $e>0$ be maximal such that $r^e$ divides $q_i$, for some $i$, and fix such an $i$. $r^e$ is then the largest power of $r$ dividing $m$. Let $\nu_r$ be the $r$-adic valuation on $\Bbb Q$. Then, since $\gcd(p_i,q_i)=1$, $\nu_r(p_i/q_i)=-e<0$, which is the minimum value $\nu_r(p_j/q_j)$ can take. However, $\nu_r(\sum_{j=1}^n p_j/q_j)=\nu_r(1)=0$, so there must be some $i'\ne i$ with $\nu_r(p_{i'}/q_{i'})=-e$. Therefore, $r^e\mid q_{i'}$ and so $r^{2e}\mid \Pi$. Repeating this step for all primes $r\mid m$ gives $m^2\mid \Pi$. Therefore, $m\le \sqrt{\Pi}\le k^{n/2}$.

share|improve this answer
add comment

Supposing that all the $q_i$ are distinct (otherwise if all $q_i$ are equal and all $p_i=1$ the bound $m=k^{n}$ is met):

If $t|q_i$ and $t$ is prime then there exists some other $q_j$ where $t|q_j$ since $\sum_{i=1}^n \frac{p_i}{q_i}=\frac{p_1q_2...q_n+q_1p_2q_3...q_n+...+q_1q_2...p_n}{q_1q_2...q_n}$ and $gcd(p_i,q_i)=1$.

If the list $k, k-1,...,k-n+1$ contains x primes, remove those x primes, multiply together the remaining members of that list, and multiply by $(k-n+1)(k-n)...(k-n-x+1)$ to get a marginally improved bound.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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