Factorization and Quadratic Non-Residue

Question

Suppose that I can always factor any number modulo $p$ into factors that are smaller than $f(p)$ where $f$ is some function.

Does that imply that the least quadratic non-residue is smaller than $f(p)$? and If so why?

Thanks

Answer 1

Yes it does. For there is a positive quadratic non-residue $b$ of $p$. If $b$ can be factored modulo $p$ as $a_1a_1\cdots a_k$, where $1\lt a_j\lt f(p)$, then since $$-1=(b/p)=(a_1/p)(a_2/p)\cdots (a_k/p),$$ at least one of the Legendre symbols $(a_j/p)$ must be $-1$. Any such $a_j$ is a positive quadratic non-residue of $p$ less than $f(p)$.

Answer 2

Thanks. and now I see this from a different perspective.

A simple proof can be done by contradiction.

Denote by $k$ to be the least quadratic non-residue, if $k < f(p)$ we are done. Otherwise $k \geq f(p)$. Factor $k$ into factors that are all smaller than $f(p)$. Since $k$ is a non-residue then one of the factors must also be a non-residue and is smaller than $k$ so we get a contradiction.