Is $7$ a Quadratic Residue mod 101?

Question

Question: Is $7$ a Quadratic Residue mod 101?

Attempt: Theorem 9.1 states that the number $a$ is a Quadratic Residue if and only if $a^{\frac{p-1}{2}} \equiv 1$ (mod $p)$.

Suppose $p=101,\frac{p-1}{2} =50,$ and $ a=7$

We need to find out whether or not the remainder will be one if we have

$7^{50} \equiv $ mod $(101)$

$(7^1) = 7$

By squaring both sides, we get $(7^1)^2 = (7)^2$

$7^2=49 $ which is close to the exponent fifty. Squaring both sides again, we have

$(7^2)^2 = (49)^2$

$7^4 = 49^2$

$7^4 = 2401$

Since we want a number that's less than 101, we need to subtract 2401 by a multiple of 101, so suppose we have $101 \times 20=2020$. Then, we have

$2401-2020 = 381$, and subtracting $303 = 101 \times 3$ from $381$ we have $78$

Now, squaring both sides, we have

$(7^4)^2 =78^2$

$7^8 = 78^2$

$7^8 = 6084$. Subtracting $6060 = 101 \times 60$ from $6084$, we have $24$

Squaring both sides, we have

$(7^8)^2 = 24^2$

$7^16 = 576$. Subtracting $ 505 = 101 \times 5$ from $ 576$ we get $71$, so squaring both sides we get ,

$(7^16)^2 = 71^2$

$(7^32) = 5041$

Subtracting $5050=101 \times 50$ from $5041$ we get $-9$.

So, now we need to write $50$ in base $2$. Therefore, we need the powers of $2$

$2^1 =2$

$2^2 = 4$

$2^3 =8$

$2^4 = 16$

$2^5 = 32$

We use $2^5 = 32$ because it is smaller than $50$, so $32$ divided by $50$ gives us a remainder of $18$ and this combination of $50=1 \cdot 32+18$

Now, we use $2^4=16$, so $16 $ divided by $18$ gives us a remainder of $2$ and a combination of $ 18=1 \cdot 16+2$.

Finally we use $2^1=2$ because we won't have a remainder afterwards and this crates a combination of $2=1 \cdot 2 +0$

Therefore, $50 = 1 \cdot 32 +1 \cdot 16 +1 \cdot 2$

or

$50 = 1 \cdot 2^5 +1 \cdot 2^4 +0 \cdot 2^3+0 \cdot 2^2+1 \cdot 2^1 + 0 \cdot 2^0$ which gives the binary of $110010$

Now this is where the problem begins to show up. Since I have $ 50=32+16+2$, that translates to $7^{50} = 7^{32} \cdot 7^{16} \cdot 7^{2}$. From our earlier calculations, $7^2 =49$ and $7^{16} = 71$, so why is $7^{32} = 92$? The only thing I can think of is that there is an error somewhere in the calculation for $7^{32}$??? Or am I missing a step? There is no way that $7^{64}$ can exist because we are only allowed to go up to $7^{50}$

---

After this step we have to multiply $92 \cdot 71 \cdot 49$ and that becomes $320,068$ Subtracting $303,000 = 101 \times 3000$ from $320,068$, we have $17,068$.

Subtracting $10,101 =101 \times 100$ from $ 17,068$, we have $6968$

And then finally subtracting $6060 = 101 \times 60$ from $ 6968$ we have $908$

The closest number is $909 = 9 \times 101$, so our result is $ 908-909 = -1$

So, $7$ is not a quadratic residue of mod $101$ because we want the remainder to be $1$ based off the Theorem and we got $-1$ instead which breaks the Theorem.

Answer 1

You have shown that $7^{50}\equiv-1\pmod{101}$. This shows (NB!) that $7$ is not a quadratic residue modulo $101$. It does not show that $7^{50}$ is not a quadratic residue.

Indeed, as given in a comment by @Arthur, $7^{50}$ is obviously a quadratic residue since it is $(7^{25})^2$.

Answer 2

I hope that in the intervening years since you first posted this question you have come up with shortcuts for computations of this sort. I will assume that by now you know the Legendre symbol, even if you didn't know it back then.

Relatively speaking, both $7$ and $101$ are small numbers. But $7$ is a very small number, so it's much easier to compute $$\left(\frac{101}{7}\right) = 101^3 \equiv 3^3 \equiv -1 \pmod 7.$$ This tells us that $101$ is not a quadratic residue modulo $7$.

But you're asking if $101$ is a quadratic residue modulo $7$. Quadratic reciprocity helps use the $\left(\frac{101}{7}\right)$ result to determine $\left(\frac{7}{101}\right)$: since $7 \equiv 3 \pmod 4$ but $101 \equiv 1 \pmod 4$, it follows from quadratic reciprocity that $$\left(\frac{7}{101}\right) = \left(\frac{101}{7}\right) = -1,$$ confirming your computations for $7^{50}$.