前回に続いて、数学に関する記事として「互いに素」について。
整数xとyの最大公約数が1のとき、xとyは互いに素と言います。
たとえば、「3と5」、「6と35」、「1と24」なんかが互いに素です。
また、互いに素は簡単な言い換え方として、「共通して持つ正の整数が1のみである」、「共に割り切る素数が存在しない」などがあります。
あまり見かけませんが、表記としてはx⊥yがあります。
いくつか、性質を確認しておきます。以下で出る文字は全て自然数です。
まず、xとyが互いに素⇔最小公倍数lcm(x,y)=xy
(⇒)
x=Πp_i^a_i, y=Πq_j^b_jとする。(a_i,b_j≠0)
このとき、p_i≠q_jなので、
lcm(x,y)=Πp_i^a_i×Πq_j^b_j=xy
(⇐)
最大公約数gとする。x=ga,y=gbとおく。
このとき、aとbは互いに素より、lcm(x,y)=gab
lcm(x,y)=xyより、gab=g^2ab
ab≠0よりg=0,1
gは正なので、g=1より、xとyは互いに素。
連続する2数、xとx+1は互いに素。
xとx+1の最大公約数gとすると、
(x+1)-x=1もgの倍数。よって、1の正の約数は1のみだから、g=1。よって、xとx+1は互いに素。
xとy,xとzが互いに素である⇔xとyzが互いに素である
(⇒)
仮定より、xとy及びxとzは共通の素因数を持たない。
ここで、yzの素因数の集合=(yの素因数の集合)∩(zの素因数の集合)だから、xとyzは共通の素因数を持たない。
よって、xとyzは互いに素。
(⇐)
対偶を考えれば良い。
xとyまたはxとzの少なくとも一方が互いに素でないとき、xとyzが互いに素でないことを示す。
i)xとyが互いに素でないとき、
xとyの最大公約数gとすると、g≧2。
ここで、xもyzもgの倍数だから、xとyzは互いに素でない。
ii)xとzが互いに素でないとき、
xとzの最大公約数hとすると、h≧2。
ここで、xもyzもhの倍数だから、xとyzは互いに素でない。
よって、対偶が示されたので、元の命題も示された。
xとyが互いに素⇔x+yとxyが互いに素
(⇒)
背理法で示す。
x+yとxyが互いに素でないと仮定する。
このとき、その2数が共通してもつ素因数が少なくともひとつ存在し、そのひとつをpとする。
xyがpの倍数でpは素数より、xがpの倍数またはyがpの倍数。
xがpの倍数のとき、x+yもpの倍数なので、y=(x+y)-xもpの倍数。
同様に、yがpの倍数のときも、xもpの倍数と分かる。これは、xとyが互いに素であることに矛盾する。よって、題意が示された。
(⇐)
対偶を示す。xとyが互いに素でない⇒x+yとxyは互いに素でない。
xとyの共通する素因数をpとする。
このとき、x+y及びxyは共にpの倍数なので、これらは互いに素でない。
よって、対偶が示されたので、題意が示された。
今回示した命題はどれも簡単なものですが、特に連続する2数が互いに素という性質は整数の証明問題でけっこう使えます！
では、今回はここまでで！！
↓twitterやってます！
