# Check whether a=36 is a quadratic residue modulo p for: a) p = 29 b) p = 41 c) p = 67 d) p = 71 Repeat the problem for a = 99

This is the theorem I'm using for my solution: (Euler). Let p be an odd prime and a an integer, then (a/p) ≡ a^(p-1)/2 (mod p)

Solution: Since p is an odd prime gcd(a,p) = 1. We proceed with Euler's Criterion. Thus,

a) 36^(29-1)/2 = 36^14 ≡ 7^14 ≡ (7^7)^2 ≡ 1^2 ≡ -1 (mod 29)
Hence, 36 is not a quadratic residue modulo 29

b) 36^(41-1)/2 = 36^20 ≡ (-5)^20 ≡ (-1)^20 (5)^20 ≡ (1) (5^2)^10 ≡ (1) (2^10) ≡ 1024 ≡ -1 (mod 41)
Hence, 36 is not a quadratic residue modulo 41

c) 36^(67-1)/2 = 36^33 ≡ (-31)^33 ≡ (-1)^33 (31)^33 ≡ (-1) (31^3)^11 ≡ (-1) (3^11) ≡ -177147 ≡ 1 (mod 67)
Hence, 36 is a quadratic residue modulo 67

d) 36^(71-1)/2 = 36^35 ≡ (-35)^35 ≡ (-1) (35)^35 ≡ (-1) (35^5)^7 ≡ (-1) ((5*7)^5)^7 ≡ (-1) (5^5)^7 (7^7)^5 ≡ (-1) (-1)^7 (-1)^5 ≡ (-1) (mod 71).
Hence, 36 is not a quadratic residue modulo 71.

For the second part. Repeat the problem for a = 99.

Solution: Since gcd(a, p) = 1 we proceed with Euler's Criterion

a) 99^(29-1)/2 = 99^14 ≡ 12^14 ≡ (2*2*3)^14 ≡ ((2*2*3)^2)^7 ≡ (2^2)^7 (2^2)^7 (3^2)^7 ≡ (-1) (-1) (-1) ≡ -1 (mod 29)
Hence, 99 is not a quadratic residue modulo 29

b) 99^(41-1)/2 = 99^20 ≡ (17)^20 ≡ (17^2)^10 ≡ (2^10) ≡ 1024 ≡ -1 (mod 41)
Hence, 99 is not a quadratic residue modulo 41

c) 99^(67-1)/2 = 99^33 ≡ (32)^33 ≡ (2^5)^33 ≡ 5^33 ≡ (5^3)^11 ≡ 3^11 ≡ 177147 ≡ -1 (mod 67)
Hence, 99 is not a quadratic residue modulo 67

d) 99^(71-1)/2 = 99^35 ≡ (28)^35 ≡ (4*7)^35 ≡ (4)^35 (7)^35 ≡ (4^5)^7 (7^7)^5 ≡ (-1) (-1) ≡ (-1) (mod 71).
Hence, 99 is not a quadratic residue modulo 71.

Can somebody please verify that my solutions are correct. If not please correct me with explanation.

-
how $1^2\equiv -1\pmod {29}$ and $(5^2)^{10}\equiv 2^{10}\pmod{41}?$ – lab bhattacharjee Nov 17 '12 at 7:58

As $36=(\pm6)^2, 36\equiv (\pm6)^2\pmod m$ for any integer $m$.

Alternatively, using Fermat's Little Theorem, $36^{\frac{p-1}2}=(\pm 6)^{p-1}\equiv 1\pmod p$ if $(6,p)=1$ i.e., prime $p>3$.

If $x^2\equiv 99\pmod p$ where $p>3$, $\left(\frac x 3\right)^2\equiv 11\pmod p$

Alternatively, using Legendre Symbol, $\binom {99}p=\binom {11}p\binom 9 p=\binom {11}p\binom {3^2}p =\binom {11}p$ as $\binom {x^2}p=1$ if $(p,x)=1$

So, we need to test for $11.$

We know, $ord_p{11}\mid (p-1)$

(a)For $p=29,p-1=28$ whose divisors are $1,2,4,7,14,28$

$11^2=121\equiv 5\pmod{29},11^4\equiv 25\equiv -4,11^7\equiv 11\cdot 11^2\cdot11^4\equiv 11\cdot5(-4)\equiv12,11^{14}=144\equiv-1$

Hence, $11$ is not a quadratic residue modulo $29$, hence $99$ is not.

Alternatively, $99\equiv 12\pmod {29}, 99^2\equiv 12^2=144\equiv -1\implies 99^{14}=(99^2)^7\equiv (-1)^7\pmod {29}\equiv -1$

(b)$11^2=121\equiv -2\pmod{41}, 11^{10}=(11^2)^5\equiv (-2)^5=-32\equiv 9, 11^{20}\equiv 9^2=81\equiv -1$

Alternatively, $99\equiv 17\pmod {41},99^2\equiv 289\equiv 2, 99^{10}=(99^2)^5\equiv 2^5\equiv -9, 99^{20}=(99^{10})^2\equiv 9^2=81\equiv-1$

(c) $11^2=121\equiv -13\pmod{67}, 11^3\equiv (-13)11\equiv -9,11^6\equiv81\equiv 14, 11^{12}\equiv 196\equiv -5,11^{24}\equiv 5^2=25, 11^{33}=11^{24}\cdot 11^6\cdot 11^3\equiv 25\cdot14(-9)\equiv 25\cdot 8=200\equiv -1$

Alternatively, $99\equiv 32\pmod {67}=2^5$

Now, $2^6=64\equiv -3\pmod {67}, 2^{24}=(2^6)^4\equiv(-3)^4=81\equiv 14$

$2^{33}=2^3\cdot 2^6\cdot 2^{24}\equiv 8(-3)14=8(-42)\equiv 8(25)=200\equiv -1$

So, $99^{33}\equiv(2^5)^{33}\equiv (-1)^{33}=-1$

(d) $99\equiv 28\pmod{71}, 99^{35}\equiv (28)^{35}=2^{70}\cdot 7^{35}\equiv7^{35}$ as $2^{71-1}\equiv 1\pmod{71}$ using Fermat's Little Theorem.

$7^3=7\cdot7^2\equiv7(-22)\pmod{71}\equiv-12, 7^6\equiv(-12)^2=2, 7^{30}\equiv 2^5\pmod{71}=32$

$7^{35}=7^{30}\cdot7^3\cdot7^2\equiv 32(-12)(-22)=64(132)\equiv (-7)(-10)=70\equiv -1$

-
Thank you for your explanation it really helped me understand the problem. – Diana Martinez Nov 18 '12 at 1:51