 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2014/discrete-mathematics-continuous-mathematics-and-probability/3/b/ii/solution

Write

a_{1} - a_{2} = kn

with

k \in Z

a_{1}^{2} - a_{2}^{2} = (a_{1} - a_{2}) (a_{1} + a_{2}) = n k (a_{1} + a_{2}) .

The final factor is an integer, so

n

a_{1}^{2} \equiv a_{2}^{2} (mod n)

 New to topics? Read the docs here!