Elementary number theory, compute this sum My first problem is the following: prove that $4|\sigma(4n+3)$ for any positive integer $n$.
This is what I tried:
if $1\le m\le n$, then  $\sigma(n)=\sum_{\gcd(n,m)=m}m;$
Now the sum of all integers less than $n$ and relative prime to it is $s=\frac{1}{2}n\phi(n)$. Hence $\sigma(n)=1+\sum_{1}^nm-s-\sum_{\gcd(n,m)=k\ne m}m$ (here $k\ne1$). So our problem reduces to find the last writtem sum...hints? If someone knows a better way to solve this, he's welcome. But I'd like someone other could help me find that sum because I'm still curious.
 A: Outline: Let $N=4n+3$. Then there is a prime $p$ of the form $4k+3$ such that the largest $e$ such that $p^e$ divides $N$ is odd. 
Now show that $4$ divides $\sigma(p^e)$, and use the multiplicativity of $\sigma$.
A: Given $N\equiv -1\pmod{4}$, we have $p\mid N$ for some prime $p\equiv -1\pmod{4}$: odd primes can only be $\pm 1\pmod{4}$, so if any prime divisor of $N$ would be $\equiv 1\pmod{4}$, $N$ would be $\equiv 1\pmod{4}$ too, giving a contradiction. For the same reason, we may assume that the greatest $h$ such that $p^h\mid N$, i.e. $\nu_p(N)$, is odd, but in such a case:
$$ \sigma(p^h) = 1+p+\ldots+p^h = (1+p)\left(1+p^2+\ldots+p^{h-1}\right) $$
so $(p+1)\mid \sigma(N)$ and $4\mid \sigma(N)$ follows.
We may also notice that if $N$ is odd, $\nu_2(\sigma(N))$ is at least the number of prime divisors of $\frac{N}{\square(N)}$, where $\square(N)$ is the greatest square dividing $N$, then consider a few cases.
A: Let $S(n)$ be the set of all positive integers less than or equal to $n$ that are coprime to $n$.  For $n>1$, show that, for $k=1,2,\ldots,n$, $k\in S(n)$ if and only if $n-k\in S(n)$.
