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 7 of 7: Count the divisors and finish part (b)

Previous step Next step

p< p+d<2p\le p^2\le n,\qquad z=p+\frac{p(p-1)}{d}\le p^2\le n,\qquad N_{\mathrm{choices}}=\tau(p-1)

Detailed analysis

For every divisor $d$ of $p-1$ , we have $d\le p-1$ , so $p<y=p+d<2p\le p^2\le n$ ; also $z=p+\frac{p(p-1)}{d}\le p^2\le n$ . Thus every divisor gives a valid choice, and the divisor parametrization is one-to-one, so the number of choices is the number of positive divisors of $p-1$ .