練習問題
1. 次の不定一次方程式の全ての解を求めよ。解がないときは「解なし」とすること。
(1) 91x − 312y = 39,
(2) 551x − 58y = 152,
(3) 319x + 203y = 87,
(4) 289x + 391y = 85
(5) 222x − 407y = 74,
(6) 367x + 407y = 2
(7) 351x − 539y = 4,
(8) 364x − 378y = 52
解: 例として、(1)、(6)、(8) の解法を載せておく。
(1) まず (91, −312) を求める。ユークリッドの互除法より、
91 = 312 × 0 + 91
312 = 91 × 3 + 39
91 = 39 × 2 + 13
39 = 13 × 3
よって、(91, −312) = 13。これは 39 の倍数なので、問題の方程式は解をもつ。上の式より、
13 = 91 − 39 × 2 = 91 − (312 − 91 × 3) × 2 = 91 × 7 − 312 × 2
よって、91z − 312w = 13 の解の一つとして、z = 7、w = 2 がとれるから、問題の方程式 91x − 312y = 39 の解全体は
x=
39
−312
×7+
k = 21 − 24k,
13
13
y=
39
91
× 2 − k = 6 − 7k,
13
13
(k : 整数)
となる。
(6) まず、(367, 407) を求める。ユークリッドの互除法より、
367 = 407 × 0 + 367
407 = 367 × 1 + 40
367 = 40 × 9 + 7
40 = 7 × 5 + 5
7=5×1+2
5=2×2+1
2=1×2
なので、(367, 407) = 1。これは、2 の倍数なので、問題の方程式は解を持つ。上の式より、
1 = 5 − 2 × 2 = 5 − (7 − 5 × 1) × 2 = 5 × 3 − 7 × 2 = (40 − 7 × 5) × 3 − 7 × 2 = 40 × 3 − 7 × 17
= 40 × 3 − (367 − 40 × 9) × 17 = 40 × 156 − 367 × 17 = (407 − 367 × 1) × 156 − 367 × 17
= 367 × (−173) + 407 × 156
よって、367z + 407w = 1 の解のひとつとして、z = −173、w = 156 がとれるから、問題の方程式 367x + 407y = 2 の
解全体は、
(
)
( )
407
2
× (−173) +
k = −346 + 407k,
x=
1
1
( )
(
)
2
367
y=
× 156 −
k = 312 − 367k,
1
1
1
(k : 整数)
となる。
(8) まず、(364, −378) を求める。ユークリッドの互除法を用いると、
364 = 378 × 0 + 364
378 = 364 × 1 + 14
364 = 14 × 26
よって、(364, −378) = (364, 378) = 14。52 は 14 の倍数ではないので、この方程式は解を持たない。
他の問題も同様に解ける。解答は、
(2)
解なし.
{
(4)
{
(7)
{
(3)
x = 6 + 7k,
y = −9 − 11k
(k : 整数),
{
x = −20 + 23k,
y = 15 − 17k
(k : 整数),
x = 172 − 539k
y = 112 − 351k
(k : 整数),
(5)
x = 4 − 11k,
y = 2 − 6k
(k : 整数),
となる。
2. (1) 110 円の缶コーヒーと 130 円のペットボトルの代金の合計が 2100 円になった。それぞれ何本ずつ買ったか。
(2) ある日の自宅と携帯の電話料金の合計が 290 円だった。1 分あたり 9 円の自宅の電話と、1 分あたり 19 円の
携帯電話をそれぞれ何分ずつ使用したか。
(1) 不定１次方程式
110x + 130y = 2100
⇐⇒
11x + 13y = 210
の解の全体は、
x = 1260 + 13k,
y = −1050 − 11k
(k : 整数)
となる。このとき、x ≥ 0 より、
1260 + 13k ≥ 0
k≥−
=⇒
1260
= −96.9 · · ·
13
y ≥ 0 より、
1050
= −95.4 · · ·
11
よって、x、y ともに正になるためには、k = −96 とすればよい。このとき x = 12、y = 6 なので、缶コーヒー 12 本、
ペットボトル 6 本。
−1050 − 11k ≥ 0
k≤−
=⇒
(2) (1) と同様に考えると、自宅 9 分で携帯 11 分。
3. (1) 10999 を 11 で割った余りを求めよ。
(2) 1001 = 7 × 11 × 13 であることを用いて、1050 を 13 で割った余りを求めよ。
2
(1) 10 ≡ −1 (mod 11) だから、
10999 ≡ (−1)999 = −1 ≡ 10
(mod 10)
となる。よって、10999 を 11 で割った余りは 10。
(2)
1050 = 103×16+2 ≡ (−1)16 · 102 100 ≡ 9 (mod 13)
となる。よって、1050 を 13 で割った余りは 9。
4. 次の一次合同式の解の全体と、n を法としたときの個数を求めよ。解がない場合もある。
(1)
57x ≡ 21 (mod 33)
(3)
23x ≡ 1 (mod 17)
(2)
153x ≡ 54 (mod 68)
(4) 144x ≡ 99 (mod 81)
例として、(1)、(2) を解く。
(1) １次不定方程式
57x + 33y = 21
の解 x の全体を求めればよい。ユークリッドの互除法を用いると、
57 = 33 × 1 + 24
33 = 24 × 1 + 9
24 = 9 × 2 + 6
9=6×1+3
6=3×2
より、gcd(57, 33) = 3 なので、この一次合同式は解をもつ。
3 = 9−6×1 = 9−(24−9×2) = 9×3−24 = (33−24)×3−24 = 33×3−24×4 = 33×3−(57−33)×4 = 57×(−4)+33×7
よって、57w ≡ 3
(mod 33) の解の１つとして w = −4 がとれるから、解の全体は、
x=
21
33
× (−4) + k = −28 + 11k
3
3
(k ∈ Z)
で、解は 33 を法として 3 個ある。
(2) １次不定方程式
153x + 68y = 54
の解 x の全体を求めればよい。ユークリッドの互除法を用いると、
153 = 68 × 2 + 17
68 = 17 × 4
より、gcd(153, 68) = 17 だが、54 は 17 の倍数ではないので、解は存在しない。
他の問題も同様に解ける。答えは、
3
(3) x = 3 + 17k （k は整数）で、17 を法とした解は一意。
(4) x = 44 + 9k で、81 を法とした解の個数は 9 個。
となる。
5. 次の連立一次合同式の解とその個数を求めよ。ただし、解は、法とした数で最小となる正の数を答えること。
{
x ≡ 1 (mod 3)
x ≡ 3 (mod 5)
(1)
(2)
x ≡ 3 (mod 4)
x ≡ 5 (mod 6)
x ≡ 4 (mod 7)
(3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
x ≡ 7 (mod 9)
x ≡ 3 (mod 7)
x ≡ 2 (mod 11)
x ≡ 10 (mod 13)
(4)
例として、(1)、(2) の解法を示す。
(1) 5 と 6 は互いに素。合同式
6u1 ≡ 1
(mod 5)
5u2 ≡ 1 (mod 6)
u1 = 1,
u2 = −1
の解のひとつとして、
が取れるので、
x = 3 × 6 × 1 + 5 × 5 × (−1) = −7 ≡ 23
(mod 30)
が 30 を法として、ただひとつの解になる。
(2) 3、4、7 は互いに素である。
28u1 ≡ 1 (mod 3)
21u2 ≡ 1
(mod 4)
12u3 ≡ 1 (mod 7)
は、それぞれ、解のひとつとして、
u1 = 1,
u2 = 1
u3 = 3
がとれるので、
x = 1 × 28 × 1 + 3 × 21 × 1 + 4 × 12 × 3 = 235 ≡ 67 (mod 84)
が 84 を法としたただひとつの解になる。
(3)、(4) も同様に示せる。答えは、
(3) x = 268 が 315 を法としてただひとつの解。
(4) x = 101 が 1001 を法としてただひとつの解。
となる。
6. オイラーの公式を用いて、次のオイラー関数を計算せよ。
(1)
φ(48)
(2) φ(126)
4
(3)
φ(240)
(1) 48 = 24 × 3 なので、オイラーの公式より、
(
)(
)
1
1
1 2
φ(48) = 48 1 −
1−
= 48 × × = 16
2
3
2 3
である。
(2) 126 = 2 × 32 × 7 なので、オイラーの公式より、
(
)(
)(
)
1
1
1
φ(126) = 126 1 −
1−
1−
= 36
2
3
7
となる。
(3) 240 = 24 × 3 × 5 なので、オイラーの公式より、
(
)(
)(
)
1
1
1
φ(240) = 240 1 −
1−
1−
= 64
2
3
5
となる。
7. (1) 55120 を 124 で割り算したときの余りを求めよ。
(2) 3737 を 108 で割り算したときの余りを求めよ。
(3) 49200 を 125 で割り算したときの余りを求めよ。
(4) 100200 を 27 で割り算したときの余りを求めよ。
(1) gcd (55, 124) = 1 なので、オイラーの定理を用いることができる。φ(124) = 50 だから、5560 ≡ 1 gcd (mod 124)。
よって、
55120 = (5560 )2 ≡ 1
(mod 124)
よって、55120 を 124 で割った余りは 1。
(2) gcd(37, 108) = 1 より、オイラーの定理を用いることができる。φ(108) = 36 だから、3736 ≡ 1 (mod 108)。これ
より、
3737 ≡ 37
(mod 108)
よって、3737 を 108 で割った余りは 37
(3) gcd (49, 125) = 1 なので、オイラーの定理を用いることができる。φ(125) = 100 なので、49100 ≡ 1(mod 125) 。こ
れより、
49200 = 49100×2 ≡ 1 (mod 125)
となる。よって、49200 を 125 で割った余りは 1。
(4) gcd (100, 27) = 1 より、オイラーの定理を用いることができる。φ(27) = 18 だから (100)18 ≡ 1 (mod 27) 。よって、
100 ≡ −8 (mod 27) に注意すると、
100200 = 10018×11+2 = (10018 )11 × 1002 ≡ 1002 ≡ (−8)2 = 64 ≡ 10
となり、100200 を 27 で割ったあまりは 10 になる。
5
(mod 27)
8. オイラーの定理を用いて、次の１次合同式を解け。
(1) 7x ≡ 3 (mod 24)
(3) 121x ≡ 1
(mod 25)
(2) 11x ≡ 3 (mod 9)
(4) 116x ≡ 6
(mod 13)
(1) gcd(7, 24) = 1 より解は一意に存在する。φ(24) = 8 、72 = 49 ≡ 1 (mod 24) に注意すると、
x ≡ 7φ(24)−1 × 3 = 77 × 3 = (49)3 × 7 × 3 ≡ 21 (mod 24)
よって、解は x = 21 で、これは 24 を法として一意。
(2) (11, 9) = 1 より、解は一意に存在する。φ(9) = 6 、11 ≡ 2 (mod 9) に注意すると、
x ≡ 11φ(9)−1 × 3 = 115 × 3 ≡ 25 × 3 = 96 ≡ 6 (mod 9)
よって、x = 6 で、これは 9 を法として一意。
(3) gcd (121, 25) = 1 より、解は一意に存在する。φ(25) = 20 、44 = 256 ≡ 6 (mod 25) に注意すると、
x ≡ 121φ(25)−1 × 1 = 12119 ≡ (−4)19 ≡ 64 × (−4)3 = 6 × (−24)3 ≡ 6 × 13 = 6
(mod 25)
解は x = 6 で、これは 25 を法として一意。
(4) gcd(116, 13) = 1 より、解は一意に存在する。φ(13) = 12、116 ≡ −1 (mod 13) などに注意すると、
x ≡ 116φ(13)−1 × 6 = 11611 × 6 ≡ (−1)11 × 6 = −6 ≡ 7 (mod 13)
よって、解は x = 7 で、これは 13 を法として一意。
(5) gcd(139, 17) = 1 より、解は一意に存在し、φ(17) = 16、139 ≡ 3 (mod 17)、34 = 81 = −4 (mod 17) 、448 ≡
6 (mod 17) などに注意すると、
x ≡ 139φ(17)−1 = 13915 = 315 = (34 )3 × 33 ≡ (−4)3 × (−7) = 64 × 7 = 448 ≡ 6
(mod 17)
よって、解は x = 6 で、これは 17 を法として一意。
• オイラーの定理を使った後、どう簡単にするかは、もちろん、一通りではありませんし、ここで解いた方法より簡単に
解ける方法があるかもしれません。
6
© Copyright 2024 ExpyDoc
