can you please do it perfectly with explination

Assignment 5
Question 1: Find all the quadratic residues and non-residues of 19.
Solution: A number „a‟ which is relatively prime to n is a quadratic residue modulo n if the
congruence x
2
≡ a (mod n) has a solution.
For 19, the quadratic residues are {1, 4, 5, 6, 7, 9, 11, 16, and 17}
For 19, the quadratic non-residues are {2, 3, 8, 10, 12, 13, 14, 15, and 18}.
Question 2: Let p be prime and a, a quadratic residue of p. Show that if p ≡ 1 (mod 4), then
−a is also a quadratic residue of p, while if p ≡ 3 (mod 4), then −a is a quadratic non-residue
of p.
Solution: The following is proved by Gauss‟s statement of quadratic reciprocity:
If p ≡ 1 (mod 4), then
The congruence x
2
≡ a (mod p) is solvable if and only if x2 ≡ p (mod a) is, but
If p ≡ 3 (mod 4), then
The congruence x
2
≡ a (mod p) is solvable if and only if x2 ≡ -p (mod a) is.
Question 3: Evaluate each of the following Legendre symbols:
(a) 





23
19

Solution: (19/23) = (−4/23) = (4/23)(−1/23) = 1 · (−1) = −1.
(b) 





79
17

Solution: (17/79) = −1.
(c) 





101
18

Solution: (18/101) = (3/101)*(3/101)*(2/101) = (-1).(-1).(-1) = -1
Question 4: Show that if p is a prime with p > 3, then 




 
p
3
= 1 if p ≡ 1 (mod 3), 




 
p
3
= -1
if p ≡ −1 (mod 3).
Solution: The 




 
p
3
= 1 is only possible when -3 is quadratic residue of p.
For, -3 being quadratic residue, it must fulfill p ≡ 1 (mod 3).
Conversely, 




 
p
3
= -1 is only possible when -3 is quadratic non-residue of p.
For, -3 being quadratic non-residue, it must fulfill p ≡ - 1 (mod 3).
Question 5: Evaluate the Jacobi symbol 





35
22

Solution: The steps are below:
(22/35) = - (11/35) = (2/11) = - (1/11) = -1
Question 6: Show that the integer 645 is a pseudo-prime but not an Euler pseudo-prime to
the base 2.
Solution: The steps are below to prove 645 is pseudo-prime:
Note that working mod 645,
2^((645 - 1)/2) = 2^322 = (2^14)^23 = 259^23
= (259^3)^7 * 259^2
= 259^7 * 259^2
= (259^3)^3
= 259^3
=...