Skip to content

Instantly share code, notes, and snippets.

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

Embed
What would you like to do?
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
You can’t perform that action at this time.