ページ1:

整数の性質
n進法
テク
テク
N
テク
テク
....
ユーグリットの互除法
どうも、ユーグリットです

ページ2:

例2
(1) 2436の最大公約数、最小公倍数
パターン
24
36
○最大公約数(GC.M)
212
18
○最小公倍数(L.C.M)
6
9
2 3)
最大公約数:12 最小公倍数 : 72
(2)2490の最大公約数、最小公倍数
パターン2
①それぞれ素因数分解
winner
24=23-3
90=2.3.5
最小公倍数
最大公約数
2が3つ
VS
2がか
2が3つ
②が1つ
36115
VS
3が2つ
3が2つ
3が1つ
5が1つ
VS
5が1つ
:.GCM:6
LCM:360
(3) 28,84,180の最大公約数と最小公倍数
2
28
84180
0
最大公約数
14
42
90
○最小公倍数
7
21
45
3
45
最大公約数:4
最小公倍数:1260
15

ページ3:

~約数と倍数~
基本形:( )( )=整数の形にする
積
例
(1)(x-2)(y+3)=5を満たす整数
(x-2,y+3)=(1,5) (5,1) (-1,-5) (-5,-1)
.: (x,y)
=(3,2),(7-2) (1-8) (-3,-4)
(2)xy+4x-3y=15を満たす整数
xy+4x-3y=15
((x-3)(y+4)=15-12
(x-3)(y+4)=3
注意!!
符号を変えずに移行する
(-3,y+4)=(1,3),(3,1) (-3-1),(-1,-3)
.. (x,y) = (4,-1), (6,-3), (0,-5), (2-7)
(3)xy+8x-2y=24を満たす整数
(x-2)(y+8)=24-16
=8
(x-2y+8)=(1,8)(8.1)(-1,-8)(-8,-1) (2,4) (4,2) (-2,-4) (14,-2)
(x,y)
=(3,0)(10,-7)(1,-16) (-6,-9) (4,-4) (6)-6) (0.1) (-2,-10)

ページ4:

D
例3
れは正の整数とすると18の最小公倍数が180であるようなんをすべて求めよ
①18:180を素因数分解する
18:2.32
180=22-32-5
〔証明]
例
[22.5(3の正の約数)=20-1.20.3, 2009
n=20,60,180
aは自然数とする。 atろは4の倍数であり、at4は7の倍数であるとき、atllは28の倍数
a+3=4mat4=7m (minは自然数)と表される
atll: at3+8=4m+8=4(m+2)-①
atll:a+4+7:7n+7=7(n+1)-②
①②より、atllは4かつ7の倍数である。
よって atllは4つの最小公倍数 28の倍数である (Q.E.D.)
互いに素
①2.3の場合
2と3の最大公約数はしなので互いに素である
② 3.7の場合
3とつの最大公約数は1なので互いにである
③ 15.18の場合
15と18の最大公約数は3なので互いに素ではない

ページ5:

例5
(1)最大公約数に、最小公倍数が72である2つの自然数a,bの組。(ただし、acb)
a=12d,b=126'
最小公倍数は
120b'=72
(a,bは自然数)
a'b'は'b'で互いに素であるから
ab=6
(a,b)=(1,6)(
(a,b)=(272) (24,36)
(2)1/2のいずれかに掛けても積が自然数となる分数のうち、最も小さいものを求めよ
例6
o (a,b=自然数)
15
22
b
a
・は自然数となるからaは22の倍数,bは15の約数
誤とは自然数となるからひは35の倍数、6は20の約数
a:66,b=5
66
a.bは整数とするassで割ると3余り、ba5で割ると4余る。次の数を5で割ったときの余りを求めよ。
a=5kt36=52+4(kって=整数)
(1) atb
(5k+3)+(57+4)
350k+777
2
証明
例7
(2) 2a+3b
2(5k+3)+3(5P+4)
=10476+152+1
=5(2k+37) 418
(3) ab
(5k+3)(+4)
(4) atth²
(5613)+(544)
=25130k+2501407+16
=5(Sks++)ナ
3.
2
こち(5k+bk+52 +81) +16
L
(1)奇数の2乗からは引いた数は8の倍数である
奇数は2k+1(k=整数)と表される
(2k +1)²-1=4k² 74k = 4/2 (k+1) -①
k(kt1はこの倍数であるから、①は8の倍数である(Q.E.D)

ページ6:

(2) 連続する2つの偶数の2乗の和から4を引いた数は16の倍数である
連続する2つの偶数は2k,2k+2 (k= 整数)と表される
(2k)+(2142)~4=41+4k²+81c+4-4=8k(k+1)
-①
K(k+1)は2の倍数であるから、①は16の倍数である(Q.E.D)
(3)で割ったときの余は2ではない(nは整数)
すべての整数は整数を用いて3k.3土で表される
[i]んころのとき
[2]nsのとき
m²=91=3.3k²
=(3K上げ=9kI6k+1=3(3k±2k)+1
よっていずれの場合もんを割ったときの余りは2ではない
(4)²が4で割り切れないとき、その余りは1である
すべての整数は整数を用いて2k,2k+1と表される
[1]n=2kのとき
h² 4k² = 2.2.k²
2
[2]n=zkt1のとき
n2=(2x+1)^2=4tk+1=4(ktk)+1
よっていずれの場合もが4で割り切れないときその余りは1である
例8
108以下の自然数で108と互いに素であるものの個数
①素因数分解
108=2.33
2倍3倍 6倍
⇒>2の倍数でも3の倍数でもない自然数
108-(54+36-18)=36
36コ
+
36
18 18 18

ページ7:

例9
5つになので×
24>になので×
1~12までの自然数の積 N=1.2.3.4.12ついて、Nを計算すると、
末尾には口を連続して何個ならぶか。
①10:2.5であるからNを素因数分解したときの2と5の素因数の個数を調べる
5の倍数 5,10
素因数5の個数は2つ
2の倍数 2,4,6,8,10,1
素因数2の個数は10コ
よって、末尾には10コ並ぶ
22の倍数 4,8,12
での倍数
8
暗記!!
和差積の余
①atbをmで割った余りはrtyをmで割った余りに等しい
②a-bmで割った余りは'mで割った余りに等しい。
③ abamで割った余mで割った余りに等しい
例10
(1)71006で割った余り
(2) 2300
716 =
[ ... ]
2÷7:0...5
余り=1
++
余=5

ページ8:

Dato
~合同式~
性質
①aza (modm)
② a=b(modm)のときbia(modm)
③ a bic (modm)のときac(modm)
accmodm); b=d(modm)のとき
| atb= ctd (modm) 2a-bc-d (mod m)
3 ab= cd Cmod m)
3の証明
例
4ack cmod m)
a=c(modm), bid (modm)のとき
整数?でを用いてa-c=ml,b-d=ms'と表される
ab-cd=ab-adtad-cd=acbd) +d (a-c)=ami+dml=mcal+d)
ab-cdがmの倍数になっているからab=cd (modm)が成り立つ。(Q.E.D.)
(1) 151007で割った余り
15=1(mod 7)より15100 1100 1(mod 7)
余りは1
例に
1,nを4で割った余りが2であるとき(nは整数)
(1)W529で割った余
25 = 32 = 5(moda)
余りは5.
(2) 2n+1で割った余
2n thtl = 2.2 +2+1=11=2 (moda)
余りは2

ページ9:

~ユークリッドの互除法~
(定理)
例1
自然数a,bについて、aをbで割ったときの余りをとすると、
aとbの最大公約数は、berの最大公約数に等しい。
0
最大公約数
(1) 391と299
391÷299=1あまり92
299÷92=3あまり 23
92÷23:4あまり
(2) 2512と674
最大公約数は23
登場したら
終了
2512÷674=3あまり490
122÷62=1あまり60
674÷490=1あまり184
62÷60=1あまり2
490÷184=2あまり122
60÷2=30あまりの
184÷122=1あまり62
最大公約数は2
0
方程式の整数解
(3) 3x+4y=1
3x+4y=1…①を満たす整数解の一つはx=1,y=l。①に代入すると
3・(-1)+4.1=1
①-②
3(x+1)+4(1-1)=0.③
3と4は互にに素であるから③より
x+1=4k -1=-3k
∴x=4k-1,y=-3k+1 (ki整数)

ページ10:

(4) 31x+22y=3
31x+22y=3…①
まず、31x+22y=1の整数解を1つ求める
x=5yo-7
31.5 +22 (-7) = 1 ... (2)
x3 31.15722 (-21) = 3 ... (3)
31(x-15)+22(y+21) 20
31と22は互いに素であるから、x-5=22kg+21-3/k
2=22k+15,y=-31k-21 (ki整数)
○等式を満たす整数x、yの組を求める
(5)24x+1y=1
24と17に互除法の計算を行う
24=17.1+7
17=7.2+3
〃
7:3.2+1
になると終了
7=24-17-1
3=17-7.2
17-3-2
よって17-3-2=017-7.2).2=7.5+1.6-2)=(24-17-1)・5+7(-2)
= 24.5+17⋅(-1) ... @
よって求める整数解の1つはx=5,y=-7
(6)26x+lly=1
a=26,b=11 とおくと
26:11.2+4
11=4-2+3
4-3-141
14=26-11.2=a-2h
13=11-4-2=b-za+4b=-2at5b
1=4-3-1=(a-26)-(-2a+b)=3a-7b
よって求める整数解の1つはところ、yニーク

ページ11:

(1)30212y=5
まず30x+17y=1を求める
a=30,b=17とおくと
30=17-1+13
17:13.1+4
13:4.3+1
13:30-17-1=a-b
04=17-13-1=b-atb=-at2b
113-4.3=(a-b)+3a-6b=4a-7b
.30-4 47 (-1)=/ ... O
①×5
30.20+17-(-35)=5
よって求める整数解の1つはx=20,y2-35
○応用問題
(8)11で割ると1余り、5で割ると4余る自然数のうち、3桁で最小のものを求めよ。
求める自然数をんとすると、
n=1lx+1、n=5y+4(xyi整数)と表される。
よって 11x+y+4 すなわち11xyころ…①
x=1,y=2は1つ-5y=1の整数解の1つであるから
11.1-5.2=1
1
両辺に3を掛けると
5:11.3-5.6=3
①-②から
11(x-3)-5(12-6)=0
いとらは互いに素であるから、③を満たす整数水は
x-3=5k すなわち x=5k+3(ki整数)
n=11x+1=11(5k+3)+1=55k+34
55k+34が3桁で最小の自然数となるのはk=2のときで
n=55-2+34=144
144
キ

ページ12:

~小数~
○有限小数
例)1/16=0.3.1/8=0.125など…
○無限小数
7
一有限
小数
-180
102,8
など
例)/3=0.333... 12/2=0.3181818... 「2=1,41421356... など
○循環小数
2.
無限-
Br
例)123=0.3, 1/12=0.3182=1.16.17=0.142857
例2
①分数方を小数で表したとき、小数で表したときの小数第50位
11=0.142857
50÷6=8...2
4
②分数量を小数で表したとき、小数第100位
12=0.692307
(100-2)÷4=24.2
○既約分数:分母と分子が互いに素
例3
次の分数のうち有限小数で表されるものを選べ
5
2
ナ
4
33
40
52
ナ
55
125
7
9
2
4140 ) 55
125
1,75
0.15
0,225 0.1923076 0.036 0,008
+

ページ13:

Date
~進法~
○10進法
123
=1×10^+2×10'+3×10°
○2進法
…+□×22+1x2+□×20
03進法
いい
ロ
3
〇違法→10進法
例
(1) 110101(2) 表われている省略
=1x2+1×2+0x23+1×2+0×2+1×2
=32+16+0+4+0+1
:53
(2)2041(5)
=2.5'+0.3°+4.3+1.30
=54+ナ
(3) 0.101 (2)
こ
0.5+O+0.125
=0.625
○10進法→進法
例5
(1)77[3進法]
3/77
3/25
38
2
322
0
いい
2212 (3)
2
×1
=67
なぜ?
(4)0,342(5)
=1/2x+1/x+12
=0.6+0.16+0.016
=0.776
77まで割っ
り
77=2×33+2×3+1×3+2×30
次に
すで割った余
(2)101[3進法〕
3)101
333 ... 2
3,
3
3 ... 2
0
0.1
10202(3)

ページ14:

Dialo
(3) 0.8125[2進法コ
0.8125
0.6253
¥12500
x
2
0,5000
2
1.0000
2:0なので
0.1101
m進法→進法
Point!
m進法→10進法→進法
例6
(1)345(7)を5進法
7進法→10進法
10進法→5進法
5/180
5 36...0
W
345(7)=3・7+4・7+5・7
=147+28+5
=180
5
...2
O...!
1210(5)