 Solution

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

Divide the divisibility relation

91 ∣ 26 x - 39

13

to obtain

7 ∣ 2 x - 3

. Since

2 \cdot 4 \equiv 1 (mod 7)

x \equiv 12 \equiv 5 (mod 7)

. Therefore all integer solutions are

x = 5 + 7 q

q \in Z

91 = 13 \cdot 7

q = 0, \dots, 12

give

x \equiv 5, 12, 19, 26, 33, 40, 47, 54, 61, 68, 75, 82, 89 (mod 91) .

They are distinct residue classes: equality of two such classes would imply

91 ∣ 7 (q - q^{'})

, hence

13 ∣ q - q^{'}

. Every integer

q

is congruent to one of those thirteen choices, so the list is exhaustive.

 New to topics? Read the docs here!