In this post we denote the Dedekind psi function as $\psi(m)$ for integers $m\geq 1$. This is an important arithmetic fuction in several subjects of mathematics. As reference I add the Wikipedia Dedekind psi function, and [1].

One has the definition $\psi(1)=1$, and that the Dedekind psi function can be represented for a positive integer $m>1$ as $$\psi(m)=m\prod_{\substack{p\mid m\\p\text{ prime}}}\left(1+\frac{1}{p}\right).$$

I've considered the following problem: compute composite numbers $n\geq 1$ satisfying the congruence $$n^2\equiv 1\text{ mod }\psi(n).\tag{1}$$

I don't know if this congruence is in the literature, I was thinking what congruences, and related problems, can be potentially interesting and that are similar than other that are in the literature (I was inspired in the form of the congruence studied in [2], currently I've no Guy's book to know if my congruence is in the literature, I think that isn't in the OEIS).

Question. A) I would like to know if there are infinitely many composite integers satisfying the congruence $(1)$. B) We can to count these solutions using the following arithmetic function $$C(X)=\#\{1\leq n\leq X:n\text{ is a composite number that satisfies }n^2\equiv 1\text{ mod }\psi(n)\}.$$ If it is possible state if we can say something about the number of these solutions, I mean the size of $C(X)$ as $1\leq X$ grows. Many thanks.

If these congruence and problems are in the literature please refer it in comments or answer these questions as a reference request, that I'm going to try to search and read those statements from the literature.

Claim. It's easy to prove (by contradiction) that the solutions $n$ are square-free integers (have no repeated prime factors).

Computational experiments. The first few solutions are $$55,161,209,551,649,1079,1189,2849,3401\ldots$$ Here there is a table that provide us how many of those solutions, for our problem, there are for the first few segments of the form $[1,10^k]$ $$ \begin{array}{c|l|c|r} X & C(X) & X & C(X) \\ \hline 10^2 & 1 & 10^5 & 33 \\ 10^3 & 5 & 10^6 & 56 \\ 10^4 & 12 & 10^7 & 96 \end{array} $$ thus here $X=10^k$, with $k$ integer $2\leq k\leq 7$.


[1] Tom M. Apostol, Introduction to analytic number theory, Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag (1976).

[2] Florian Luca and Michal Křížek, On the solutions of the congruence $n^2\equiv 1\text{ mod }\phi^2(n)$, Proceedings of the American Mathematical Society, Vol. 129, No. 8 (August, 2001), pp. 2191-2196.

  • $\begingroup$ For the secondary question only is required some idea about how grows $C(X)$ for large values of $X$ (the first question is if there exist infinitely many solutions for our problem). $\endgroup$ – user759001 May 27 at 10:22
  • $\begingroup$ Unrelated to our post is that I don't know if my congruence is the most interesting that one can to create, and I tried to think what congruences could be interesting as companion of those famous congruences that are in the literature for the Euler's totient function. $\endgroup$ – user759001 May 27 at 10:41
  • 1
    $\begingroup$ Below $10^8$ , there are $155$ solutions. $\endgroup$ – Peter May 27 at 11:48
  • $\begingroup$ Thanks you very much @Peter your calculations and knowledges are incredible. $\endgroup$ – user759001 May 27 at 12:07

In the case $$n=pq$$ with primes $\ p<q\ $ we have to satisfy $$(p+1)(q+1)\mid p^2q^2-1$$

We have $$p^2q^2-1-(p^2-1)(q^2-1)=p^2+q^2-2$$ hence the divisibility is equivalent to $$(p+1)(q+1)\mid p^2+q^2-2$$

We have $$\frac{p^2+q^2-2}{(p+1)(q+1)}=\frac{p-1}{q+1}+\frac{q-1}{p+1}$$

This is equal to $2$ , hence a positive integer , if $$k(p-1)=(k-1)(q+1)$$ $$k(q-1)=(k+1)(p+1)$$ holds for some integer $k>1$

So $$kp+(1-k)q=2k-1$$ $$(k+1)p-kq = -2k-1$$

which has the solution $$p=4k^2-2k-1$$ $$q=4k^2+2k-1$$

If the generalized Bunyakovsky conjecture holds, there are infinite many $k$ such that $p$ and $q$ are both prime , hence there are very probably infinite many solutions.

| cite | improve this answer | |
  • 1
    $\begingroup$ Many thanks for your excellent answer. I would like to dedicate this your result and discussion to your excellence. I'm going to study it in next hours. $\endgroup$ – user759001 May 28 at 8:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.