If $4|n(n-1)$ then $4|n$ or $4|(n-1)$ 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? 
 A: 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$).
A: 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$.
A: 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.
A: 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.$$
A: 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$.
