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](https://en.wikipedia.org/wiki/Ramanujan%27s_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](https://mathoverflow.net/questions/245370/there-at-least-4-divisors-of-n-1-which-do-not-divide-phin-if-n-is-a-com).



Congruences for the non-divisors of Euler's $\phi(n)$
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](https://math.stackexchange.com/questions/906159/a-number-is-a-perfect-square-if-and-only-if-it-has-odd-number-of-positive-diviso))


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](https://math.stackexchange.com/questions/702550/why-is-eulers-totient-function-always-even)). 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. 


