Is my proof correct of 3|a+1 being false.

Question

The question I'm posed is as follows. Let a ∈ $\mathbb{Z}$ such that 3|a. Prove that 3|(a+1) is false without using the Euclid Division Theorem.

My proof is as follows:

---

For the sake of contradiction, assume that 3|a, a ∈ $\mathbb{Z}$, implies that 3|(a+1).

3|a => ∃ k ∈ $\mathbb{Z}$, such that a = 3k.

3|(a+1) => ∃ h ∈ $\mathbb{Z}$, such that a = 3h.

Then 3k+1 = 3h

=> 3k - 3h = -1

=> 3(k - h) = -1

=> k - h = -$\frac 13$

k - h ∈ $\mathbb{Z}$ by closure.

=> -$\frac 13$ ∈ $\mathbb{Z}$

-$\frac 13$ $\notin$ $\mathbb{Z}$ by definition.

=> <=

$\therefore$ 3|a => 3 $\not$ | (a+1)

(i.e. 3 is not divisible by a+1)

Answer 1

By dividing sides by $3,$ you temporarily work in the rational numbers. These are constructed from the integers using a somewhat involved route. So even though your proof doesn't explicitly use the Euclid division theorem, it is a bit "fishy" in going to the rationals. By the way that theorem is just a proof that one can divide an integer $a$ by a nonzero integer $b$ and get a unique quotient $q$ and remainder $r$ where $a=bq+r$ and $0 \le r < |b|.$

At one point you get to $3(k-h)=-1,$ which is same as $3(h-k)=1.$ Here $h-k\ge 1$ since it is positive by sign consideration. Then $3(h-k)\ge 3.$ But then $1=3(h-k)\ge 3,$ a contradiction.

This version doesn't use rationals or Euclid's division theorem.

Answer 2

When you arrive at $3(h-k)=-1$, you're done without going to $-1/3$.

Rewrite it as $3(k-h)=1$, which implies $3$ is invertible in $\mathbb{Z}$, which is known to be false (and is basically your argument).

More simply, from $3\mid a$ and $3\mid (a+1)$ we can derive that $3$ divides $(a+1)-a=1$: contradiction.

If you need to go deeper, note that, for positive integers $x$ and $y$, $x\mid y$ implies $x\le y$, but $3>1$.