Consider the function $f_k:\mathbb{Z}^{+}\rightarrow\mathbb{Z}^{+}$ satisfying \[f_k(x)=x+k\varphi(x)\]where $\varphi(x)$ is Euler's totient function, that is, the number of positive integers up to $x$ coprime to $x$. We define a sequence $a_1,a_2,...,a_{10}$ with $a_1=c$, and $a_n=f_k(a_{n-1}) \text{ }\forall \text{ } 2\le n\le 10$ Is it possible to choose the initial value $c\ne 1$ such that each term is a multiple of the previous, if (a) $k=2025$ ? (b) $k=2065$ ? Proposed by chorn
Problem
Source: 2024 IRN-SGP-TWN Friendly Math Competition P4
Tags: function, number theory
02.08.2024 12:32
02.08.2024 15:52
Interesting problem.
02.08.2024 19:31
Common Remarks: Notice that if $x=p_1^{e_1}p_2^{e_2}\dots p_n^{e_n}$ then $$f_k(x)=\prod_{i=1}^{n}p_i^{e_i-1} \left(\prod_{i=1}^{n} p_i+k\prod_{i=1}^{n}(p_i-1) \right)$$ Answer for part a: The answer is no. Let $p$ be the largest prime divisor of $c$. Notice $k=2025=3^4\cdot 5^2$. If $p\nmid k$ then $p^e\nmid f(c)$ so we must have $p\leq 5$. The set of divisors of $c$ must be a subset of $\{2,3,5\}$ and the same must hold for $f(c)$. Notice however that at most one power of $3$ and $5$ divide the second product and $3^4\cdot 5^2$ divides the third product so the product within the parenthesis has at most one power of $3$ and $5$ dividing it. Thus the inner product will have a power of $2$ dividing it (by size). If $2\nmid c$ then $2$ will not divide the inner product. In order for the inner product to have more than one power of $2$ dividing it we must have that both parts have an equal highest power of two dividing them giving that the prime divisors of $c$ are $2$ and $3$ which makes the inner product evaluate to $2^3\cdot 3\cdot 13^2$ which has a prime divisor larger than $5$. Answer for part b: The answer is yes. Choose $c=3\cdot 5\cdot 7$. Then $f_{2065}(3\cdot 5\cdot 7)=(3\cdot 5\cdot 7+(5\cdot 7\cdot 59)(2\cdot 4\cdot 6))=3^4\cdot 5^2\cdot 7^2$. Clearly we then have $a_i|a_{i+1}$ for all $i$.
04.08.2024 09:50
The key is to consider the quotient $$\frac{f_k(x)}{x}=1+\frac{k\varphi(x)}{x}=1+k\prod_{p\mid x}\frac{p-1}p.$$Since $\frac{a_{i+1}}{a_i}=\frac{f_k(a_i)}{a_i}$, the product $k\prod_{p\mid a_i}\frac{p-1}p$ must be an integer. Consider the largest prime $p\mid a_i$, since it doesn't divide $q-1$ for any prime $q\leq p$, we must have $p\mid k$. (a) is the same as above, the prime factors of $a_i$ must be restricted to $\{2,3,5\}$ and checking all $8$ cases shows that $a_{i+1}$ must contain a prime factor larger than $5$, so this sequence may not be continued further. For (b), the sequence that I found was different: the set of prime factors of $a_i$ was chosen to be $\{2,7,29,59\}$ resulting in a quotient of $$1+2065\times\frac12\times\frac67\times\frac{28}{29}\times\frac{58}{59}=841=29^2.$$Thus the sequence $a_i=2\times7\times29^{2i}\times59$ satisfies the equation.