Maths Olympiad Prep

Library / /176 of 299

Number theory Difficulty 6.7 National Olympiad Prove it Iran

Let xx, yy be two unknown natural numbers less than 100!100!. Prove that there are natural numbers mm and nn such that knowing the value of φ(d(my))+d(φ(nx))\varphi(d(my)) + d(\varphi(nx)) would lead to the uniquely determination of the values xx and yy.

(Note. φ(n)\varphi(n) is the number of positive integers that are less than and co-prime to nn, and d(n)d(n) is the number of positive divisors of nn.)

Solution

Notice that we can find a good NN such that after knowing d(Nx)d(Nx) then xx can uniquely be determined. For this reason, we shall provide two different approaches;

1st approach. Let p1<p2<<ptp_1 < p_2 < \dots < p_t be all the primes less than 100!100! such that p1R>100!p_1^R > 100!. Now, for each ii, choose large enough primes qijq_{ij} and 1jR1 \le j \le R and put N=p1α1ptαtN = p_1^{\alpha_1} \cdots p_t^{\alpha_t} such that aij(modqij)a_i \equiv -j \pmod{q_{ij}}, j=1,,Rj = 1, \dots, R. Now, if d(Nx)d(Nx) is divisible by qijq_{ij} it follows that vpi(x)=jv_{p_i}(x) = j and this would help us to uniquely determine xx.

2nd approach. Let us denote by p1,,ptp_1, \dots, p_t the prime divisors dividing xx. Then, x=i=1tpiαix = \prod_{i=1}^t p_i^{\alpha_i}, αi0\alpha_i \ge 0. Then if N=i=1tpiβiN = \prod_{i=1}^t p_i^{\beta_i} it follows that d(Nx)=i=1t(1+αi+βi)d(Nx) = \prod_{i=1}^t (1 + \alpha_i + \beta_i). Letting βi=x2i1\beta_i = x^{2^{i-1}}. Considering P(x)=i=1t(1+αi+x2i)P(x) = \prod_{i=1}^t (1 + \alpha_i + x^{2^i}) then, degP(x)=2t1\deg P(x) = 2^t - 1 and the coefficient of x2t2j1x^{2^t - 2^{j-1}} is equal to 1+αj1+\alpha_j. Take n>i=1t(1+αi)n > \prod_{i=1}^t (1+\alpha_i) then P(n)P(n) will be a number in base nn that all of its digits can uniquely be determined by αi\alpha_i. So, it remains to choose, n>i=1t(1+ai)n > \prod_{i=1}^t (1+a_i) where ai=maxiAαia_i = \max_{i \in A} \alpha_i and βi=n2i1\beta_i = n^{2^{i-1}}.

Now, putting T=100!NT = 100!N and then d(φ(Tx))=d(φ(100!))Nxd(\varphi(Tx)) = d(\varphi(100!))Nx. Plugging m=pS1Nm = p^{S-1}N where t=qk=1100!d(kN)t = q \prod_{k=1}^{100!} d(kN) for some sufficiently large primes pp and qq. Then
φ(d(my))=(q1)d(Ny)φ(k=1100!d(kN)) \varphi(d(my)) = (q-1)d(Ny)\varphi\left(\prod_{k=1}^{100!} d(kN)\right)
It follows that if we consider φ(d(my))+d(φ(Tx))(modq1)\varphi(d(my)) + d(\varphi(Tx)) \pmod{q-1} we can determine d(φ(Tx))d(\varphi(Tx)) and then determine xx.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.