Can I get number 3 answered please. I don\'t understand it. thank you MATH 116.
ID: 3147357 • Letter: C
Question
Can I get number 3 answered please. I don't understand it. thank you
MATH 116. Wednesday 11/15/17 1, Exercise 10.8. Let n e Z, n > 1. o(n) (a) Prove that Z., for n > 2, contains at most o22 squares. Hint: z2 (-2P (mod n), for all z E Z. 2. Exercise 10.10. Fix p an odd prime and k E N. Compute (b) (g Hint for part (a): Erercise 10.8(c). Hint for part (b): Take two cases: k even and k odd. 3. Exercise 10.15. Let p be an odd prime. Assume that a is a quadratic residue modulo p. Show that -a is also a quadratic residue modulo p if and only if p 1 (mod 4). 4. Exercise 10.29. Is 1974 a quadratic residue modulo p? Where (c) p 991 (d) p = 1009 5, Exercise 10.33. Is n = 262012 . 621,000.001-251003 a square modulo p-991?Explanation / Answer
3. It is given that a is a quadratic residue mod p.
By Euler's criterion, a(p-1)/2 1 mod p
If p 1 mod 4, let p = 4k + 1 where k is an integer
=> a(4k+1-1)/2 1 mod p
=> a2k 1 mod p
=> (a2)k 1 mod p
=> ((-a)2)k 1 mod p
=> (-a)2k 1 mod p
=> (-a)(4k+1-1)/2 1 mod p
=> (-a)(p-1)/2 1 mod p
=> -a is a quadratic residue mod p.
If -a is a quadratic residue mod p
=> (-a)(p-1)/2 1 mod p
=> (-1)(p-1)/2 a(p-1)/2 1 mod p
Since a(p-1)/2 1 mod p,
=> (-1)(p-1)/2 1 mod p
Note that (-1)(p-1)/2 can be -1 or 1.
If (-1)(p-1)/2 = -1,
=> -1 1 mod p
=> -2 0 mod p which is not possible since p is an odd prime.
=> (-1)(p-1)/2 = 1
=> (p-1)/2 = 2k where k is an integer
=> p - 1 = 4k
=> p = 4k + 1
=> p 1 mod 4.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.