Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

1 Answer 1

up vote 2 down vote accepted

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$

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.