1 約数と倍数 2 Euclidの互除法

(No.1)
数の世界（日比野）
1
約数と倍数
整数 a, b, c, . . . に共通な約数を公約数
公約数
整数 a と自然数 b に対して,
a = qb + r,
0<
=r<b
正の公倍数
存在する.
かく.
a
b
という.
の整数である. これを
を越えない最大
とかく.
hai
b
• a, b, c, . . . の公倍数を l とすると, {a, b, c, . . .} | l
と
• a, b, c, . . . の公約数を m とすると, m | (a, b, c, . . .)
(1) において, |r| が最小になるようにも取れる.
• {a, b}(a, b) = ab
整数 a と自然数 b に対して,
• (a, b) = 1† のとき,
b
b
a = q 0 b + r0 , − < r0 <
=
2
2
、、、、
となる整数 q 0 と r0 がただ一つ
存在する.
このときの r0 を絶対値最小剰余
a | bc =⇒ a | c
という.
r = 0 のとき∗ , a は b で割り切れるといい, これを b | a
2
Euclid の互除法
問1
とかく.
(i) (377, 290)
(ii) {377, 290}
b | a のとき, a は b の倍数
, b は a の約数
という.
(iii) (2754, 799)
(iv) (481, 299, 195)
• 0
は全ての数の倍数である.
• 1
は全ての数の約数である.
∗
このとき必然的に r 0 = 0 である. なぜか. 考えてみよ.
という.
のうち, 最小のものを最小公倍数という.
これを, {a, b, c, . . .}
このときの q を商, r を非負最小剰余
qは
とかく.
自然数 a, b, c, . . . に共通な倍数を公倍数
(1)
という.
のうち, 最大のものを最大公約数という. これを,
(a, b, c, . . .)
、、、、
となる整数 q と r がただ一つ
(v) (357, 765, 935)
†
この性質を, a と b は互いに素という
(No.2)
数の世界（日比野）
3
• n の約数の個数
素因数分解



 １
自然数 =
素数



合成数
T (n) = (1 + a)(1 + b)(1 + c) · · ·
, 約数が 1 つ
問 2 トランプのクイズ
, 約数が 2 つ
• n の約数の和
, 約数が 3 つ以上
S(n) = (1 + p + . . . + pa ) . . .
p を素数とすると,
=
p | ab =⇒ p | a または p | b
Cf)
pa+1 − 1 q b+1 − 1
···
p−1
q−1
• n の約数の積
6 | 72 だが 6 6 | 9 かつ 6 6 | 8
P (n) = nT (n)/2
bababababababababababababababab
•
任意の自然数 n は
n = pa q b r c · · ·
、、、、、、
の形にただ一通りに
(素因数分解) とすると,
nm = pam q bm rcm · · · ,
(p, q, r, . . . は素数
)
(2)
{n1 , . . . , nm } = pmax(ai ) q max(bi ) rmax(ci ) · · · ,
(n1 , . . . , nm ) = pmin(ai ) q min(bi ) rmin(ci ) · · · .
素因数分解できる.
• {(n1 , l), . . . , (nm , l)} = ({n1 , . . . , nm }, l).
(2) の約数は
px q y r z · · · ,
n1 = pa1 q b1 rc1 · · · ,
..
.
(x = 0, 1, 2, . . . , a; y = 0, 1, 2, . . . , b; z = 0, 1, 2, . . . , c; . . .)
• p が素数 =⇒ p | p Ck .
• n! = pa · · · とすると, a =
で全てである.
P
k
k [n/p ]
=
n−s
.
p−1
‡
問 3 1000! を素因数分解したときの 7 の指数はいくらか.
‡
ここで, n = ah · · · a1 a0 (p) (p 進数表示) とするとき, s = ah + · · · + a1 + a0 .
(No.3)
数の世界（日比野）
4
素数定理
• 双子素数§
bababababababababababababababab
素数の個数は無限である. (Euclid)
• Goldbach の予想
• Eratosthenes のふるい
問 4 30 以下の素数を全て求めよ
• Fermat の (4n + 1) 定理
• Dirichlet の定理
bababababababababababababababab
x 以下の素数の個数を π(x) とすると, 大きな x に対して
• Tchebyscheff の定理
π(x) ;
x
loge x
http://primes.utm.edu
§
p と p + 2 がともに素数 ⇐⇒ p(p + 2) | 4{(p − 1)! + 1} + p (Clement)
(No.4)
数の世界（日比野）
5
6
完全数と Mersenne 数
Fermat 数
n の約数 (n 自身を除く) の和が n に等しいとき, 完全数という.
2m + 1 の形の素数を Fermat 素数という.k
問 5 6, 28 が完全数であることを示し, 28 の次の完全数を見つけてみよ.
n
n 2n Fn = 22 + 1 素数か
0
bababababababababababababababab
1
2
2n − 1
(n > 1) が素数
のとき,
2n−1 (2n
− 1)
3
は完全数である.(Euclid)
4
また, 偶数
5
の完全数はこの形に限る. (Euler)
奇数の完全数はまだ 1 つも見つかっていない. あるかどうかも分かっ
ていない.
2n − 1 の形の素数を Mersenne 素数という.
¶
• 2m + 1 が素数ならば, 正 2m + 1 角形が定規とコンパスだけで作図
できる. (Gauss)
• n 6= l ならば, Fn と Fl は互いに素.
n Mn = 2n − 1 素数か 2n−1 (2n − 1) 完全数
2
3
5
7
11
13
¶
http://www.mersenne.org/
n が素数のとき以外は, 2n − 1 は素数ではない.
k
m = 2n のとき以外は, 2m + 1 は素数ではない.
(No.5)
数の世界（日比野）
7
黄金比
τ=
√
1+ 5
2
を黄金比という.
8
Fibonacci 数列
問6
(i) 1 つがいの親ウサギは 1ヶ月に 1 つがいの子ウサギを生み, 生まれ
た子ウサギは 1ヶ月で親になるとする. 初めに 1 つがいだったら nヶ月
目には何つがいになるか.
(ii) 1 回に一段か二段登ることのできるロボットが n 段の階段を上る. 何通
りの昇りかたがあるか.
(iii) 1 × 1 の正方形 2n 個で, 2 × n の長方形ができている. 1 × 2 の長方形チッ
プ n 個を用いて敷き詰めるとき, 敷き詰め方は何通りあるか.
(iv) 表が続けて 2 回出るまで, コインを投げる. n 回目で終わる方法は何通り
あるか.
fn+2 = fn + fn+1 ,
f1 = f2 = 1
• n が大きいとき,
• fn =
√1
5
fn+1
;τ
fn
{τ n − (−1/τ )n }
• m | n ⇐⇒ fm | fn
• (fm , fn ) = f(m,n)
• 全ての自然数 d に対して, d | fn となる fn が存在する.
(No.6)
数の世界（日比野）
9
Diophantus 方程式
10
整数 a, b, . . . に対して,
合同式
とかく.∗∗
m | (a − b) のとき, a ≡ b (mod m)
ax + by + · · · = k
(3)
bababababababababababababababab
をみたす整数解 x, y, . . . を求める問題を Diophantus 方程式という.

 a≡b
 c≡d
bababababababababababababababab
(3) が解をもつ ⇐⇒ (a, b, . . .) | k
.

 a±c≡b±d
(mod m)
=⇒
 ac ≡ bd
(mod m)
(mod m)
(mod m)
(c, m) = 1 のとき,
ac ≡ bc (mod m) =⇒ a ≡ b (mod m)
問 7 26x + 57y = 2 をみたす整数解 x, y を求めよ.
(c, m) = d > 1 のとき,
ac ≡ bc (mod m) =⇒ a ≡ b (mod
m
)
d
問 9 25683941 を次の数で割ったときの非負最小剰余をそれぞれ求めよ.
(i)
問 8 162x − 47y = 1 をみたす整数解 x, y を求めよ.
9
(ii)
3
(iii)
11
(iv) 7
(v)
13
問 10 2012 年の元日は日曜になるが，この元日から 2910 日後は何曜にな
るか?
問 11
(i) 4642 × 7823 = 36214366 は正しいか?
(ii) 237 × 386 = 91 82
∗∗
剰余の概念と比較してみよ.
(No.7)
数の世界（日比野）
11
一次合同式
bababababababababababababababab
(a, m) = 1 のとき, (4) の解は mod m でただ一つに定まるから, こ
b
れをと書いてみる.
a
2x ≡ 1 (mod 7) は x ≡ 4 (mod 7) だから,
4 ≡
整数 a, b に対して,
ax ≡ b (mod m)
(4)
3x ≡ 1 (mod 7) は x ≡ 5
5 ≡
は
(i) (a, m) = 1 のとき, mod m でただ 1 つの解をもつ.
(ii) (a, m) = d > 1 のとき, d | b
の解をもつ. すなわち, mod
6x ≡ 5 (mod 7) は x ≡ 2
2 ≡
ならば mod m で d 個
m
d
でただ 1 つの解をもつ
6x ≡ 1 (mod 7) は x ≡ 6
6 ≡
(4) を解くことは, Diophantus 方程式: ax + my = b を解くことと同
じことである.
この記法は,
問 12 162x ≡ 1 (mod 47) を解け.
問 13 26x ≡ 2 (mod 57) を解け.
(mod 7).
(mod 7) だから,
1
3
(mod 7).
(mod 7) だから,
5
6
(mod 7).
(mod 7) だから,
1
6
(mod 7).
5
1 1
5
1 1
+ = に対応して, + ≡
2 3
6
2 3
6
4+5≡2
4×5≡6
を満たしている.
(mod 7), つまり,
(mod 7)
を満たしている.
1
1 1
1
1 1
また, × = に対応して, × ≡
2 3
6
2 3
6
問 14 28x ≡ 3 (mod 5) を解け.
問 15 21x ≡ 3 (mod 72) を解け.
1
2
(mod 7), つまり,
(mod 7)
(No.8)
数の世界（日比野）
12
中国剰余定理
問 16 私の年齢は，3 で割ると 1 余り, 5 で割ると 2 余り, 7 で割ると 3 余る.
私の年齢は何か. (孫子算経)
bababababababababababababababab
m1 , m2 , . . . , mn が 2 つずつ互いに素のとき,



x ≡ a1 (mod m1 )


..
.



 x ≡ an (mod mn )
、、、、
をみたす x は mod M でただ一つに決まる. ここで, M =
m1 · · · mn .
(
問 17
x
x
≡ 1
≡ 2
(mod 13)
を解け.
(mod 24)
bababababababababababababababab
m, n が互いに素でないとき, (m, n) = d, {m, n} = l とすると,

 x ≡ a (mod m)
 x ≡ b (mod n)
が解を持つ条件は a ≡ b (mod d)
、、、、
のとき, x は mod l でただ一つに決まる.
(
問 18
x ≡
x ≡
4 (mod 15)
を解け.
10 (mod 21)
である. こ
(No.9)
数の世界（日比野）
13
Wilson の定理
14
bababababababababababababababab
素数 p に対して,
(p − 1)! ≡ −1 (mod p)
Fermat の小定理
bababababababababababababababab
p を素数とする. (a, p) = 1 のとき,
ap−1 ≡ 1 (mod p)
(5)
が成り立つ. また, 逆に (5) が成り立つならば, p は素数である.
(6)
が成り立つ.
問 19 2012 年の元日は日曜になるが，この元日から 1050 日後は何曜にな
るか?
〔注意〕Fermat の小定理の逆, つまり,
a と p が互いに素のとき, (6) ならば, p は素数である
は間違い.
問 20 p = 561 に対して, これを確かめよ.
(No.10)
数の世界（日比野）
15
16
平方剰余
Euler の関数
奇素数 p と互いに素な整数 a に対して
n 以下で n と互いに素になる自然数の個数を ϕ(n) とかく. これを
Euler の関数と言う.
x2 ≡ a (mod p)
が解を持つとき，a は p の平方剰余であるといい， ap = 1
と書く.
a
p = −1
問 22 ϕ(1) から ϕ(10) と ϕ(100) を求めよ.
そうでないときは，平方非剰余であるといい，
と書く. (Legendre の記号)
• 平方剰余と平方非剰余は ( mod p で) 同じ個数ある.
ab
a
b
•
=
p
p
p
bababababababababababababababab
(平方剰余の相互法則)
(第 1 補充法則)
−1
p
(第 2 補充法則)
2
p
0
p
p0
p
p
= (−1)qq
0
= (−1)q
= (−1)q(q+1)/2
• p が素数のとき, ϕ(p) = p − 1
, ϕ(pk ) = pk − pk−1
• n が (2) のように素因数分解されているとき,
問 21
151
5
151
7
,
,
,
を求めよ.
5
151
7
151
1
ϕ(n) = n(1 − )...
p
(No.11)
数の世界（日比野）
bababababababababababababababab
18
問 25 次の循環小数を既約分数の形に表せ.
(a, n) = 1 のとき
aϕ(n) ≡ 1
循環小数
(i) 0.12˙
(ii) 0.12˙ 3˙
(mod n)
˙ 3˙
(iii) 0.12
Cf)Fermat の小定理
(iv) 0.749˙
問 23 5 で割り切れない奇数 N を何倍かすると, 全ての桁を 9 にできること
を示せ.
• 7 を分母とする分数について
問 24
(i) 3123 の下 1 桁を求めよ.
(ii) 3123 の下 2 桁を求めよ.
• 13 を分母とする分数について
〔注意〕ϕ(n) より低いベキで ≡ 1 となることもある.
17
指数
bababababababababababababababab
ae ≡ 1
(mod n) となる最小数 e を n に関して a に対応する指数
n が (2) のように素因数分解されているとき, p に関して
という.
• am ≡ 1 (mod n) =⇒ e | m
10 に対応する指数を e1 , q に関して 10 に対応する指数を
e2 , . . . とすると, n に関して 10 に対応する指数は e =
{e1 , e2 , . . .}
• e | ϕ(n)
特に n が素数 p のとき, e | (p − 1)
.
(No.12)
数の世界（日比野）
19
連分数
問 26 次の数を連分数展開せよ.
162
(i)
=
47
20
循環連分数
無理数 x が
x = [a0 , . . . , a˙i , . . . , a˙j ]
となるとき, 循環連分数という.
bababababababababababababababab
(ii)
57
=
26
x が循環連分数
⇐⇒
x は 2 次無理数
⇐⇒
xは
⇐⇒
x=
˙ 2]
˙ となる無理数 y を求めよ.
問 27 y = [1,
(iii)
√
2=
˙ となる無理数 z を求めよ.
問 28 z = [1]
(iv)
√
3=
bababababababababababababababab
m
(m > n) に対して,
有理数
n
r
m
=
n
(No.13)
数の世界（日比野）
21
無理数の連分数近似
無理数 x = [a0 , a1 , a2 , . . .] に対して,
数列
qn
= [a0 , a1 , . . . , an ] とおくと,
pn
q0 q1 q2
, , ,...
p0 p1 p2
bababababababababababababababab
の極限値は x である.
1
qn • x − < 2
pn
pn



 
 
a0 1
a 1
a 1
q q
 1
··· n
 =  n n−1 
• †† 
pn pn−1
1 0
1 0
1 0
•
‡‡
qn qn−1
pn pn−1
= (−1)n+1
とおくと, (7) より,
a q = ap − bq = (−1)n+1
b p ax − by = (−1)n+1 を解くには,
(9) とおくとき,

 x = p + kb
 y = q + ka
(7)
有理数の連分数展開と合同式
a
有理数が
b
(i) 162x − 47y = 1
a
= [a0 , . . . , an−1 , an ]
b
(8)
(ii) 162x − 47y = −1
(iii) 162x + 47y = 1
(iv) 26x + 57y = 1
q
= [a0 , . . . , an−1 ]
p
!
!
a b
p q
行列の積
=
c d
r s
a b ‡‡
行列式 = ad − bc
c d ap + br
cp + dr
(9)
aq + bs
cq + ds
(mod b) と考えても解ける.
問 29 次の式を満たすすべての整数解 (x, y) を求めよ.
と連分数展開されているとする.
††
(k は任意の整数)
ですべての解が得られる.
もちろん, ax ≡ (−1)n+1
22
a
の連分数展開 (8) に対して,
b
!
(v) 26x + 57y = 2

Download Report