congruences
Find a solution or show that there is none: $x^2 \mod 7 = 3\;(x\in \mathbb{Z})$
I've tried different ways to approach this problem, such as rewriting the equation in the form $x^2 = 7k+3$, where k is an integer.
Then it becomes proving that $\sqrt{7k+3}$ is not an integer (for $k\in \mathbb{Z}$), or finding a solution to it. But here, I've been stuck.
Can anybody help me with this?
Thank you for your time.
Some rearranging and reduction: \begin{align} 8x + 10y &\equiv 8 \pmod 7 \iff \\ x + 3y + 7x + 7y &\equiv 1 + 7 \pmod 7 \iff \\ x + 3y &\equiv 1 \pmod 7 \end{align}
The following will apply the algorithms for linear congruence equations and for linear Diophantine equations (because it was asked) to get solutions. I use the algorithms here because they are guaranteed to give the number of solutions and all solutions.
Solution as linear congruence equation
We can interpret this as linear congruence $a X \equiv b \pmod m$ in the integer unknown $X$: \begin{align} x + 3y &\equiv 1 \pmod 7 \iff \\ 7x + 3y &\equiv 1 + 6x \pmod 7 \iff \\ 3y & \equiv 1 + 6x \pmod 7 \quad (*) \end{align}
For this there exists an solution algorithm (link) to find all solutions from $\mathbb{Z}_m$.
The linear congruence $(*)$ has $d = \gcd(a,m) = \gcd(3, 7) = 1$ and $d \vert b$ and $d$ solutions (per fixed $x$) in $\mathbb{Z}_m$. One uses the extended Euclidean algorithm to find $s, t$ with $1 = 3s + 7t$, e.g. $s = -2$, $t = 1$. We get the only solution from $\mathbb{Z}_7$: $y = (-2) (1+6x) \bmod 7$ or: $$ y = (5 + 2x) \bmod 7 $$ Regarding $\mathbb{Z}$, the general solution is $$ (x,y) = (x, ((5 + 2x) \bmod 7) + 7k) \quad (k \in \mathbb{Z}) \quad (\#) $$
Some example solutions
The colour encodes different $k$ parameters.
$$ (x, y) \in \{ \ldots (-2, 1), (-1, 3), (0, 5), (1, 0), (2, 2), (3, 4), (4, 6), (5, 1), (6, 3), (7, 5), (8, 0), \ldots \} $$
Test
\begin{align} x + 3 y &\equiv 1 \pmod 7 \iff \\ x + 3(5 + 2x) &\equiv 1 \pmod 7 \iff \\ 7 x + 15 &\equiv 1 \pmod 7 \iff \\ 7 x + 14 &\equiv 0 \pmod 7 \iff \\ 0 &\equiv 0 \pmod 7 \end{align}
Solution as Diophantine equation
We interpret the congruence as linear Diophantine equation $a X + b Y = c$ in the integer unknowns $X$ and $Y$: $$ x + 3y \equiv 1 \pmod 7 \iff \\ x + 3y = 1 + 7 k \quad (k \in \mathbb{Z}) $$ For this there exists an algorithm as well (link).
We have $d = \gcd(a, b) = \gcd(1,3) = 1$. So $d \vert c = 1+7k$. We set $m = 1 + 7k$. Then we need $s, t$ for $s + 3t = 1$, e.g. $s=1$, $t = 0$. This gives the particular solution $x_0 = ms = 1 + 7k$, $y_0 = mt = 0$, thus $$ (x_0, y_0) = (1+7k, 0) $$ All solutions (for fixed $k \in \mathbb{Z}$) are $$ (x_n, y_n) = (x_0 + bn, y_0 - an) = (1+7k+3n,-n) \quad (n \in \mathbb{Z}) $$ E.g. for $k=0, n=1$ we have the solution $(4,-1)$. But we want to have a similar solution like $(\#)$, in terms of $x$:
Now $7k + 3n = x - 1$ is another Diophantine equation, because $d=\gcd(7,3) = 1$ and $d\vert x - 1$ we have infinite solutions. We get $s = 1$, $t=-2$ and $k_0 = x-1$, $n_0=-2(x-1)=2-2x$, $k_i = x-1+3i$, $n_i = 2-2x - 7i$.
So we have the solutions \begin{align} (x,y) &= (1+7k+3n,-n) \\ &= (1+7(x-1+3i)+3(2-2x-7i), -(2-2x-7i)) \\ &= (1+7x-7+21i+6-6x-21i, -2+2x+7i) \\ &= (x, 2x-2+7i) \quad (i \in \mathbb{Z}) \quad (\#\#) \end{align} So this looks more similar to $(\#)$. And $(5+2x)\bmod 7 = (2x + 5) \bmod 7 = (2x-2) \bmod 7$. Thus because of $2x-2 = 7q + ((2x-2) \bmod 7)$ for some $q$ we got the same solution sets, once we add multiples of $7$.
The solution looks the same, the colour encodes different $i$ parameters. So we see the parametrization is different, but set seems the same, looking at the $[0,6]\times[0,6]$ with its $7$ solutions.
Fermat's theorem tells us that $n^7 \equiv n \bmod 7$ and so $7$ divides $n^7-n=n(n^3-1)(n^3+1)$.
Since $7$ is prime, $7$ must divide one of the factors:
Best Answer
The question of whether the equation $$x^2 \equiv 3 \pmod{7}$$ has any solutions is equivalent to the question is $$x^{2} = 3$$ solvable for $x \in \mathbb{Z}/ 7\mathbb{Z}$.
So, as Donald Splutterwit mentions in the comments, we can calculate the value of $x^{2}$ for each $x \in \mathbb{Z}/ 7\mathbb{Z}$ and check whether it is equal to $3$.
In general, the question of whether for $p$ prime and fixed integer $n$ the equation, $$x^{2} \equiv n \pmod{p}$$ has a solution is answered by Gauss's quadratic reciprocity.
$\textbf{Edit:}$
To expand upon the answer, suppose that there exists $x\in \mathbb{Z}$ such that $$x^{2} \equiv 3 \pmod{7},$$ then $7 \mid (x^{2} - 3)$, which implies that there is an $a\in \mathbb{Z}$ so that $$x^{2} - 3 = 7a.$$
Then, by the Euclidean division algorithm, $x = 7k+r$ for some $0 \leq r \leq 6$. Substituting this expression into the above formula yields $$49x^{2} + 14kr + r^{2} - 3 = 7a,$$ which is equivalent to saying that there is $a^{'} \in \mathbb{Z}$ so that $$r^{2} - 3 = 7a^{'}.$$ (Just bring the terms on the LHS divisible by $7$ to the RHS and factor out a $7$.)
Now, we see that if $7 \mid (x^{2} - 3)$, then $7 \mid (r^{2} - 3)$ for some $0 \leq r \leq 6$.
So, to show that $7 \nmid (x^{2} - 3)$ for all $x\in \mathbb{Z}$, it is enough to show that $7 \nmid (r^{2} - 3)$ for $r \in \{0,1,\ldots, 6\}.$