と
(1)
103
| 次の1次不定方程式の解を1つ見つけよ。
143x+43y=1
るようにぃの値を定めよ。
(2) nを20以下の自然数とする。 5n+29とn+3の最大公約数が7とな
ポイント
(1) 特殊解を見つけよという問題です。 143と43は最大公約数が1 (互いに素)
なので、割り算を次々と実行していくと、 必ず1が出てきます。 これから式
す。
変形すると,特殊解が見つかります。
(2)a=bg+rのr の部分が定数になるように式変形して, 互除法の原理を使いま
解答
(1)割り算を実行すると
143 = 43.3 + 14
･･･ ← 143÷43 商3. 余り14
43 = 14.3 + 1)
←43÷14商3,余り1
これより,
1=43-14・3②を1について解いた
=43-3 (143-433)
①を14=143-43・3と変形し代入
= (-3)・143 +(1 + 9) 43143と43注目し整理
= (-3)143 + 10・43
よって, 143x + 43y=1の解のひとつは
(x,y) = (-3, 10)
(2)5 + 29 = (n + 3)5 + 14 ←
a=bg+rのrが定数となるように変形
+3と14の大小は気にしなくてよい)
g(5n + 29, n + 3) = g (n + 3,14)
よって, g(5n + 29, n+3)=7であるためには,n+3 が7の倍数か
つ奇数であればよい。よって, 1≦x≦20より
n+3=7,21
.. n=4, 18
n+3が7の倍数かつ偶数
のときは,g (n+3,14)=14
で不適となることに注意!!
パターン103 ユークリッドの互除法
21
