Problem 3

Let

n>3

be an integer. Choose three numbers from

\{1,2,\ldots,n\}

. Using each once, together with addition, multiplication, and parentheses, form all possible combinations. (a) Show that if all three chosen numbers are greater than

n/2

, their values are all distinct. (b) Let

p

be a prime with

p\le \sqrt{n}

. Show that the number of choices whose smallest number is

p

and whose combination values are not all distinct is exactly the number of positive divisors of

p-1

Step 6 of 7: Parametrize the repeated-value choices in part (b)

Previous step Next step

x=p,\qquad (y-p)(z-p)=p(p-1),\qquad d=y-p\mid(p-1)

Detailed analysis

Set $x=p$ . From the equality criterion, $(y-p)(z-p)=p(p-1)$ . Since $y-p<z-p$ , we have $(y-p)^2<p(p-1)$ , hence $y-p<p$ ; because $p$ is prime, $p$ does not divide $y-p$ , so $d=y-p$ divides $p-1$ . Conversely, every positive divisor $d$ of $p-1$ gives $x=p$ , $y=p+d$ , $z=p+\frac{p(p-1)}{d}$ .