Instantly share code, notes, and snippets.

# dtinth/proof.md Last active Oct 11, 2015

a^2 - 3 is never divisible by 9.

# (a^2 - 3) is never divisible by (9).

## Proof

Suppose that (a) is any positive integer, we must show that

$$a^2 - 3 = 9n + r; n \in \mathbb{Z}, r \in \mathbb{Z}, 0 < r < 9$$

By the quotient-remainder theorem, we can divide (a) into these 9 cases:

1. ( a = 9k; k \in \mathbb{Z} \\ \therefore a^2 - 3 = 9(9k^2)-3 = 9(9k^2-1)+6 )
2. ( a = 9k + 1; k \in \mathbb{Z} \\ \therefore a^2 - 3 = 9(9k^2+2k)+1-3 = 9(9k^2+2k-1)+7 )
3. ( a = 9k + 2; k \in \mathbb{Z} \\ \therefore a^2 - 3 = 9(9k^2+4k)+4-3 = 9(9k^2+4k)+1 )
4. ( a = 9k + 3; k \in \mathbb{Z} \\ \therefore a^2 - 3 = 9(9k^2+6k)+9-3 = 9(9k^2+6k)+6 )
5. ( a = 9k + 4; k \in \mathbb{Z} \\ \therefore a^2 - 3 = 9(9k^2+8k)+16-3 = 9(9k^2+8k+1)+4 )
6. ( a = 9k + 5; k \in \mathbb{Z} \\ \therefore a^2 - 3 = 9(9k^2+10k)+25-3 = 9(9k^2+10k+2)+4 )
7. ( a = 9k + 6; k \in \mathbb{Z} \\ \therefore a^2 - 3 = 9(9k^2+12k)+36-3 = 9(9k^2+12k+3)+6 )
8. ( a = 9k + 7; k \in \mathbb{Z} \\ \therefore a^2 - 3 = 9(9k^2+14k)+49-3 = 9(9k^2+14k+5)+1 )
9. ( a = 9k + 8; k \in \mathbb{Z} \\ \therefore a^2 - 3 = 9(9k^2+16k)+64-3 = 9(9k^2+16k+6)+7 )

Therefore, in every case, (a^2 - 3) can be written in form of (9n + r) where (n, r \in \mathbb{Z} \text{ and } 0 < r < 9).

Since (r) is never (0), we can never eliminate the (+ r) term to make it in the form of (9n), and therefore (a^2 - 3) is never divisible by 9. Quod erat demonstrandum.

to join this conversation on GitHub. Already have an account? Sign in to comment