>http://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0 ;

> 素数は無限に存在する。
> 
> エウクレイデスによる証明 
> 背理法による。 
> 素数が有限個しかないと仮定し、それらを次のようにおく。 
>  
> pi, i <= n 
> ただし n は定数。 
> 
> q = p1p2p3．．．ｐｎ + 1
> 
> を考えよう。q は合成数であるか素数であるかのいずれかである。 
> q が合成数だとすると q は pi のいずれかを用いて積の形に表されるはずである。その一方で q は pi のいずれで割っても 1 があまり、矛盾する。 
> 素数だとすると、これは pi のいずれとも異なるから素数が有限個しかないことに反する。 
> Q.E.D. 

この証明変だよね。