Sign up ×
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.

From Putnam and Beyond:

Proofs (Question 10:)

Let $n>1$ be an arbitrary real number and let $k$ be the number of positive prime numbers less than or equal to $n$. Select $k + 1$ positive integers such that none of them divides the product of all the others. Prove that there exists a number among the chosen $k + 1$ that is bigger than $n$.

Assume the contrary. Our chosen numbers $a_1,a_2,\dots,a_{k+1}$ must have a total of at most $k$ distinct prime factors (the primes less than or equal to $n$). Let $o_p(q)$ denote the highest value of $d$ such that $p^d\mid q$. Also, let $a = a_1a_2\dots a_{k+1}$ be the product of the numbers. Then for each prime $p$, $o_p(a) = \sum_{i=1}^{k+1} o_p(a_i)$, and it follows

Here's the part onwards that I do not understand: Specifically, what does it mean by hostile value?

that there can be at most one hostile value of $i$ for which $o_p(a_i)>o_{p}(a)/2$. Because there are at most $k$ primes that divide $a$, there is some $i$ that is not hostile for any such prime. Then $2o_p(a_i)\le o_p(a)$, so $o_p(a_i) \le o_p(a/a_i)$ for each prime $p$ dividing $a$. This implies that $a_i$ divides $a/a_i$, which contradicts the fact that the $a_i$ does not divide the product of the other $a_j$’s. Hence our assumption was false, and the conclusion follows.

Question is page 16 of the pdf while answer is on 367 of the pdf.


PS Can someone help me tag it here

When I put 'contest-math' it does not recognize the existing tag and says its new.

share|cite|improve this question

migrated from May 19 '12 at 12:27

This question came from our site for users of TeX, LaTeX, ConTeXt, and related typesetting systems.

Please learn some TeX, as your question is almost unreadable without it. For example, instead of a1, write a_1, and put dollar signs around it, and you get $a_1$. – Gerry Myerson May 19 '12 at 12:35
I think that I guessed correctly at subscripts and superscripts, but you should check my translation. – Brian M. Scott May 19 '12 at 12:42
Doesn't this book also provide solutions. (Solution to your question on page 367) – Kirthi Raman May 19 '12 at 12:42
@Artin: The OP’s question is about the language of the solution. – Brian M. Scott May 19 '12 at 12:43
@ Gerry Myerson: Thanks, for notice. I will use Tex next time. – Mat.S May 19 '12 at 12:50

1 Answer 1

up vote 3 down vote accepted

The sentence in which the term hostile value of i is used is intended to define the term: a hostile value of $i$ is one such that $o_p(a_i)>o_p(a)/2$. If there were distinct $i$ and $j$ such that $o_p(a_i)>o_p(a)/2$ and $o_p(a_j)>o_p(a)/2$, then $o_p(a) = \sum_{i=1}^{k+1} o_p(a_i)>o_p(a)$, so there is at most one such ‘hostile’ $i$. (I usually use the term ‘bad’ as a temporary descriptive term in such situations.) We therefore have $o_p(a_j)\le o_p(a)/2$ for $j\ne i$ and hence $2o_p(a_j)\le o_p(a)$.

share|cite|improve this answer
Thank you for the clarification. – Mat.S May 23 '12 at 18:19

Your Answer


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.