# If $3 \nmid (k-1)$ and $3 \nmid k$, prove $3 | (k+1)$ [duplicate]

Suppose $$k-1, k \in \mathbb{N}$$, and $$3 \nmid (k-1)$$ and $$3 \nmid k$$, I have to prove that $$3 | (k+1)$$. Since $$k$$ is a natural number, I can see that the very next natural number would be divisible by 3, but I don't know how to argue this mathematically.

• Any three consecutive integers form a residue class $\bmod 3$. So one of three consecutive integers is always divisible by $3$. Commented Aug 1 at 11:54

## 4 Answers

If $$3\nmid k-1$$, then $$k-1\equiv 1\pmod 3\quad \text{or}\quad k-1\equiv 2\pmod 3.$$

If $$k-1\equiv 2\pmod 3$$, then $$k\equiv 0\pmod 3$$, and thus $$3\mid k$$, which is a contradiction. Therefore, $$k-1\equiv 1\pmod 3$$, and thus $$k+1\equiv 0\pmod 3$$, which prove that $$3\mid k+1$$.

• from which theorem does the second line follow ? Commented Aug 1 at 10:04
• I didn't used any theorem here. The second line follows from the fact that any integer number is either $\equiv 0\pmod 3$, or $\equiv 1\pmod 3$ or $\equiv 2\pmod 3$ @user9026
– Surb
Commented Aug 1 at 10:15
• @Surb, isn't this basically assuming the result you are trying to prove? Commented Aug 1 at 10:48
• @AdamRubinson: What do you mean ?
– Surb
Commented Aug 1 at 11:06
• I didn't bring up equivalence relations: Eemil did. @Surb my point is that you have asserted "If k∈Z, there are q,r∈Z with 0≤r<3 s.t. k=3q+r ", but you cannot use this "fact" unless you are sure that there is a proof of this fact doesn't require assuming OP's proposition is true (in which case, it is pertinent you state such a proof). Commented Aug 1 at 14:22

Their product is $$k^3-k=0\mod 3$$ by Fermat's little theorem, so their product is divisible by $$3$$. By Euclid's theorem $$3|k(k-1)$$ or $$3|k+1$$, and since we know it doesn't divide the first two, so it must divide $$k+1$$.

• Please strive not to post more (dupe) answers to dupes of FAQs. This is enforced site policy, see here. Commented Aug 1 at 16:34
• @BillDubuque no thank you. Commented Aug 2 at 9:31

Suppose the following statement, $$P(k),$$ is false:

$$P(k):\quad$$ If $$3 \nmid (k-1)$$ and $$3 \nmid k$$, then $$3 | (k+1)$$.

Then there exists $$K$$ such that $$3 \nmid (K-1),\ 3 \nmid K,\$$ and $$3 \nmid (K+1)$$.

But then, since $$3 \nmid K+1,\ 3 \nmid K-2.\$$ Since $$3 \nmid K,\ 3 \nmid K-3.$$ And so on. By induction, it follows that $$3\nmid J$$ for all $$J\leq K+1.$$

Thus, all multiples of $$3$$ must be $$\geq K+2.$$ By the well-ordering principle, there exists a minimal multiple of three. Call it $$x.$$

But $$x-3$$ must be a multiple of three also, contradicting the definition of $$x.$$ A contradiction has arisen. Thus $$P(k)$$ is true.

• Please strive not to post more (dupe) answers to dupes of FAQs. This is enforced site policy, see here. Commented Aug 1 at 16:34

We can argue by induction. Let's first rephrase the theorem into this equivalent version:

Theorem: For all nonnegative integers $$k$$, at least one of $$k-1$$, $$k$$, and $$k+1$$ is divisible by $$3$$.

Proof. Base case: When $$k=0$$, then $$3$$ divides $$k$$.

Induction step: Suppose it's true for $$k$$. Since $$3|k-1\iff 3|(k-1)+3,$$ we know that $$3$$ divides at least one of $$(k-1)+3$$, $$k$$, and $$k+1$$. In other words, $$3$$ divides at least one of $$(k+1)+1$$, $$(k+1)-1$$, and $$(k+1)$$, and we are done. $$\square$$

(As a bonus, we can extend the theorem to negative $$k$$ as well, by applying this theorem to $$(-k)-1$$, $$(-k)$$, and $$(-k)+1$$ and negating.)

• You can also replace "at least one" with "exactly one" throughout. Commented Aug 1 at 11:36
• Please strive not to post more (dupe) answers to dupes of FAQs. This is enforced site policy, see here. Commented Aug 1 at 16:34