Question

2. Suppose P and Q are positive odd integers such that (PQ)-1. Prove that Qm] Pn] P-1 0-1 0<m<P/2 0<n

Answer 1

let P and Q be odd positive integers (P, Q) = 1 Let F-be the set of all pairs of integers (x, y) satisfying 1 lessthanorequalto x < P/2 and 1 lessthanorequalto y lessthanorequalto q/2 then F has P - 1/2, q - 1/2 members We find separation of F into F_1 and F_2 F_1 = {(x, y)/x > p y} F_2 = {(x, y)/x < p y} There are no pairs (x, y) in F s.t q x = p y F_1 can be given as set of all pairs in F, (x, y) such that 1 lessthanorequalto x lessthanorequalto (p - 1)/2, 1 lessthanorequalto y lessthanorequalto x/p Therefore Number of pairs in F_1 is Sigma^p - 1/2_x = 1 [Q_x/P] Similarly F_2 consists of the pairs (x, y) such that 1 lessthanorequalto y lessthanorequalto (q - 1)/2 and 1 lessthanorequalto x < y/Q Therefore Number of pairs in F_2 are Sigma^(Q - 1)/2_y = 1 [p y/Q]