平成２４年４月２９日

[流れ星]

　　　　　第２７３回数学的な応募問題解答

　　　　　　＜解答募集期間：４月8日〜4月29日

［合同式］

平成２４年から実施される新学習指導要領（数学）の科目「数学A」は「場合の数と確率」「整数の性質」「図形の性質」の３つの内容から構成されています。「整数の性質」の中に「合同式」の考えがあります。

これは、ａ−ｂが自然数ｃで割り切れるときに、aとｂはｃを法として合同であるといい、a≡ｂ（mod ｃ）と表す。すると、次の性質が成り立ちます。

a≡ｂ（mod ｍ）、ｃ≡ｄ（mod ｍ）ならば

（１）加法　a＋ｃ≡ｂ＋ｄ（mod ｍ）

（２）減法　a−ｃ≡ｂ−ｄ（mod ｍ）

（３）乗法　aｃ≡ｂｄ（mod ｍ）　

＜注：４月９日１０日　青に訂正　指摘された八木さんに感謝します。＞

（４）べき乗　a^ｎ≡ｂ^ｎ（mod ｍ）　ｎは自然数

問題１：次の合同式を解け。２５６ｘ≡１７９（mod ３３７）

問題２：次の１次不定方程式を解け。

（１）３９ｘ＋４７ｙ＝４１５１　　　（２）３２ｘ＋５７ｙ−６８ｚ＝１

問題３：次の連立合同式を解け

（１）２ｘ＋７ｙ≡１（mod １３），５ｘ＋１０ｙ≡２（mod １３）

（２）ｘ≡３（mod ５），ｘ≡４（mod ７），ｘ≡５（mod ９）　

ＮＯ１「uchinyan」 04/08 15時30分受信 更新4/29

まずは，最初にある合同式の性質を少し拡張して簡単に証明しておきましょう。

a ≡ b (mod m)，c ≡ d (mod m) とします。

(1) 加法 a + c ≡ b + d (mod m)

(a + c) - (b + d) = (a - b) + (c - d) で，これが m の倍数だから。

(2) 減法 a - c ≡ b - d (mod m)

(a - c) - (b - d) = (a - b) - (c - d) で，これが m の倍数だから。

(3) 乗法 ac ≡ bd (mod m)

ac - bd = (a - b)c + b(c - d) で，これが m の倍数だから。

(4) べき乗 a^n ≡ b^n (mod m)，n は自然数

a^n - b^n = (a - b)(a^(n-1) + a^(n-2)b + … + ab^(n-2) + b^(n-1)) で，これが m の倍数だから。さらに，後で使うので，

(5) 除法，c と m が互いに素のとき ac ≡ bc (mod m) ならば a ≡ b (mod m)

ac - bc = (a - b)c が m の倍数で，c と m が互いに素なので，a - b が m の倍数だから。c と m が互いに素ではないときには，

残念ながら，単純に割ることはできず，簡単にはいきません。

以上の準備の下に解いていきます。

問題１：

256x ≡ 179 (mod 337)

2 と 337 は互いに素なので，mod 337 で

256x ≡ 179

256x + 0 ≡ 179 + 337　性質(1)

256x ≡ 516　両辺の計算

64x ≡ 129　性質(5)

64x + 0 ≡ 129 + 337　性質(1)

64x ≡ 466　両辺の計算

32x ≡ 233　性質(5)

32x + 0 ≡ 233 + 337　性質(1)

32x ≡ 570　両辺の計算

16x ≡ 285　性質(5)

16x + 0 ≡ 285 + 337　性質(1)

16x ≡ 622　両辺の計算

8x ≡ 311　性質(5)

8x + 0 ≡ 311 + 337　性質(1)

8x ≡ 648　両辺の計算

x ≡ 81　性質(5)

つまり，x ≡ 81 (mod 337)，になります。

(別解)

ちょっと気付かないですが．．．mod 337 で

256x ≡ 179

(337 - 81)x ≡ 179　左辺の計算

337x - 81x ≡ 179　左辺の計算

337x - 81x - 337x ≡ 179 - 0　性質(2)

- 81x ≡ 179　両辺の計算

81x ≡ - 179　性質(3)

81x + 0 ≡ - 179 + 337 * 20　性質(1)

81x ≡ 6561　両辺の計算

81x ≡ 81 * 81　右辺の計算

x ≡ 81　性質(5)

面倒なので，以下では，使った性質に関していちいち示さないことにします。

問題２：

(1) 39x + 47y = 4151

- 8x ≡ 39x ≡ 4151 ≡ 15 (mod 47)

8x ≡ -15 ≡ 32 (mod 47)

x ≡ 4 (mod 47)

そこで，t を整数として，

x = 47t + 4，y = - 39t + 85

(別解)として，最初に y を求めると，

8y ≡ 47y ≡ 4151 ≡ 17 (mod 39)

8y ≡ 17 ≡ 56 (mod 39)

y ≡ 7 (mod 39)

そこで，s を整数として，

x = - 47s + 98，y = 39s + 7

になりますが，s = - t + 2 で両者は同じものです。

まぁ，これは当然ですね。

(2) 32x + 57y - 68z = 1

mod 57 で，

32x - 68z ≡ 1

32x ≡ 68z + 1 ≡ 68z + 58

16x ≡ 34z + 29 ≡ 34z + 86

8x ≡ 17z + 43 ≡ 74z + 100

4x ≡ 37z + 50 ≡ 94z + 50

2x ≡ 47z + 25 ≡ 104z + 82

x ≡ 52z + 41

そこで，s，t を整数として，

x = 57s + 52t + 41，z = t

で，y は元の式に x，z を代入して，

32(57s + 52t + 41) + 57y - 68(t) = 1

57y = - (32 * 57)s - (32 * 52 - 68)t + (1 - 32 * 41)

y = - 32s - 28t - 23

そこで，s，t を整数として，

x = 57s + 52t + 41，y = - 32s - 28t - 23，z = t

もちろん，s，t の自由度で他の表現もあり得ます。

問題３：

(1) 2x + 7y ≡ 1 (mod 13)，5x + 10y ≡ 2 (mod 13)

4x + 14y ≡ (2x + 7y) * 2 ≡ 1 * 2 ≡ 2 ≡ 5x + 10y (mod 13)

x ≡ 4y (mod 13)

2x + 7y ≡ 2(4y) + 7y ≡ 15y ≡ 1 (mod 13)

2y ≡ 15y ≡ 1 ≡ 14 (mod 13)

y ≡ 7 (mod 13)

x ≡ 4y ≡ 28 ≡ 2 (mod 13)

(2) x ≡ 3 (mod 5)，x ≡ 4 (mod 7)，x ≡ 5 (mod 9)

x ≡ 3 (mod 5) より，a を整数として x = 5a + 3 です。そこで，

x ≡ 5a + 3 ≡ 4 (mod 7)

5a ≡ 1 ≡ 8 ≡ 15 (mod 7)

a ≡ 3 (mod 7)

つまり，b を整数として a = 7b + 3，x = 5(7b + 3) + 3 = 35b + 18 です。そこで，

x ≡ 35b + 18 ≡ 5 (mod 9)

35b ≡ - 13 ≡ - 4 ≡ 5 (mod 9)

7b ≡ 1 ≡ 10 ≡ 19 ≡ 28 (mod 9)

b ≡ 4 (mod 9)

つまり，c を整数として b = 9c + 4，x = 35(9c + 4) + 18 = 315c + 158 になります。

(別解)

7 * 9 ≡ 63 ≡ 3 (mod 5)，5 * 9 ≡ 45 ≡ 3 (mod 7)，5 * 7 ≡ 35 ≡ 8 (mod 9)

7 * 9 * 2 ≡ 6 ≡ 1 (mod 5)，5 * 9 * 5 ≡ 15 ≡ 1 (mod 7)，5 * 7 * 8 ≡ 64 ≡ 1 (mod 9)

なので，

x ≡ 7 * 9 * 2 * 3 + 5 * 9 * 5 * 4 + 5 * 7 * 8 * 5 (mod 5 * 7 * 9)

x ≡ 378 + 900 + 1400 ≡ 2678 ≡ 158 (mod 315)

これは，いわゆる中国人の剰余の定理ですね。

(感想)

いよいよ高校でも合同式を習うのですね。

合同式は通常の等式と似ていて便利なのでこれはいいことです。

ただ，通常の等式と違って割り算は要注意ですが。

そこをしっかり理解すれば，大学レベルの群論への視界も開けるし，

個人的には何かうれしいし，高校生がうらやましくもあります。

Ｎｏ２「浜田明巳」 04/09 17時35分受信 更新4/29　　

問題１
　　２５６ｘ≡１７９（mod ３３７）
から，
　　−８１ｘ≡−１５８（mod ３３７）
　　∴８１ｘ≡１５８（mod ３３７）
　エクセルのマクロ（Maro1，Macro1_2）で解くと，ｘ≡８１（mod ３３７）となる．

問題２（勝手にｘ，ｙ，ｚは整数という条件を付けさせていただきます．それとも不定方程式と銘打った段階で，自動的に整数を解とする方程式となるのでしょうか）
（１）３９ｘ＋４７ｙ＝４１５１
　−１０００≦ｘ≦１０００，−１０００≦ｙ≦１０００の範囲で，エクセルのマクロ（Macro21）で解くと，
　　(ｘ，ｙ)＝(４，８５)，(５１，４６)，(９８，７)，………
という解が得られる．
　この結果から，ｘ＝４７ｍ＋４，ｙ＝３９ｎ＋８５（ｍ，ｎは整数）となることが分かり，与える方程式に代入すると，
　　３９(４７ｍ＋４)＋４７(３９ｎ＋８５)＝３９・４７(ｍ＋ｎ)＋(３９・４＋４７・８５)＝３９・４７(ｍ＋ｎ)＋４１５１＝４１５１
　　∴ｎ＝−ｍ
　　∴(ｘ，ｙ)＝(４＋４７ｍ，８５−３９ｍ)（ｍは整数）

（２）３２ｘ＋５７ｙ−６８ｚ＝１
　３２＝２^5，５７＝３・１９，６８＝２^2・１７であるので，係数の絶対値の最小公倍数は，
　　２^5・３・１７・１９＝３１００８
　故に
　　ｘ＝３１００８／３２・ｍ＋ａ，ｙ＝３１００８／５７・ｎ＋ｂ，ｚ＝３１００８／６８・ｋ＋ｃ（ｍ，ｎ，ｋ，ａ，ｂ，ｃは整数）
とすることができる．
　与方程式に代入すると，
　　３２(３１００８／３２・ｍ＋ａ)＋５７(３１００８／５７・ｎ＋ｂ)−６８(３１００８／６８・ｋ＋ｃ)＝１
　　∴３１００８(ｍ＋ｎ−ｋ)＋３２ａ＋５７ｂ−６８ｃ＝１
　故にｍ＋ｎ＝ｋとして，３２ａ＋５７ｂ−６８ｃ＝１となるａ，ｂ，ｃを１組求めればよい．
　エクセルのマクロ（Macro22）で，−１００≦ｘ≦１００，−１００≦ｙ≦１００，−１００≦ｚ≦１００の範囲で，与方程式を満たし，ｘ，ｙ，ｚの絶対値の和を最小にする組を求めると，
　　(ｘ，ｙ，ｚ)＝(−１，−３，−３)
　故に
　　ｘ＝９６９ｍ−１，ｙ＝５４４ｎ−３，ｚ＝４５６(ｍ＋ｎ)−３（ｍ，ｎは整数）
となる．

問題３
（１）２ｘ＋７ｙ≡１（mod １３），５ｘ＋１０ｙ≡２（mod １３）
　２ｘ＋７ｙ＝１３ｍ＋１，５ｘ＋１０ｙ＝１３ｎ＋２（ｍ，ｎは整数）として，エクセルのマクロ（Macro31）で解くと，
　　(ｘ，ｙ)＝(２，−６)，(２，７)，(−１１，−６)，(−１１，７)，………
となるので，
　　(ｘ，ｙ)＝(１３ｍ＋２，１３ｎ＋７)（ｍ，ｎは整数）
とすることができる．また確かに，
　　２・２＋７・７＝５３≡１（mod １３），５・２＋１０・７＝８０≡２（mod １３）
であるので，
　　ｘ≡２（mod １３），ｙ≡７（mod １３）

（２）ｘ≡３（mod ５），ｘ≡４（mod ７），ｘ≡５（mod ９）
　０≦ｘ≦１００００の範囲で，エクセルのマクロ（Macro32）で解くと，
　　ｘ＝１５８，４７３，７８８，………
となる．
　５，７，９の最小公倍数は３１５なので，
　　ｘ＝３１５ｎ＋１５８（ｎは整数）
であり，
　　ｘ≡１５８（mod ３１５）

（マクロ）
Option Explicit
Sub Macro1() '256*x≡179(mod 337)
    Dim x As Long
    Dim retsu As Integer
    Sheets("Sheet1").Select
retsu = 1
    Cells(1, retsu).Value = 0
    For x = 0 To 337 - 1
      If (256 * x) Mod 337 = 179 Then
        Cells(1, retsu).Value = Cells(1, retsu).Value + 1
        Cells(Cells(1, retsu).Value, 2).Value = x
        Range("B" & Cells(1, retsu).Value).Select
      End If
    Next x
    Range("B1").Select
End Sub
Sub Macro1_2() '256*x≡179(mod 337) → 81*x≡158(mod 337)
    Dim x As Long
    Dim retsu As Integer
    Sheets("Sheet1").Select
retsu = 1
    Cells(1, retsu).Value = 0
    For x = 0 To 337 - 1
      If (81 * x) Mod 337 = 158 Then
        Cells(1, retsu).Value = Cells(1, retsu).Value + 1
        Cells(Cells(1, retsu).Value, 2).Value = x
        Range("B" & Cells(1, retsu).Value).Select
      End If
    Next x
    Range("B1").Select
End Sub
Sub Macro21()
    Dim x As Long
    Dim y As Long
    Dim retsu As Integer
    Sheets("Sheet1").Select
retsu = 4
    Cells(1, retsu).Value = 0
    For x = -1000 To 1000
      For y = -1000 To 1000
        If 39 * x + 47 * y = 4151 Then
          Cells(1, retsu).Value = Cells(1, retsu).Value + 1
          Cells(Cells(1, retsu).Value, retsu + 1).Value = x
          Cells(Cells(1, retsu).Value, retsu + 2).Value = y
          Range("E" & Cells(1, retsu).Value).Select
        End If
      Next y
    Next x
    Range("E1").Select
End Sub
Sub Macro22()
    Dim x As Long
    Dim y As Long
    Dim z As Long
    Dim retsu As Integer
    Dim wa As Long
    Dim min As Long
    Dim deta As Integer
    Dim gyou As Integer
    Sheets("Sheet1").Select
retsu = 8
    Cells(1, retsu).Value = 0
    min = 1000000
    For x = -100 To 100
      For y = -100 To 100
        For z = -100 To 100
          If 32 * x + 57 * y - 68 * z = 1 Then
            Cells(1, retsu).Value = Cells(1, retsu).Value + 1
            Cells(Cells(1, retsu).Value, retsu + 1).Value = x
            Cells(Cells(1, retsu).Value, retsu + 2).Value = y
            Cells(Cells(1, retsu).Value, retsu + 3).Value = z
            Range("I" & Cells(1, retsu).Value).Select
wa = Abs(x) + Abs(y) + Abs(z)
            If min > wa Then
              min = wa
            End If
          End If
        Next z
      Next y
    Next x
deta = 0
gyou = 1
    While deta = 0 And gyou <= Cells(1, retsu).Value
wa = Abs(Cells(gyou, retsu + 1).Value) + Abs(Cells(gyou, retsu + 2).Value) + Abs(Cells(gyou, retsu + 3).Value)
      If wa = min Then
deta = 1
        Range("I" & gyou).Select
      Else
gyou = gyou + 1
      End If
    Wend
End Sub
Sub Macro31() '2*x+7*y≡1(mod 13), 5*x+10*y≡2(mod 13)
    Dim x As Double
    Dim y As Double
    Dim m As Integer
    Dim n As Integer
    Dim retsu As Integer
    Sheets("Sheet1").Select
retsu = 13
    Cells(1, retsu).Value = 0
    For m = -50 To 50
      For n = -50 To 50
        x = (10 * (13 * m + 1) - 7 * (13 * n + 2)) / (2 * 10 - 7 * 5)
        y = (-5 * (13 * m + 1) + 2 * (13 * n + 2)) / (2 * 10 - 7 * 5)
        If Int(x) = x And Int(y) = y Then
          Cells(1, retsu).Value = Cells(1, retsu).Value + 1
          Cells(Cells(1, retsu).Value, retsu + 1).Value = x
          Cells(Cells(1, retsu).Value, retsu + 2).Value = y
          Range("N" & Cells(1, retsu).Value).Select
        End If
      Next n
    Next m
    Range("N1").Select
End Sub
Sub Macro32()
    Dim x As Long
    Dim retsu As Integer
    Sheets("sheet1").Select
retsu = 17
    Cells(1, retsu).Value = 0
    For x = 0 To 10000
      If x Mod 5 = 3 And x Mod 7 = 4 And x Mod 9 = 5 Then
        Cells(1, retsu).Value = Cells(1, retsu).Value + 1
        Cells(Cells(1, retsu).Value, retsu + 1).Value = x
        Range("Q" & Cells(1, retsu).Value).Select
      End If
    Next x
    Range("Q1").Select
End Sub　　

皆さん、答えがわかったら、一部でも構いませんから、解答とペンネームを添えて、

メールで送ってください。待っています。