If $n$ is composite, then $\phi(n) < n-1$: hence, there is at least one number $d$ which does not divide $\phi(n)$ but divides$(n-1)$. We shall call $d$ the totient divisor of $n$. The purist will say that totient non-divisor is a more appropriate name but for the sake of simplicity we shall stay with totient divisor.

Let $\tau(n)$ be the number of totient divisors of $n$, i.e.,

\begin{equation} \tau(n) = \# \{d : d\mid (n-1), \ d \nmid \phi(n) \}. \end{equation}

Trivially, if $p$ is a prime then, $\tau(p) = 0$ and $\tau(p+1) = 1$. I observed the following congruences and I am looking for a proof or disproof of them:

\begin{equation} \tau(4n+3) \equiv 0 (\textrm{mod}\ 2) \end{equation}

\begin{equation} \tau(8n+5) \equiv 0 (\textrm{mod}\ 3) \end{equation}

Motivation: Notice the resemblance between the above congruences and Ramanujan's partition congruences

\begin{equation} p(5n+4) \equiv 0 (\textrm{mod}\ 5) \end{equation}

\begin{equation} p(7n+5) \equiv 0 (\textrm{mod}\ 7) \end{equation}

\begin{equation} p(11n+6) \equiv 0 (\textrm{mod}\ 11) \end{equation}

Note: This may be related to another question on totient divisors.


2 Answers 2


I can prove the first congruence, so $\tau(4k+3) \equiv 0 \mod 2$.

Let $\sigma_0(n)$ be the number of divisiors of $n$. Note that if $k \mid \varphi(n)$ and $k \mid n-1$ then $k \mid \gcd(\varphi(n),n-1)$. So $\tau(n)$ is the number of divisiors of $n-1$ that are not a divisor of $\gcd(\varphi(n),n-1)$. In other words, $$\tau(n)=\sigma_0(n-1)-\sigma_0(\gcd(\varphi(n),n-1))$$

Note that $\sigma_0(n)$ is odd if and only if $n$ is a square. (proof on Math.SE)

Since $n=4k+3$, we have $n-1=4k+2$ which is never a square. So $\sigma_0(n-1)$ is even.

Note that $\varphi(n)$ is even for $n>2$. (proof on Math.SE). Therefore $2 \mid \gcd(\varphi(n),n-1)$. However, $4 \nmid n-1$, since $n-1=4k+2$ for an integer $k$. So $\gcd(\varphi(n),n-1)$ is also not a square. Hence $\sigma_0(\gcd(\varphi(n),n-1))$ is also even, and hence $\tau(n)$ is even for all $n=4k+3$.

To prove the second congruence, we will again use:


Note that since $n-1=8k+4$ for an integer $k$, $4 \mid n-1$ but $8 \nmid n-1$. So $3 \mid \sigma_0(n-1)$. (Proof: Write $n = p_1^{a_1} \dots p_l^{a_l}$, where $p_1, \dots, p_l$ are different primes. Then the number of positive divisors of $n$ is equal to $(a_1 +1)(a_2 + 1)\dots(a_l+1)$. Since $a_1=2$ if we take $p_1=2$, we have that $3$ divides the number of positive divisors of $n$. )

Now note that $n$ is odd. If $n$ is divisible by two different odd primes, then $\varphi(n)$ is divisible by 4. If $n$ is not divisible by two different odd primes, we have $n=p^l$ for an odd prime $p$ and an integer $l$. Note that $p^2 \equiv 1 \mod 8$ for all odd $p$ (proof: consider all possibilities of $p$ mod 8).

Hence $l$ must be odd and $p \equiv 5 \mod 8$. Since $p-1 \mid \varphi(n)$, we have that $4 \mid \varphi(n)$.

Hence $4 \mid \gcd(\varphi(n),n-1)$ but not $8 \mid \gcd(\varphi(n),n-1)$, so we also have $3 \mid \sigma_0(\gcd(\varphi(n),n-1))$. Hence also $3 \mid \sigma_0(n-1)-\sigma_0(\gcd(\varphi(n),n-1))=\tau(n)$.

Note: I added two links to Math.SE, because I consider them to be standard facts, but I just want to make sure that you have the proof if you don't know these facts.


I think both congruences are essentially trivial: As $\varphi(4n+3)$ is even and $(4n+3)-1$ is $2$ times an odd number, the divisors which are counted come in pairs $t,2t$, where $t$ is odd.

Similarly for the second congruence: $(8n+5)-1$ is $4$ times an odd number, while $\varphi(8n+5)$ is divisible by $4$ (for otherwise $8n+5=p^m$ for $p\equiv3\pmod{4}$ which cannot hold), so the divisors come as triples $t,2t,4t$ for certain odd $t$'s.


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.