If $4|n(n-1)$ then $4|n$ or $4|(n-1)$

Question

Since $4$ is not prime, we can't use Euclid's lemma. Assume $4$ does not divide $n$, we'd like to show that $4|(n-1)$.

Suppose $n=4a+b$ where $b\neq 0$. It suffices to prove that $b=1$, but I feel like this is a dead end. Is my setup wrong?

Answer 1

Note that $n-1$ and $n$ are two consecutive numbers, so exactly one of them is even and one is odd. If, for example, $n-1 = 2k$ is even, then $n(n-1) = 2k(2k+1) = 4k^2 + 2k \equiv_{4} 2k \equiv_2 k = 0$, so $k$ is even and so $4|n-1$. (Here $a\equiv_c b$ means $a \equiv b \mod c$).

Answer 2

Correct me if wrong:

Note that either $n$ or $(n-1)$ is odd.

Let $n$ be even.

$(n-1)n =4k=2(2k)$, i.e.

$2|n(n-1) \rightarrow 2|n$ (Euclid) .

$ n/2 \in \mathbb{Z^+}$

Rewriting:

$(n-1)(n/2)2 = 2(2k)$, or

$(n-1)(n/2) = 2k$.

Similar argument $2|(n/2)$ (Euclid), or

$n/2 = 2s$, or

$n=4s$.

Similar argument when $n-1$ is even.

Answer 3

Method 1: You can't use Euclid's Lemma with $4$ but you can use it with $2$. So either i) $2^2|n$ or ii) $2|n$ and $2|n-1$ or iii) $2^n|n-1$. And ii) $2|n$ and $2|n-1$ is impossible.

Method 2: $n$ and $n - 1$ are relatively prime. So If $2|n$ then $2\not \mid n-1$ so $2^2|n$. Likewise if $2|n-1$ then $2\not \mid n$ so $2^2|n-1$.

Method 3:

Corollary to Euclids lemma: If $m|ab$ then there exist $j,k$ so that $m = jk$ and $j|a$ and $k|b$. If $\gcd(a,b) = 1$ then $\gcd(j,k) = 1$.

(Can you prove that)

Thus $4|n(n-1)$ means either $4|n$ or $4|n-1$.

Method 4:

$n \equiv 0, 1,2,3 \mod 4$.

If $n\equiv 0 \mod 4$ then $n(n-1)\equiv 0*3\equiv 0 \mod 4$

If $n \equiv 1\mod 4$ then $n(n-1)\equiv 1*0 \equiv 0 \mod 4$

If $n \equiv 2 \mod 4$ then $n(n-1) \equiv 2*1 \equiv 2 \mod 4$.

If $n \equiv 3 \mod 4$ then $n(n-1) \equiv 3*2\equiv 2 \mod 4$.

So if $4|n(n-1)$ then either $n\equiv 0 \mod 4$ or $n\equiv 1 \mod 4$.

Answer 4

We want to show: $$4\mid n(n-1) \Rightarrow 4\mid n \ \ \text{or} \ \ 4\mid (n-1).$$ If $$4\mid n \iff n\equiv 0\pmod 4 \iff n-1\equiv -1\pmod 4 \Rightarrow 4\nmid (n-1).$$ If $$4\mid (n-1) \iff n-1\equiv 0\pmod 4 \iff n\equiv 1\pmod 4 \Rightarrow 4\nmid n.$$

Answer 5

Suppose $p$ is prime and $p^m\mid n(n-1)$ where $m\ge1$. Since $p$ is prime and $p\mid n(n-1)$, we have $$ p\mid n\quad\text{or}\quad p\mid n-1 $$

---

Case 1: Suppose that $p^k\mid n$ where $1\le k\lt m$. Then $\left.p^{m-k}\,\middle|\,\frac{n}{p^k}(n-1)\right.$ and since $p$ is prime and $\left.p\,\middle|\,\frac{n}{p^k}(n-1)\right.$, we have $$ \left.p\,\middle|\,\frac{n}{p^k}\right.\quad\text{or}\quad p\mid n-1 $$ We cannot have $p\mid n-1$ since then $p$ divides $n-(n-1)=1$. Therefore, $p^{k+1}\mid n$.

Inductively, $p^m\mid n$.

---

Case 2: Suppose that $p^k\mid n-1$ where $1\le k\lt m$. Then $\left.p^{m-k}\,\middle|\,n\frac{n-1}{p^k}\right.$ and since $p$ is prime and $\left.p\,\middle|\,n\frac{n-1}{p^k}\right.$, we have $$ p\mid n\quad\text{or}\quad\left.p\,\middle|\,\frac{n-1}{p^k}\right. $$ We cannot have $p\mid n$ since then $p$ divides $n-(n-1)=1$. Therefore, $p^{k+1}\mid n-1$.

Inductively, $p^m\mid n-1$.

---

Thus, if $p$ is prime and $p^m\mid n(n-1)$ where $m\ge1$, then $$ p^m\mid n\quad\text{or}\quad p^m\mid n-1 $$ Now set $p=m=2$.