NUMBER THEORY 38 PROOF n the net 6t 10 mod 19 roblems find t

n the net 6,t 1-0 (mod 19) roblems, find the least complete solution. In 31. 426 33.42++10 (mod 1 35. 5+81 (modl 1 32, 4x2 + 6x + 1 34, a,2 +16z +30 (mod 127) 36, 3r2 + 3r-5 + 1 0 (mod 13) 0 (mod 11), , 35. 5x2 + 8x + 1 0 (mod 129) 0(mod 53) . Finish the proof of the first theorem of this section by showing that if p is an odd prime not dividing a, if y-b2-4ac (mod p), and if 2ar--bty (mod p), then ax2 + bx+c 0, (modp). (Hint: Find usuch that 2au 1 (mod p). Then x a(-b + y) (mod p). Substitute this into the desired congruence. Show that if m 0 and if a and b are integers such that 2a (mod m) Show that if m > 0 and if a and b are integers such that a? a(mod m) and y2 (mod m), then ~2-ab (mod m) is solvable. 39. Show that if p is an odd prime and p t ac, then complete solutions to 0 (mod p) and cr + br + a 0 (mod p) have the same b Ih the next four problems, tell whether the statement is true and give a coun- b 2 + br + c number of elements. 40. Suppose p is an odd prime not dividing ab.. Show that z2 = ab (mod p) is solvable exactly when both or neither of 2a (mod p) and y2 (mod p) are solvable. tererample if it is false. 41. Let me > 0 and (m, ab) 1 . If neither 2,2 a (mod m) nor y2 4) (mod m) is solvable, then z2 12. If ab (mod m) is solvable. p is an odd prime, then complete solutions to ar2 +ba +c 0 (mod p) and cr2 + br + 0 (mod p) have the same number of elements.

Solution

x^2=a mod m

x^2-a=rm for some integer ,r

y^2=b mod m

So,

y^2-b=sm for some integer,s

(x^2)(y^2)=(a+rm)(b+sm)

(xy)^2=ab+m(rb+sa)+rsm^2=ab mod m

Hence if x and y are solutoins to

x^2=2 mod m and y^2=b mod m respectively

THen,xy is a solution to

u^2=ab mod m