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$.


Your Answer

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

Browse other questions tagged or ask your own question.