TMUA Practice Question — Worked Solution

P2·Number Theory & Divisibility·6.0CrackTMUA Original

proof-erroreuclids-lemmamodular-edge-casedivisibility

Below is an attempted proof of the claim: 'For every integer

n

, if

3

divides

n^{2} - n

, then

3

divides

n

.' On which line does the argument first go wrong?

Line 1

Factorise:

n^{2} - n = n (n - 1)

Line 2

Since

3

divides

n (n - 1)

and

3

is prime, it follows that

3

divides

n

3

divides

n - 1

Line 3

3

divides

n - 1

, then

n - 1 = 3 k

for some integer

k

, so

n = 3 k + 1

, which is divisible by

3

Line 4

Therefore, in either case,

3

divides

n

, as required.

Discussion

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