# Euler Totient Integer Remainder Sum Lemma

My question was:

Prove that the sum of the remainder of $$N$$ divided by $$\phi(N-1)$$ and the remainder of the division of $$N - 1$$ by $$\phi(N)$$ is always odd for $$N \gt 3$$.

This is my attempt thus far:

let the sum of remainder of $$N$$ divided by $$\phi(N - 1)$$ and the remainder of $$N - 1$$ divided by $$\phi(N)$$ be $$S_N$$.

knowing that one of terms of $$S_N$$ must be:

$$s_0=2\Bigl\lfloor-\frac {1}{2}\Bigr(\Bigl\lfloor\frac {N}{\phi(N-1)} \Bigr\rfloor\phi(N-1)-1+\Bigl\lfloor \frac {N-1}{\phi(N)}\Bigr\rfloor\phi(N)\Bigl)\Bigr\rfloor$$

and from the observation such a term is clearly an even number,we that deduce that the sum of the remaining terms must be odd in order for the sum $$S_N$$ to be odd. Denoting all remaining terms collectively as $$s_1$$:

$$s_1=\Bigl(\frac {N}{\phi(N-1)}-\Bigl\lfloor\frac {N}{\phi(N-1)} \Bigr\rfloor\Bigr)\phi(N)+\Bigl(\frac {N-1}{\phi(N)}-\Bigl\lfloor\frac {N-1}{\phi(N)} \Bigr\rfloor\Bigr)\phi(N-1)-1$$

We can therefore say that if $$s_1$$ is an odd number,$$S_N$$ is then the sum of an odd and even number, therefore also odd.

knowing $$\phi(N-1)$$ & $$\phi(N)$$ to always be even numbers for all N>2 affirms that $$s_1$$ is indeed odd, therefore we can now conclude that $$S_N$$ is also odd for all $$N \gt 2$$.