Competition problem — Number theory

Library / /5 of 17

Number theory Difficulty 5.4 AIME, harder Prove it Mongolia

Let $\phi(n)$ denote the number of positive integers less than or equal to a given integer $n$ that are relatively prime to $n$ . For example, $\phi(6) = |\{1, 5\}| = 2$ and $\phi(1) = |\{1\}| = 1$ .
Let $a, b, c, d$ be nonnegative integers such that $\phi(2^a(2b+1)) = 2^c(2d+1)$ . If $b \ge 1$ then show that
(1) $a \le c$ and,
(2) $b \ge 2d + 1$ .

Solution

Consider the prime factorization $2b+1 = (2b_1+1)^{\alpha_1} \dots (2b_l+1)^{\alpha_l}$ , where $\alpha_i$ are the exponents. Then
$\varphi(2b+1) = 2^l(2b_1+1)^{\alpha_1-1} \dots (2b_l+1)^{\alpha_l-1}b_1 \dots b_l.$
It is clear that $l \ge 1$ since $b \ge 1$ .
(i) The case $a=0$ is clear. So assume that $a \ge 1$ . Then $c \ge a-1+l \ge a$ .
(ii) By the given condition we get that $\frac{2d+1}{2b+1} \le \frac{b_1}{2b_1+1} \cdots \frac{b_l}{2b_l+1} < \frac{1}{2}$ , hence $2d+1 \le b$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.