「 整数・証明・計算問題 」一覧

数学I・IIにまたがる分野です。

ユークリッドの互除法[2018 首都大学東京・理・数理科]

ユークリッドの互除法[2018 首都大学東京・理・数理科]

 以下の問いに答えなさい。
(1) 正の整数 p , q , f および整数 r が次の関係をみたしているとする。
 p = fq + r
ただし、 0 ≦ r < q とする。このとき整数 d が p と q の公約数であることと、 d が q と r の公約数であることは同値であることを示しなさい。
(2) 正の整数 k , m の最大公約数を gcd ( k , m ) で表す。 p , q を p > q をみたす正の整数とする。また n ≧ 2 とし、2n - 1 個の正の整数 f1 , f2 , … , fn-1 , r1 , r2 , … , rn が次の関係をみたしているとする。
  p = r1
  q = r2
  r1 = f1 r2 + r3, ( r3 > r2 )
  r2 = f2 r3 + r4, ( r4 > r3 )
    ︙
  rn-2 = fn-2 rn-1 + rn, ( rn > rn-1 )
  rn-1 = fn-1 rn
 このとき、 gcd ( p , q ) = gcd ( rj , rj+1 ) ( j = 1 , 2 , … , n - 1 ) が成り立つことを j に関する数学的帰納法で示しなさい。
(3)  p と q を互いに素な正の整数とする。このとき、 ap + bq = 1 を満たす整数 a , b が存在することを示しなさい。

鳩の巣原理 [2016 神戸大・理(後)]

鳩の巣原理 [2016 神戸大・理(後)]

m を 2 ≦ m ≦ 9 をみたす自然数とする。 xy 平面上の点のうち、 x 座標と y 座標がともに整数のものを格子点という。 x 座標と y 座標がともに -1 , 0 , 1 のいずれかである 9 個の格子点を考える。これらの格子点から異なる m 個の格子点を選ぶ。選ばれた m 個の格子点のうち、どの異なる2点の中点も格子点とならないような m 個の格子点を選ぶ選び方の総数を am とおく。 am ( 2 ≦ m ≦ 9 )を求めよ。

巡回群の直積と位数 [2016 慶應大・理工]

巡回群の直積と位数 [2016 慶應大・理工]

 iを虚数単位とする。次の事実がある。
【事実F】 a , b を互いに素な正の整数とする。このとき、 ( cos 2aπ/b + i sin 2aπ/b)k = cos 2π/b + i sin 2π/b となる整数 k が存在する。
(1) 等式 ( cos 4π/5 + i sin 4π/5 )k = cos 2π/5 + i sin 2π/5 を満たす最小の正の整数 k は   である。
(2) a , b を互いに素な正の整数とし、集合Pを、
P = { z | z は整数 k を用いて ( cos 2aπ/b + i sin 2aπ/b )k と表される複素数 }
で定める。事実Fを考慮すると、集合Pの要素の個数 n(P) は   である。
(3) 事実Fを証明しなさい。
(4) a1 , b1 を互いに素な正の整数とし、a2 , b2 も互いに素な正の整数とする。集合Q1 , Q2
Q1 = { z | z は整数 k を用いて ( cos 2a1π/b1 + i sin 2a1π/b1 )k と表される複素数 }
Q2 = { z | z は整数 k を用いて ( cos 2a2π/b2 + i sin 2a2π/b2 )k と表される複素数 }
で定め、集合Rを
R = { z | z は集合 Q1 の要素と集合 Q2 の要素の積で表される複素数 }
で定める。b1 , b2 が互いに素ならば、集合Rの要素の個数 n(R) は   である。b1 , b2 が互いに素でないとき、それらの最大公約数を d とすれば、集合Rの要素の個数 n(R) は   である。