整数の基本性質の練習問題（全9問・解答つき）

a を b で割った商を q とすると

a=bq+r

である。

a と b の公約数を d とすると、 a も bq も d の倍数であるから、倍数の和と積より、その差 r=a-bq も d の倍数である。よって、 d は b と r の公約数でもある。

逆に、 b と r の公約数を d' とすると、 bq も r も d' の倍数であるから、その和 a=bq+r も d' の倍数である。よって、 d' は a と b の公約数でもある。

すなわち、 a と b の公約数と、 b と r の公約数はすべて一致する。したがって、そのうち最大のものも等しく

gcd(a,b)=gcd(b,r)

が成り立つ。

例として1071と1029の最大公約数を求めてみよう。

1071を1029で割ると、商は1余りは42、すなわち

1071=1029・1+42

となるので、1071と1029の最大公約数は、1029と42の最大公約数と等しい。 ここで得られた、1029と42に関して、再び割り算を行うと

1029=42・24+21

となるので、1029と42の最大公約数は、42と21の最大公約数と等しい。同様にして

42=21・2+0

となるので、42と21の最大公約数は21であることがわかる。すなわち、1071と1029の最大公約数は21である。

a と p の最大公約数は p の約数であるから、 1 または p である。

もし、最大公約数が p ならば、 a は p で割り切れる。

もし、最大公約数が 1 ならば、互いに素な数の性質より、 b が p で割り切れる。

よって、 a,b のうち、少なくとも1つは p で割り切れる。

1. それぞれ計算すると

   2・3+1=7, 2・3・5+1=31, 2・3・5・7+1=211

   であり、どれも1とその数自体以外に正の約数をもたないので、素数である。

2. 素数が有限個 p1,p2,…,pn しかないとする。ここで

   N=p1p2…pn+1

   とおくと、 N はどの pi で割っても1余るので、どの pi でも割り切れない。

   よって、 N 自身が素数であるか、または p1,p2,…,pn 以外の素因数をもつことになり、いずれにしても素数が n 個しかないことに反する。

   したがって、素数は無数にある。

2x+3y=1 ①

を満たす整数解として、 x=−1,y=1 がある。つまり

2・(-1)+3・1=1 ②

①-② より

2{x-(-1)}+3{y-1}=0 ⇔ 2(x+1)+3(y-1)=0 ③

2と3は互いに素であるから、 ax+by=0 の整数解より ③ のすべての整数解は

x+1=3k,y−1=−2k（kは整数） と表せる。

よって、 ① のすべての整数解は

x=3k−1,y=−2k+1（kは整数）

となる。