HINT $\ $ Use the Chinese Remainder Theorem to reduce to the prime power case, and then use Hensel's lemma to reduce to the prime case. In fact, in this manner, one may prove the following generalized Euler criterion.
THEOREM $\ $ Let $\rm\ a,\:n\:$ be integers, with $\rm\:a\:$ coprime to $\rm\:n\ =\ 2^e \:p_1^{e_1}\cdots p_k^{e_k}\:,\ \ p_i\:$ primes.
$\rm\quad\quad \ x^2\ =\ a\ \ (mod\ n)\ $ is solvable for $\rm\:x\:$
$\rm\quad\quad \: \iff\ \ \: a^{(p_i\ -\ 1)/2} \ \ \equiv\ \ 1\ \ (mod\ p_i)\quad\quad\ \ $ for all $\rm\ i\le k$
$\quad\quad\ $ and $\rm\quad\ \ e>1 \:\Rightarrow\: a\equiv 1\ \ (mod\ 2^{2+\delta}\:),\ \ \ \delta = 1\ \ if\ \ e\ge 3\ \ else\ \ \delta = 0$
Proof: See Ireland and Rosen, A Classical Introduction to Modern Number Theory, Proposition 5.1.1 p.50.
Sorry for this being very non-rigorous and not very elegant either.. as a high schooler I don't know many "high powered" tools that I could use to solve this.
Let's try to find $n$ which don't fit the statement.
Proposition: We'll get our best bet at falsifying the statement among primorials, i.e., those numbers of the form $\displaystyle \prod_{n = 1}^k p_n$
Consider when it is not a primorial.
Case 1: We add a $p_i$ to our primorial $p_k \#$ with $i < k$. In other words, $n$ has a repeated factor. Then $p_i \phi(n) = \phi (np_i)$. Thus, by doing this we increase the left hand side by $p_i$ while increasing our right hand side only by $\sqrt p_i$, so this is unproductive. Conclusion, we have at most of one of any prime factor in $n$.
Case 2: What if we didn't take the smallest primes. What if we changed a factor $p_i$ in $p_k \#$ into a $p_j$ with $i < k <j$? Then we would increase the left hand side by a factor of $(\frac{p_j}{p_i})(\frac{p_i}{p_i-1})(\frac{p_j-1}{p_j})$ while increasing the left hand side by a lesser factor of $\sqrt{\frac{p_j}{p_i}}$. Conclusion, we take the smallest primes we can.
Furthermore, once we find one primorial that works for the statement, all further primorials work as well. Consider if $p_i \#$ doesn't work, i.e. $\phi(p_i \#) \geq \sqrt{p_i \#}$. Then $\phi (p_{i+1} \#) = \phi(p_{i+1})\phi(p_i \#) \geq \sqrt{p_{i+1}} \sqrt{p_i \#}$, since $\phi(p_{i+1}) = p_{i+1} - 1 \geq \sqrt{p_{i+1}}$ for all $i \geq 1$
So, by inspection we find $n = 2, n = 6$ don't work. $n = 24$ works because $6 \geq \sqrt{24}$, so no further primorials work either.
To finish, we just need to do some inspection in $n =2$ and $n = 6$ to make sure that variations of them work. For $n = 2$, we check $2^2$, and find that $\phi (4) = 2 \geq 2$ works. For $n = 6$, we check $2^2 \times 3$ and $2 \times 3^2$, and find that both of them work. Thus, $n = 2, n = 6$ are the only integers $n$ which do not satisfy the statement.
Best Answer
Suppose $4k+3=p^{\alpha}$, where $p$ is a prime. Then $p \equiv 3 \mod 4$ (otherwise $p^{\alpha}\equiv 1\mod 4$). Thus, $3\equiv p^{\alpha}\equiv 3^{\alpha} \mod 4 \Longrightarrow \alpha$ is odd. Thus, $$\sigma(p^{\alpha})= 1+p+p^2+...+p^{\alpha}\equiv 1+3+3^2+...+3^{\alpha}\equiv 1+(-1)+(-1)^2+...+(-1)^{\alpha}\mod 4$$ Since $\alpha$ is odd, the above sum is $0$.
Now if $n=4k+3$ is not a prime power, then it can be written as a product of prime powers. Since $n\equiv 3\mod 4$, atleast one of the prime powers must be $3\mod 4$, and since $\sigma$ is multiplicative the result follows.