Let $n=2^k\prod _1 ^m q_i \cdot a^2$ There exists infinitely many primes $p$ for which $2^k\prod _1 ^m q_i$ is non-residue mod $p$ (by Chinese remainder theorem and Dirichlet's theorem), hence $n$ has to be a square and obviously all such numbers satisfy conditions of the problem.

We can avoid Dirichlet (the only analytical step) by using quadratic reciprocity for Jacobi symbols (the rest of the proof being the same). Here an adapted copy of more or less the same from a post of mine on MathLinks: Assume that $n$ isn't a square, but a square $\mod $ all primes $>n$. Let $n=2^s b = 2^s p_1^{v_1} p_2^{v_k} ... p_k^{v_k}$ be the prime factorisation and $b$ it's greatest odd factor. Since $n$ is not a square, either (w.l.o.g.) $v_1$ is odd or $s$ is odd. 1. case: all $v_i$ are even, so $s$ is odd. Then simply taking an integer $q$ (coprime to all primes $\leq n$) not dividing $n$ and $\equiv 3\mod 8$ gives $\left( \frac{n}{q} \right) = \left( \frac{2^s}{q} \right) \left( \frac{b}{q} \right) = (-1)^s = -1$. 2. case: $v_1$ is odd. Now let $c$ be a quadratic non-residue $\mod p_1$ and take an integer $q$ (coprime to all primes $\leq n$) such that $q \equiv 1 \mod 8$, $q \equiv c \mod p_1$ and $q \equiv 1 \mod p_i$ for all other $p_i$. Then we get: $\left( \frac{n}{q} \right) = \left( \frac{2}{q} \right)^s \left( \frac{p_1}{q} \right)^{v_1} \left( \frac{p_2}{q} \right)^{v_2} ... \left( \frac{p_k}{q} \right)^{v_n} = \left( \frac{q}{p_1} \right)^{v_1} \left( \frac{q}{p_2} \right)^{v_2} ... \left( \frac{q}{p_k} \right)^{v_k}=(-1)^{v_1}=-1$. In both cases, $n$ is not a quadratic residue $\mod q$, thus not for at least one of it's prime divisors. This contradicts the assumption of $n$ being a square $\mod$ all primes $>n$. There are some tough ones: 1. If $n$ is a $k$-th power $\mod $ all primes $p>n$, then: - $8 \nmid k$ ; then $n$ is a $k$-th power of an integer. - $8 | k$ ; then $n$ is a $\frac{k}{2}$-th power of an integer. 2. If $n$ is a power of $2$ $\mod$ all primes $p>n$, then $n$ is also a power of $2$ seen as an integer.

ZetaX wrote: We can avoid Dirichlet (the only analytical step) by using quadratic reciprocity for Jacobi symbols (the rest of the proof being the same). Here an adapted copy of more or less the same from a post of mine on MathLinks: Assume that $n$ isn't a square, but a square $\mod $ all primes $>n$. Let $n=2^s b = 2^s p_1^{v_1} p_2^{v_k} ... p_k^{v_k}$ be the prime factorisation and $b$ it's greatest odd factor. Since $n$ is not a square, either (w.l.o.g.) $v_1$ is odd or $s$ is odd. 1. case: all $v_i$ are even, so $s$ is odd. Then simply taking an integer $q$ (coprime to all primes $\leq n$) not dividing $n$ and $\equiv 3\mod 8$ gives $\left( \frac{n}{q} \right) = \left( \frac{2^s}{q} \right) \left( \frac{b}{q} \right) = (-1)^s = -1$. 2. case: $v_1$ is odd. Now let $c$ be a quadratic non-residue $\mod p_1$ and take an integer $q$ (coprime to all primes $\leq n$) such that $q \equiv 1 \mod 8$, $q \equiv c \mod p_1$ and $q \equiv 1 \mod p_i$ for all other $p_i$. Then we get: $\left( \frac{n}{q} \right) = \left( \frac{2}{q} \right)^s \left( \frac{p_1}{q} \right)^{v_1} \left( \frac{p_2}{q} \right)^{v_2} ... \left( \frac{p_k}{q} \right)^{v_n} = \left( \frac{q}{p_1} \right)^{v_1} \left( \frac{q}{p_2} \right)^{v_2} ... \left( \frac{q}{p_k} \right)^{v_k}=(-1)^{v_1}=-1$. In both cases, $n$ is not a quadratic residue $\mod q$, thus not for at least one of it's prime divisors. This contradicts the assumption of $n$ being a square $\mod$ all primes $>n$. There are some tough ones: 1. If $n$ is a $k$-th power $\mod $ all primes $p>n$, then: - $8 \nmid k$ ; then $n$ is a $k$-th power of an integer. - $8 | k$ ; then $n$ is a $\frac{k}{2}$-th power of an integer. 2. If $n$ is a power of $2$ $\mod$ all primes $p>n$, then $n$ is also a power of $2$ seen as an integer. Thank you thank you thank you! You wouldn't believe how long i have been trying to find the answer to this! Thank you so much ZetaX, Laura