Statements with rare counter-examples This is a soft question. I'm searching for examples of mathmatical statements (preferably in number theory, but other topics are also fine), that seem to be true, but are actually not. Statements where observing some examples would let you think it is always true, but then there is a well hidden counter-example.
If Riemann's $\zeta$ function had a zero beside the critical line, this would be such an example I'm looking for. Or if Fermat's Last Theorem would be false.
Do you know any such surprising counter-exmaples?
 A: Fermat's ‘little’ theorem states that if $n$ is prime, then  $$a^n\equiv a\pmod n\tag{$\ast$}$$ holds for all $a$.  The converse, which is false, states that if $(\ast)$ holds for all $a$, then $n$ is prime.
Counterexamples to this converse are uncommon; the smallest is $n=561$.
A: The largest odd value of $n$ such that regular $n$-gons are constructable by compass and straight edge is $n=1~431~655~765$.
There is one known exception: $n=4~294~967~295$.
All in all, there are currently only $31$ known constructable regular polygons with an odd number of sides. Prior to Gauss, the largest odd-sided constructable regular polygon was just the pentagon. No doubt much of the numerological and mystical lore surrounding the pentagon and pentagram can be traced back to observations by the ancients that this five sided shape represented some fundamental boundary between the world of finite imperfect man on one side, and the perfect and infinite on the other. 
A: Euler's Sum of Powers Conjecture:
$$a_1^k+\ldots+a_n^k=b^k\qquad\text{with }k>n>1$$
has no solutions in positive integers.
The smallest counterexample is
$$95800^4 + 217519^4 + 414560^4 = 422481^4$$
A: The following spikedmath is cute.

The books "Counterexamples in Topology" by Steen and Seebach as well as "Counterexamples in Analysis" by Gelbaum  and Olmstead have some that are surprising when you first see them. 
A: If  $\ n\ $ that $\ ◎(n)=\frac{n+1}{2^x}$ or $\ ◎(n)=\frac{n-1}{2^x}, \ n \in \mathbb{Z^+},\ x \in \mathbb{N}_{\gt 0},\ $then $\ n\ $ is prime.
First  counter-example is $\ 92673$.
$◎(n)\ $ is called the cycle length of $n$ , detail see: How to prove these two ways give the same numbers?
A: Lucke numbers of Euler:
For every natural number $n$, the following number is prime:
$$n^2-n+41$$
The smallest $n$ for which this conjecture is wrong, is 41 -- naturally.
A: For every $n$
$$\int_0^\infty 2 \cos(x) \prod_{i=0}^n\frac{\sin\frac{x}{2i+1}}{\frac{x}{2i+1}}\,dx=\pi/2$$
Is it true? Well, for every $n$ less than 56, but after...
An example of Borwein integral.
A: Pierre de Fermat conjectured that all Fermat numbers  were prime, and a similar
mistaken conjecture can be made for most pseudoprimes (Catalan, Fibonacci, Euler, Wieferich, etc.).
Also see Euler's sum of Powers conjecture , and the Polya conjecture.
