Let $d(n)$ be the sum of positive integers divisors of number $n$ and $\phi(n)$ the quantity of integers in the interval $[0,n]$ such that these integers are coprime with $n$. For instance $d(6)=12$ and $\phi(7)=6$. Determine if the set of the integers $n$ such that, $d(n)\cdot \phi (n)$ is a perfect square, is finite or infinite set.
Problem
Source: Rioplatense 2011 #6 L3
Tags: Divisors, number theory, algebra
23.08.2017 01:36
27.02.2021 09:00
Bump this.
27.02.2021 09:23
Let $n$ be $5^{4k^2-1}$, where $p$ is a prime and $k\in\mathbb{Z^+}$. $d(n)=4k^2$ $\varphi(n)=4\times 5^{4k^2-2}$ Thus $d(n)\varphi(n)=16k^2\times 5^{4k^2-2}=(4k\times 5^{2k^2-1})^2$ is a perfect square, which means the answer is infinite. Edit: We can replace $5$ with any prime $p$ satisfying $p-1$ is a perfect square. Edit: @below sorry I misunderstood the problem. My solution was wrong.
27.02.2021 12:05
Scrutiny wrote: Let $n$ be $5^{4k^2-1}$, where $p$ is a prime and $k\in\mathbb{Z^+}$. $d(n)=4k^2$ $\varphi(n)=4\times 5^{4k^2-2}$ Thus $d(n)\varphi(n)=16k^2\times 5^{4k^2-2}=(4k\times 5^{2k^2-1})^2$ is a perfect square, which means the answer is infinite. Edit: We can replace $5$ with any prime $p$ satisfying $p-1$ is a perfect square. $d(n)$ is not the number of divisors, but rather the sum of divisors of $n$.
20.03.2021 18:34
Sorry for bumping, but can anyone solve it? Thanks!
22.03.2021 19:56
https://dgrozev.wordpress.com/2021/03/22/is-this-number-theory-rioplatense-mo-2011/
30.03.2021 21:50
Typos etc. fixed It's intuitively clear that this set has to be an infinite one, but assume it's not and let $\mathcal S$ be the set of all $n$ for which $$f(n):=\phi(n)\sigma(n)$$is a perfect square. Let $p_m$ be the largest prime dividing an element of $\mathcal S$ and let $$c_1, c_2, \dots, c_m$$be the smallest exponents of $$p_1<\cdots<p_m$$that $p_{i}^{c_i}\nmid n, n\in \mathcal S$, in particular $c_i=1$ for all $i>m$. Now let $p_M$ be the largest prime dividing one of $f(n), n\in\mathcal S$. We proceed by bounding the set of prime factors of the set $\mathcal K$ of values of $f$ attained at numbers formed by the elements of the set $$\{p_{1}^{c_{1}}, \dots, p_{M+1}^{c_{M+1}}\}$$namely $2^{M+1}-1$ non-zero numbers, say $$\mathcal{K}:= \{t_1, t_2, \dots, t_{2^{M+1}-1}\}$$. Lemma. There's no prime $p>p_M$ that $p\mid f(p_{i}^{c_i}), 1\le i\le M+1$. Proof. Distinguish two cases, if $1\le i\le m$ then it's clear by the definition of $M$. If $m+1\le i\le M$ : $$p\mid (p_{i}-1)(p_{i}+1), p\mid p_{i}-1\to p_{M}<p<p_{i}\le p_{M+1}$$absurd (the other case gives an analogous contradiction ). $\square$ Consider this set $\mathcal K$, and interpret each of its elements as a string of its exponents wrt $p_i$ modulo $2$ , and consider all the $2^{M}-1$ non-zero binary strings of length $M$. Then there're two $t_i, t_j$ that are assigned the same binary row. Thus $$f(t_i)f(t_j)=c^2, c\in \mathbb N$$Let $d=(t_i, t_j)$ and observe that (see def of $\mathcal K$) $$(d, \frac{t_i}{d})=(d, \frac{t_j}{d})=(\frac{t_i}{d}, \frac{t_j}{d})=1$$So, finally using the multiplicativity of $f$ : $$f(\frac{t_{i}t_{j}}{d^2})=f(\frac{t_i}{d})f(\frac{t_j}{d})=\frac{c^2}{(\phi(d)\sigma(d))^2}\in \mathbb Z$$is a perfect square and $\frac{t_{i}t_{j}}{d^2}\notin \mathcal S$ due to an obvious reason, contradiction. $\mathbb{Q.E.D}$