2^(n^2-1) for odd n?

Do you mean for even $n$?

Oh, yes, your right.

The official solution is more complicated - and I don't really understand how such a simple construction was overseen - but it has a cute claim: Given a positive integer $N$, there exists a squarefree positive integer $n$ whose prime divisors are all greater than $N$, and $\varphi(n)$ is a perfect square.

Where can I find the RMM SL pdf?

There is no public PDF.

Can you share it with us here (as you seemingly have the solutions)? I see no reason it to remain confidential (of course, unless you have the shortlist in paper form).

oVlad wrote: The official solution is more complicated - and I don't really understand how such a simple construction was overseen - but it has a cute claim: Given a positive integer $N$, there exists a squarefree positive integer $n$ whose prime divisors are all greater than $N$, and $\varphi(n)$ is a perfect square. For a proof of this claim, assume $N$ is sufficiently large, by PNT we have that the number of primes between $N$ and $2N$ ($K$) is at least $\frac{cN}{\ln(n)}$ for some positive $c$. Enumerate them $p_1, p_2, \cdots, p_K$. Note that any factor of $p_i - 1$ is at most $N$. Say $q_1, q_2, \cdots, q_k$ are the primes below $n$. To each prime $p_i$, assign it the $k$ tuple $(c_1, c_2, \cdots, c_k)$ where $c_j = \nu_{q_j}(p_i - 1)$. Clearly if some of these tuples add to the zero vector $\pmod 2$ then choose $n$ to be the product of those primes, so $\varphi(N)$ is a perfect square. But this must happen since otherwise $2^{K} \leqslant N$, a contradiction since $K \geqslant \frac{cN}{\ln(n)}$. Obviously PNT is overkill but you don't need that strong of a bound for this proof to work anyway.

My construction was $n=15 \cdot 2^{4k^2+4k}$, which also works since $\tau(n)=4(2k+1)^2$ and $\phi(n)=2^{4k^2+4k+2}$.

n=2^(4k^2-1) work

Trying out $n = p^k$ for a prime $p$, we would like $k+1 = m^2$ and $p^{k-1}(p-1) = t^2$, i.e. $p^{m^2-2}(p-1) = t^2$. Now it's clear that taking $p=2$ and $m$ to be even suffices.

L567 wrote: oVlad wrote: The official solution is more complicated - and I don't really understand how such a simple construction was overseen - but it has a cute claim: Given a positive integer $N$, there exists a squarefree positive integer $n$ whose prime divisors are all greater than $N$, and $\varphi(n)$ is a perfect square. For a proof of this claim, assume $N$ is sufficiently large, by PNT we have that the number of primes between $N$ and $2N$ ($K$) is at least $\frac{cN}{\ln(n)}$ for some positive $c$. Enumerate them $p_1, p_2, \cdots, p_K$. Note that any factor of $p_i - 1$ is at most $N$. Say $q_1, q_2, \cdots, q_k$ are the primes below $n$. To each prime $p_i$, assign it the $k$ tuple $(c_1, c_2, \cdots, c_k)$ where $c_j = \nu_{q_j}(p_i - 1)$. Clearly if some of these tuples add to the zero vector $\pmod 2$ then choose $n$ to be the product of those primes, so $\varphi(N)$ is a perfect square. But this must happen since otherwise $2^{K} \leqslant N$, a contradiction since $K \geqslant \frac{cN}{\ln(n)}$. Obviously PNT is overkill but you don't need that strong of a bound for this proof to work anyway. I am not sure about the last step - you have $K$ vectors (for each $p_i$ you have a vector) and each vector is in $\mathbb{Z}_2^k$. You want some of these vectors to add to zero, that is, linear dependent on $\mathbb{Z}_2^k$. Don't you need $K>k$ for this? A fix would be to choose $p_1,\cdots,p_K$ all primes in $[N\cdots,2M]$ for $N$ fixed and $M$ large, then $q_1.\cdots q_k$ would be all primes in $[1\cdots M]$. Then we are good as long as $\pi(2M)-\pi(N)>\pi(M)$, or $\pi(2M)-\pi(M)>\pi(N)$, which is true for some $M$ by PNT.

R8kt wrote: 2^(n^2-1) for odd n? oops lmao Let $p$ be an arbitrary odd prime. We construct some $n$ with $p$ as its largest prime divisor as follows. Initialize $n=p^3$, so $d(n)=4$ and $\varphi(n)=(p-1)p^2$. Now repeatedly consider the squarefree part of $\varphi(n)$ (initially this is the squarefree part of $p-1$). Let $q$ be the largest prime dividing it, and multiply $n$ by $q^2$. This multiplies $d(n)$ by $3$ and the largest prime dividing the squarefree part of $\varphi(n)$ strictly decreases. Repeat this until the squarefree part of $\varphi(n)$ isn't divisible by any odd primes, and stop. At this point, $n$ is odd. Furthermore, the squarefree part of $d(n)$ is either $1$ or $3$, and the squarefree part of $\varphi(n)$ is either $1$ or $2$. We take four cases: If the squarefree parts are $(1,1)$ then we're done. If the squarefree parts are $(3,1)$ then multiply by $2^{11}$, multiplying $d(n)$ by $12$ and $\varphi(n)$ by $2^{10}$, thus making them both squares. If the squarefree parts are $(1,2)$ then multiply by $2^8$, multiplying $d(n)$ by $9$ and $\varphi(n)$ by $2^7$, thus making them both squares. If the squarefree parts are $(3,2)$ then multiply by $2^2$, multiplying $d(n)$ by $3$ and $\varphi(n)$ by $2$, thus making them both squares. This finishes the problem. $\blacksquare$ For completeness, the process starting with $p=23$ is as follows. Initialize $n=23^3$, with $d(n)=4$ and $\varphi(n)=22\cdot 23^2$. Now multiply $n$ by $11^2$, making $d(n)=12$ and $\varphi(n)=20\cdot 11^2\cdot 23^2$. Then multiply $n$ by $5^2$, making $d(n)=36$ and $\varphi(n)=20^2\cdot 11^2\cdot 23^2$. This corresponds to the $(1,1)$ case and we're just done.

$n=10^{2t+1}$ works also. We have $d(n)=(2t+2)^2$ and $\varphi (n) = 5^{2t} \cdot 4 \cdot 2^{2t}$, both are perfect squares.

???