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

Table of contents
- i b
  - Solution i
- ii b
  - Solution ii

i

Solution

The notation means that

n

divides

a_{1} - a_{2}

:

a_{1} \equiv a_{2} (mod n) ⟺ there exists k \in Z with a_{1} - a_{2} = kn .

This is congruence modulo an integer; equivalently, the two integers have the same remainder on division by the positive integer

n

.

ii

Solution

Write

a_{1} - a_{2} = kn

with

k \in Z

. The difference of two squares factors as

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

divides the difference. By congruence modulo an integer,

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

.

 Ancestors (11)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version