If in a random question, I see:
$1)\:\: x^2 = a\pmod p$, $p$ is a prime.
$2)\:\: a$ is quadratic residues $(QR)$.
How can I conclude that $(a, p)=1$ ? What is missing to determine that? I learned in class the opposite direction: If $p$ is prime, $(a, p)=1$ and $a$ is perfect square modolo $p$, then $a$ is $QR$.
In other words, what do I gain if a number is Quadratic residues?
Thanks!
"a is a quadratic residue mod $p$" means $\exists x$ such that $x^2=a$ mod $p$ and $(a,p)=1$. That's the definition.
If $p|a$ and $x^2=a$ then you call $a$ a multiple of $p$. Every multiple of $p$ has such an $x$, because $x=0$ satisfies that equation, so in that case you're not actually pointing anything out by calling it a QR.