Congruences for the non-divisors of Euler's $\phi(n)$

Question

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.

Answer 1

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:

$$\tau(n)=\sigma_0(n-1)-\sigma_0(\gcd(\varphi(n),n-1))$$

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.

Answer 2

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.