Answer to Question #297636 in Combinatorics | Number Theory for Allan

Question

Show that any prime number is either in form of 4k+1 or 4k+3, k is any positive integer

Answer 1

By Euclid’s Division Lemma, each integer number $n$ can be represent as $n=4k+r,$ where $r\in\{0,1,2,3\}.$

If $r=0,$ then $n=4k=2(2k),$ and hence $n$ is a composite number.

If $r=2,$ then $n=4k+2=2(2k+1),$ and hence $n$ is a composite number.

Therefore, any prime number is either in form of $4k+1$ or $4k+3,$ where $k$ is any positive integer.