Prove that there is no number that divides both n and n+1

Question

Statement

There is no number $x > 1$ that divides both $n$ and $n+1$.

Proof (my attempt)

Indirect proof:

\begin{align} x\mathbin{\vert} n & \implies n = xt_1 \\ x\mathbin{\vert}(n+1) & \implies n+1 = xt_2 \end{align}

Having $n$ as a multiple of $x$ that is $x t_1$, the next larger multiple of $x$ is $x(t_1+1)$ which is always greater than $n+1$ as $x>1$.

Therefore, $x$ does not divide $n+1$ and we have a contradiction.

Thus the original statement is true.

Question

Is this how you can prove the statement? Is there anything wrong or something that can be improved formally?

Answer 1

There is nothing wrong with your proof. However, the critical sentence, the one starting "Having...", is true, but is (at least to me) not convincing, or at least not as simple as it could be. It would be easier to subtract the two equations, giving $1 = x(t_2-t_1)$, deriving a contradiction.

Answer 2

If integer $x$ divides both $n,n+1$

$x$ must divide $n+1-n$

If general, $x$ must divide $a\cdot(n+1)+b\cdot n$ where $a,b$ are integers

We have chosen $a=1,b=-1$

Answer 3

Your proof is fine. Another way to say the same thing is: $x\mathbin|n$ and $x\mathbin|n+1$ would imply that $x\mathbin|(n+1)-n=1$, contradicting with the premise that $x>1$.

Answer 4

Proving that if $a$ divides $b$ for positive $a$, $b$ then $a \leq b$ is a multiple page proof if you're working from the axioms of the integers directly. (It's not hard, unreasonable or onerous - just a bit more work than you would expect.) I don't believe your proof requires this but you should take much care in introducing inequalities and properties of ordering here - it actually does make your proof much more heavyweight, and even careless.

Furthermore your proof now requires ordering properties of the integers, but you don't need to use them. If you don't, your proof becomes general to other number systems, which is nice.

Try Lemma: if $d \mid a $ and $d \mid b$ then $d \mid ax+by$ for all $x,y$.

Answer 5

Kim Jong Un's point is good, you can flip it around with Modular Arithmetic as well.

Suppose $x |n$ and $x| (n+1)$ then,

$$n +1 \equiv 0 \pmod{x}$$ $$n \equiv 0 \pmod{x}$$

Subtracting the two,

$$1 \equiv 0 \pmod{x} \implies \space \text{This means $1$ is divisible by $x$, which is impossible.}$$