Suppose that we have two natural numbers $x , y \le 100!$ with undetermined values. Prove that there exist natural numbers $m , n$ such that values of $x , y$ get uniquely determined according to value of $\varphi(d(my))+d(\varphi(nx))$. ( for each natural number $n$ , $d(n)$ is number of its positive divisors and $\varphi(n)$ is the number of the numbers less that $n$ which are relatively prime to $n$. ) Proposed by Mehran Talaei
Problem
Source: Iran Team selection test 2024 - P5
Tags: number theory
21.05.2024 17:21
Let $m_1$ and $n_1$ be natural numbers. Suppose we can determine the value of $y$ given $\phi(d(m_1 y))$ and the value of $x$ given $d(\phi(n_1 x))$. Let $100!\cdot( n_1+m_1)<p$ be a prime. Notice the pair $(m,n)=(p^{p-1}m_1,n_1)$ works as $x$ and $y$ can be uniquely determined given $ \phi(d(p^{p-1}m_1 y))+d(\phi(n_1 x))=(p-1)\cdot \phi(d(m_1y))+d(\phi(n_1x))$ (This is because $d(\phi(n_1x))<(p-1)$). Now it is sufficient to prove the following two claims: Lemma 1: If $S$ is a finite set of natural numbers, then there exists a natural number $\alpha$ such that any element $n$ of $S$ can be determined given $d(\alpha n)$ and every prime factor of $\alpha$ divides some element of $S$
Lemma 2: If $S$ is a set of natural numbers such that if a prime divides some element of $S$ then it divides all elements of $S$, then any element $n$ of $S$ can be determined given $\phi(n)$
Claim 1: There exists a natural number $m$ such that $y$ can be determined given $\phi(d(my))$ Let $\alpha$ be such that $y$ can be determined given $d(\alpha\cdot y)$. Let $p$ be a prime larger than $\alpha\cdot 100!$ then for a suitable choice of $C$, $y$ can be determined given $\phi(d(p^C\alpha\cdot y))=\phi((C+1)\cdot d(\alpha \cdot y))$. Claim 2: There exists a natural number $n$ such that $x$ can be determined given $d(\phi(nx))$ Notice that $x$ can be determined given $\phi(\text{lcm}[100!]\cdot x)$. Let $\alpha$ be such that $\phi(\text{lcm}[100!]\cdot x)$ can be determined given $d(\alpha\cdot\phi(\text{lcm}[100!]\cdot x))$. As $d(\alpha\cdot\phi(\text{lcm}[100!]\cdot x))=d(\phi(\alpha\cdot\text{lcm}[100!]\cdot x))$ we are done.
21.05.2024 18:09
Spam CRT and Dirichlet and use primes to recollect information. This isn't the best well written but NT guarentees that we can just keep using new primes by size until we win. Take $n = 2^{a_1} 3^{a_2} \dots$ such that $a_1 + 1, \dots, a_1 + 100!$ all have a giant unique prime factor $p$ so far unused, such that $p+1$ is also an unused prime factor. This can be done through CRT. Then mark all those prime factors, all prime factors of these numbers, and all divisors of the $p+1$. This means that we can uniquely determine $x$ from $\tau(d(nx))$. Now have some prime divide $y$ such that this prime is larger than all possible $\tau(d(nx))$. This allows us to determine the contributions of $\varphi(d(my))$ and $\tau(d(nx))$ by division algorithm on this large prime. We can similarly do the same thing with $m$ and a whole other set of primes $p_i \mid q_i - 1$ to finish.
21.05.2024 18:16
redacted