# Is each integer $n > 2$ is divisible by $4$ or by an odd prime number

While reading through the proof of Fermat's Last Theorem, I came across this statement. "Each integer $n > 2$ is divisible by $4$ or by an odd prime number" But I don't know how to prove it.

• hint: use unique factorization. If there are no odd prime factors, what does that tell you? – lulu Jul 1 '17 at 14:45
• "While reading through the proof of Fermat's Last Theorem" seriously? – Tobias Kildetoft Jul 1 '17 at 21:13

Two cases.

1. It's odd. Then $2$ doesn't divide it; but some prime does divide it, and that prime has to be odd because it's not $2$.
2. It's even. Then consider $n/2$. Either $2$ divides this (in which case $4$ divides $n$ and we're done) or $n/2$ is odd; but that latter case means an odd prime divides $n/2$ so an odd prime divides $n$.

Yes. Look at singly even numbers like $6$ and $-10$. These are not divisible by $4$, but they are both divisible by odd primes ($-3$ and $5$, for example). And obviously odd primes are trivially divisible by themselves.

It is also obvious that powers of $2$ are not divisible by odd primes. But aside from $1$ and $2$, they're all divisible by $4$.

You didn't ask about $0$ and the negative numbers, but it's also true for them, with the additional exceptions of $-2$ and $-1$. Now ponder $0$, mwahahahahahahahaha!

The only positive integers not divisible by an odd prime are those having at most $2$ as prime divisor, i.e., the powers of $2$. But if $n=2^k$ and $n>2$ then $k\ge 2$ and so $n=4\cdot 2^{k-2}$.

Look at the unique prime factorization of the integer. How can it look like if the integer is not allowed to be divisible by 4?