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.