Let for integers $n\geq 1$ the Euler's totient function $\varphi(n)$. On the other hand one knows the so-called Bernoulli inequality, see for example this MathWorld. This morning I wondered about two puzzles that I've created involving previous inequality and two well known sequences of integers (in this post the arithmetic function $\varphi(n)$). These puzzles do not have a context in this inequality,
my creation or definition of the puzzles was artificious and has no a special mathematical meaning, but I am curious about if it is possible to deduce a solution.

Definition. I define the sequence of integers $n\geq 1$ such that $\varphi(1+n^2)$ divides $\varphi\left((1+n)^n\right)$.

Computational fact. Our sequence starts with $$1,3,5,9,13,25,45,47,\ldots$$ and seems that there isn't in The On-Line Encyclopedia of Integer Sequences.

Question. Is it possible to deduce that previous sequence has infinitely many terms? What is you reasoning or heuristic? Many thanks.

I think that it is very difficult. I've observed that in our sequence there are primes, and also some perfect squares.


Suppose, $n+1=2p$ and $n^2+1=2q$ with odd primes $p$ and $q$

Then, we have $$\phi((n+1)^2)=\phi(4p^2)=2p(p-1)$$

and $$\phi(n^2+1)=q-1$$

But we have $2q-1=(2p-1)^2=4p^2-4p+1$ , hence $2q-2=4p^2-4p$, hence $q-1=2p^2-2p=2p(p-1)$ , so we get $\phi((n+1)^2)=\phi(n^2+1)$ , which implies $\phi(n^2+1)|\phi((n+1)^n)$ for $n\ge 2$

Hence we have infinite many entries in the sequence, if there are infinite many numbers $n$, such that both $\frac{n+1}{2}$ and $\frac{n^2+1}{2}$ are prime. With $n=2k+1$ this boils down to the condition that for infinite many $k$, the numbers $k+1$ and $2k^2+2k+1$ are both prime. And this is a consequence of the Bunyakovsky-conjecture.

Hence we proably have infinit many $n$ doing the job.

  • 1
    $\begingroup$ Many thanks for your great answer. Feel free to continue studying previous sequence: my thoughts were that it was impossible to say anything about the sequence. $\endgroup$ – user243301 Jan 8 '18 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy