素数全書 問題1.2
というような一般論もあるが、ここではユークリッド互除法を使って直接証明してみる。
素数pとpで割り切れない整数xに対して、ユークリッド互除法を繰り返し使うとkp+lx=1 なるような整数k,lが存在する。同じようにpで割り切れない整数yについてもk'p+l'y=1 なる整数k',l'が存在する。この2つを辺々掛け合わせると
1=(kp+lx)・(k'p+l'y)=ll'xy+p(kk'+kl'+lk')
となるが、ここでxyがpで割り切れると、1がpで割り切れることになり矛盾である。
よって p|xy ⇒ p|x or p|y □
後半は、 n が素数でなければ、n=k・l k,l>0 と分解され、0
