Maths Olympiad Prep

Library / /40 of 63

Number theory Difficulty 7.2 National olympiad, round 2 Prove it Japan

Find all positive integers nn such that ϕ(n)d(n)+1n\frac{\phi(n)^{d(n)} + 1}{n} is an integer and nϕ(n)1d(n)5\frac{n^{\phi(n)} - 1}{d(n)^5} is not. Here, ϕ(n)\phi(n) denotes the number of integers in {1,,n}\{1, \dots, n\} coprime to nn, and d(n)d(n) denotes the number of positive divisors of nn.

Solution

Let i=1mxi\prod_{i=1}^{m} x_i denote the product of mm real numbers x1,x2,,xmx_1, x_2, \dots, x_m. For any positive integer NN, let ord2N\text{ord}_2 N denote the maximum nonnegative integer \ell such that 22^\ell divides NN.

n=1n=1 does not meet the assumption since 1ϕ(1)1d(1)5=0\frac{1^{\phi(1)} - 1}{d(1)^5} = 0 is an integer. In the following we assume n2n \ge 2. If distinct prime numbers p1,p2,,pkp_1, p_2, \dots, p_k and positive integers e1,e2,,eke_1, e_2, \dots, e_k satisfy n=i=1kpiein = \prod_{i=1}^{k} p_i^{e_i}, then ϕ(n)=i=1kpiei1(pi1)\phi(n) = \prod_{i=1}^{k} p_i^{e_i-1}(p_i - 1).

When nn is even, the assumption that ϕ(n)d(n)+1n\frac{\phi(n)^{d(n)} + 1}{n} is an integer implies that ϕ(n)\phi(n) is odd, thus n=2n=2. On the other hand, n=2n=2 satisfies the assumptions since ϕ(2)d(2)+12=12+12=1\frac{\phi(2)^{d(2)} + 1}{2} = \frac{1^2+1}{2} = 1 and 2ϕ(2)1d(2)5=21125=132\frac{2^{\phi(2)} - 1}{d(2)^5} = \frac{2^1 - 1}{2^5} = \frac{1}{32}.

In the following we assume nn is odd and n3n \ge 3. The assumption that ϕ(n)d(n)+1n\frac{\phi(n)^{d(n)} + 1}{n} is an integer implies that nn and ϕ(n)\phi(n) are coprime, thus nn is square-free. Then n=i=1kpin = \prod_{i=1}^{k} p_i with distinct odd primes p1,,pkp_1, \dots, p_k, thus d(n)=2kd(n) = 2^k. Now we need the following lemma.

Lemma. For any odd integer x3x \ge 3 and any positive integer yy, there holds ord2(xy1)ord2(x1)+ord2y\text{ord}_2(x^y - 1) \ge \text{ord}_2(x-1) + \text{ord}_2 y.

Proof. Suppose y=2vsy = 2^v \cdot s with a nonnegative integer vv and a positive odd integer ss. Then xy1=(xs1)i=0v1(x2is+1)x^y - 1 = (x^s - 1) \prod_{i=0}^{v-1} (x^{2^i \cdot s} + 1). Since xs1=(x1)(xs1++x+1)x^s - 1 = (x-1)(x^{s-1} + \dots + x+1), ord2(xs1)ord2(x1)\text{ord}_2(x^s - 1) \ge \text{ord}_2(x-1).
Also, ord2(x2is+1)1\text{ord}_2(x^{2^i \cdot s} + 1) \ge 1 for any ii since xx is odd, thus we obtain ord2(i=0v1(x2is+1))v\text{ord}_2 \left( \prod_{i=0}^{v-1} (x^{2^i \cdot s} + 1) \right) \ge v.
Hence ord2(xy1)ord2(x1)+ord2y\text{ord}_2(x^y - 1) \ge \text{ord}_2(x-1) + \text{ord}_2 y. \blacksquare

The condition that nϕ(n)1d(n)5=nϕ(n)125k\frac{n^{\phi(n)} - 1}{d(n)^5} = \frac{n^{\phi(n)} - 1}{2^{5k}} is not an integer is equivalent to ord2(nϕ(n)1)<5k\text{ord}_2(n^{\phi(n)} - 1) < 5k. The above lemma implies that ord2(nϕ(n)1)ord2(n1)+ord2(ϕ(n))\text{ord}_2(n^{\phi(n)} - 1) \ge \text{ord}_2(n-1) + \text{ord}_2(\phi(n)). Since ϕ(n)d(n)+1n\frac{\phi(n)^{d(n)} + 1}{n} is an integer, for any pip_i there holds ϕ(n)2k1(modpi)\phi(n)^{2k} \equiv -1 \pmod{p_i}, thus ϕ(n)2k+11(modpi)\phi(n)^{2^{k+1}} \equiv 1 \pmod{p_i}. Let tit_i be the minimum positive integer tt such that ϕ(n)t1(modpi)\phi(n)^t \equiv 1 \pmod{p_i}. If a positive integer \ell satisfies ϕ(n)1(modpi)\phi(n)^\ell \equiv 1 \pmod{p_i}, then tit_i divides \ell; this is because when rr denotes the remainder of \ell modulo tit_i, then ϕ(n)ϕ(n)r1(modpi)\phi(n)^\ell \equiv \phi(n)^r \equiv 1 \pmod{p_i}, which implies r=0r=0 by the minimality of tit_i. Now tit_i divides 2k+12^{k+1} since ϕ(n)2k+11(modpi)\phi(n)^{2^{k+1}} \equiv 1 \pmod{p_i}. On the other hand tit_i does not divide 2k2^k since ϕ(n)2k1≢1(modpi)\phi(n)^{2^k} \equiv -1 \not\equiv 1 \pmod{p_i}. Hence we obtain ti=2k+1t_i = 2^{k+1}.

By the Fermat's little theorem ϕ(n)pi11(modpi)\phi(n)^{p_i-1} \equiv 1 \pmod{p_i}, thus 2k+12^{k+1} divides pi1p_i - 1. Hence ord2(ϕ(n))=i=1kord2(pi1)k(k+1)\text{ord}_2(\phi(n)) = \sum_{i=1}^{k} \text{ord}_2(p_i - 1) \ge k(k+1). On the other hand, by n1=i=1kpi1i=1k110(mod2k+1)n-1 = \prod_{i=1}^{k} p_i - 1 \equiv \prod_{i=1}^{k} 1 - 1 \equiv 0 \pmod{2^{k+1}} we obtain ord2(n1)k+1\text{ord}_2(n-1) \ge k+1. Therefore 5k>ord2(nϕ(n)1)ord2(n1)+ord2(ϕ(n))(k+1)25k > \text{ord}_2(n^{\phi(n)} - 1) \ge \text{ord}_2(n-1) + \text{ord}_2(\phi(n)) \ge (k+1)^2. Then we obtain k=1,2k=1, 2.

When k=1k=1 we obtain ϕ(n)=n1\phi(n) = n-1 and d(n)=2d(n) = 2, thus ϕ(n)d(n)+1n=(n1)2+1n=n2+2n\frac{\phi(n)^{d(n)} + 1}{n} = \frac{(n-1)^2 + 1}{n} = n-2 + \frac{2}{n} is not an integer, which contradicts the assumption. When k=2k=2, the condition 3+23ord2(n1)+ord2(ϕ(n))<523+2 \cdot 3 \le \text{ord}_2(n-1) + \text{ord}_2(\phi(n)) < 5 \cdot 2 implies that ord2(n1)=3\text{ord}_2(n-1) = 3 and ord2(ϕ(n))=6\text{ord}_2(\phi(n)) = 6. Since p11p_1-1 and p21p_2-1 are both multiples of 22+12^{2+1}, ord2((p11)(p21))=ord2(ϕ(n))=6\text{ord}_2((p_1-1)(p_2-1)) = \text{ord}_2(\phi(n)) = 6 implies ord2(p11)=ord2(p21)=3\text{ord}_2(p_1-1) = \text{ord}_2(p_2-1) = 3. Thus p1p29(mod16)p_1 \equiv p_2 \equiv 9 \pmod{16}. Hence n1=p1p210n-1 = p_1p_2-1 \equiv 0 (mod 16), which contradicts ord2(n1)=3ord_2(n-1) = 3. Thus there does not exist an odd integer n3n \ge 3 which satisfies the required conditions.

Hence the answer is n=2n = 2.

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.