素数に関する最も古くから知られている結果「素数は無限にある」はユークリッド原論に載っている．素数が有限個しかかないと仮定して，背理法で矛盾を導き出すのである．

　素数を小さい方から順にｐ1＝２，ｐ2＝３，・・・，ｐn（最大の素数）とする．

　　ｑ＝（ｐ1ｐ2・・ｐn）＋１＝２（ｐ2・・ｐn）＋１・・・奇数

が素数であるとするとｐnより大きな素数が存在することになり矛盾．合成数であるとするとｐkで割り切れることになり再び矛盾．

　したがって，素数が有限個しかかないという最初の仮定が間違っていたことになる．したがって，素数は無限に存在する．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

［Ｑ］４ｎ＋３型奇数の中に素数が無限にあることを証明せよ．

　４ｎ＋３型素数を小さい方から順にｐ1＝３，ｐ2＝７，・・・，ｐn（最大の４ｎ＋３型素数）とする．

　　ｑ＝４（ｐ1ｐ2・・ｐn）＋３

が素数であるとするとｐnより大きな素数が存在することになり矛盾．

　合成数であるとするとｐkで割り切れないので，４ｎ＋１型素数では割り切れるはずである．もし，ｑのすべての約数が４ｎ＋１型だけならば，その積であるｑは４ｎ＋１型になるが，ｑは４ｎ＋３型なので再び矛盾．（４ｎ＋３型約数は少なくともひとつは存在する．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

［Ｑ］４ｎ＋１型奇数の中に素数が無限にあることを証明せよ．

　４ｎ＋１型素数を小さい方から順にｐ1＝５，ｐ2＝１３，・・・，ｐn（最大の４ｎ＋１型素数）とする．

　　ｑ＝４（ｐ1ｐ2・・ｐn）＋１

が素数であるとするとｐnより大きな素数が存在することになり矛盾．

　合成数であるとするとｐkで割り切れないので，４ｎ＋３型素数では割り切れるはずである．もし，ｑのすべての約数が４ｎ＋３型だけならば，その積であるｑは４ｎ＋３型になるとは限らない．

　たとえば，

　　ｑ＝（４ｍ＋３）（４ｎ＋３）＝１２ｍｎ＋１２ｍ＋１２ｎ＋９

　　　＝４（３、ｍ＋３ｍ＋３ｎ＋２）＋１

となり，この証明はうまくいかない．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝