Create a gist now

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.

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