TMUA 2016 Paper 2 Q13 — Worked Solution

P2·Number Theory & Divisibility·7.0Official · 2016 · Q13

proof-errormodular-arithmeticremainder-bounds

In this question,

a

b

, and

c

are positive integers. The following is an attempted proof of the false statement: 'If

a

divides

b c

, then

a

divides

b

a

divides

c

.' ['

a

divides

b c

' means '

a

is a factor of

b c

'.]

Line 1

The statement is equivalent to 'if

a

does not divide

b

and

a

does not divide

c

then

a

does not divide

b c

Line 2

Suppose

a

does not divide

b

and

a

does not divide

c

. Then the remainder when dividing

b

a

r

, where

0 < r < a

, and the remainder when dividing

c

a

s

, where

0 < s < a

Line 3

b = a x + r

and

c = a y + s

for some integers

x

and

y

Line 4

Thus

b c = a (a x y + x s + y r) + r s

Line 5

So the remainder when dividing

b c

a

r s

Line 6

Since

r > 0

and

s > 0

, it follows that

r s > 0

Line 7

Hence

a

does not divide

b c

Which line contains the error in this proof?

All questions

Discussion

Discuss this question

No discussions yet. Stuck, or want to share an approach? Start the first one.

TMUA 2016 Paper 2 Question 13

Discussion