{"id":78905,"date":"2024-08-17T03:15:35","date_gmt":"2024-08-17T03:15:35","guid":{"rendered":"https:\/\/science-hub.click\/%E6%8B%A1%E5%BC%B5Euclid%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6%E8%A9%B3%E3%81%97%E3%81%8F%E8%A7%A3%E8%AA%AC\/"},"modified":"2024-08-17T03:15:35","modified_gmt":"2024-08-17T03:15:35","slug":"%E6%8B%A1%E5%BC%B5Euclid%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6%E8%A9%B3%E3%81%97%E3%81%8F%E8%A7%A3%E8%AA%AC","status":"publish","type":"post","link":"https:\/\/science-hub.click\/?p=78905","title":{"rendered":"\u62e1\u5f35 Euclid \u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306b\u3064\u3044\u3066\u8a73\u3057\u304f\u89e3\u8aac"},"content":{"rendered":"

\u5c0e\u5165<\/h2>

\u62e1\u5f35 Euclid \u30a2\u30eb\u30b4\u30ea\u30ba\u30e0<\/b>\u306f Euclid \u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u5909\u5f62\u3067\u30012 \u3064\u306e\u6574\u6570a<\/i>\u3068b<\/i>\u304b\u3089\u3001\u305d\u308c\u3089\u306e\u6700\u5927\u516c\u7d04\u6570 (PGCD) \u3060\u3051\u3067\u306a\u304f\u3001\u305d\u308c\u3089\u306e\u4fc2\u6570\u306e\u30da\u30a2\u306e 1 \u3064 de B\u00e9zout (2 \u3064\u306e\u6574\u6570u<\/i>\u3068v<\/i>\u306a\u3069) \u3082\u8a08\u7b97\u3067\u304d\u307e\u3059\u3002 au<\/i> + bv<\/i> = PGCD( a<\/i> , b<\/i> ))\u3002 a<\/i>\u3068b \u304c<\/i>\u4e92\u3044\u306b\u7d20\u3067\u3042\u308b\u5834\u5408\u3001 u \u306f<\/i>b<\/i>\u3092\u6cd5<\/i>\u3068\u3059\u308b a \u306e\u4e57\u7b97<\/a><\/span>\u306e<\/a><\/span>\u9006\u6570<\/a><\/span>\u3067\u3042\u308a\u3001\u3053\u308c\u306f\u7279\u306b\u4fbf\u5229\u306a\u30b1\u30fc\u30b9\u3067\u3059\u3002\u62e1\u5f35Euclid<\/a><\/span>\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306f\u3001\u30c7\u30a3\u30aa\u30d5\u30a1\u30f3\u30c8\u30b9\u65b9\u7a0b\u5f0f<\/a><\/span>ax+by = c \u306b\u89e3\u304c\u3042\u308b\u304b\u3069\u3046\u304b\u3092\u5224\u65ad\u3059\u308b\u305f\u3081\u306e\u52b9\u7387\u7684\u306a\u65b9\u6cd5 (\u5358\u7d14\u306a Euclid \u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3067\u306f\u3059\u3067\u306b\u53ef\u80fd) \u3060\u3051\u3067\u306a\u304f\u3001\u3053\u306e\u5834\u5408\u306e\u7279\u5b9a\u306e\u89e3\u3092\u7c21\u5358\u306b\u8a08\u7b97\u3059\u308b\u65b9\u6cd5\u3082\u63d0\u4f9b\u3057\u307e\u3059\u3002\u4e00\u822c\u7684\u306a\u89e3\u6c7a\u7b56\u3092\u5c0e\u304d\u51fa\u3057\u307e\u3059\u3002<\/p>

\u30e6\u30fc\u30af\u30ea\u30c3\u30c9\u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3068\u540c\u69d8\u306b\u3001\u62e1\u5f35\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306f\u3001\u53ef\u63db\u4f53\u4e0a\u306e 1 \u3064\u306e\u5909\u6570<\/a><\/span>\u3092\u6301\u3064\u591a\u9805\u5f0f\u306a\u3069\u306e\u30e6\u30fc\u30af\u30ea\u30c3\u30c9\u74b0\u306b\u4e00\u822c\u5316\u3057\u307e\u3059\u3002\u6574\u6570\u306e\u5834\u5408\u3068\u540c\u69d8\u306b\u3001\u7d20\u6570\u3068\u306a\u308b\u591a\u9805\u5f0f\u3092\u6cd5\u3068\u3059\u308b\u591a\u9805\u5f0f<\/a><\/span>\u306e\u9006\u6570\u3092\u8a08\u7b97\u3067\u304d\u308b\u305f\u3081\u3001\u591a\u9805\u5f0f\u306e\u30ea\u30f3\u30b0\u4e0a\u306e\u5546\u306b\u3088\u3063\u3066\u69cb\u7bc9\u3055\u308c\u308b\u30ea\u30f3\u30b0\u307e\u305f\u306f\u30dc\u30c7\u30a3\u306e\u9006\u6570\u306e\u8a08\u7b97\u304c\u53ef\u80fd\u306b\u306a\u308a\u307e\u3059 (\u7834\u65ad\u30dc\u30c7\u30a3<\/a><\/span>\u3001\u5b8c\u6210\u30dc\u30c7\u30a3\u306a\u3069)\u3002<\/p>

\n\"\u62e1\u5f35<\/figure>

\u5c0e\u5165\u4f8b<\/h2>

\u305f\u3068\u3048\u3070\u3001Euclid \u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u4f7f\u7528\u3057\u305f GCD 120 \u3068 23 \u306e\u8a08\u7b97\u3092\u8003\u3048\u3066\u307f\u307e\u3057\u3087\u3046\u3002<\/p>
120 \u00f7 23 = 5 \u306f 5 \u306e\u307e\u307e\u3067\u3059<\/td><\/tr>
23 \u00f7 5 = 4 \u306f 3 \u306e\u307e\u307e\u3067\u3059<\/td><\/tr>
5 \u00f7 3 = 1 \u306f 2 \u306e\u307e\u307e\u3067\u3059<\/td><\/tr>
3 \u00f7 2 = 1 \u306f 1 \u306e\u307e\u307e\u3067\u3059<\/td><\/tr>
2 \u00f7 1 = 2 \u306f 0 \u306e\u307e\u307e\u3067\u3059<\/td><\/tr><\/table>

\u3053\u306e\u5834\u5408\u3001\u6700\u5f8c\u304b\u3089 2 \u756a\u76ee\u306e\u884c\u3067\u5f97\u3089\u308c\u305f\u5270\u4f59\u306b\u3088\u308a\u3001GCD \u306f 1 \u306b\u306a\u308a\u307e\u3059\u3002\u3064\u307e\u308a\u3001120 \u3068 23 \u306f\u4e92\u3044\u306b\u7d20\u3067\u3059\u3002\u3053\u3053\u3067\u3001\u524d\u306e\u5206\u5272\u3092\u5225\u306e\u65b9\u6cd5\u3067\u8868\u73fe\u3057\u3066\u307f\u307e\u3057\u3087\u3046\u3002<\/p>
\u6ede\u5728\u3059\u308b<\/td>=<\/td>\u914d\u5f53<\/td>–<\/td>\u5546<\/td>\u00d7<\/td>\u30c7\u30a3\u30d0\u30a4\u30c0\u30fc<\/a><\/span><\/td><\/tr>
5<\/td> =<\/td> 120<\/b><\/td> –<\/td> 5<\/td> \u00d7<\/td> 23<\/b><\/td><\/tr>
3<\/td> =<\/td> 23<\/b><\/td> –<\/td> 4<\/td> \u00d7<\/td> 5<\/td><\/tr>
2<\/td> =<\/td> 5<\/td> –<\/td> 1<\/td> \u00d7<\/td> 3<\/td><\/tr>
1<\/td> =<\/td> 3<\/td> –<\/td> 1<\/td> \u00d7<\/td> 2<\/td><\/tr>
0<\/td> =<\/td> 2<\/td> –<\/td> 2<\/td> \u00d7<\/td> 1<\/td><\/tr><\/table>

\u6700\u521d\u306e 2 \u884c\u306b 120 \u3068 23 \u304c\u8868\u793a\u3055\u308c\u3066\u3044\u308b\u3053\u3068\u3092\u78ba\u8a8d\u3057\u307e\u3059\u3002\u4e00\u65b9\u3001\u5404\u884c (\u8868\u306e2<\/sup>\u884c\u76ee\u304b\u3089) \u306e\u53f3\u7aef\u306e\u5024\u306f\u524d\u306e\u884c\u306e\u4f59\u308a\u3067\u3042\u308a\u3001\u88ab\u9664\u6570\u306f3<\/sup>\u884c\u76ee\u304b\u3089\u59cb\u307e\u308b\u5404\u540c\u70b9\u3067 2 \u884c\u4e0a\u306b\u5f97\u3089\u308c\u305f\u4f59\u308a\u306b\u306a\u308a\u307e\u3059\u3002\u3057\u305f\u304c\u3063\u3066\u30012 \u3064\u306e\u521d\u671f\u5024 120 \u3068 23 \u306e\u7dda\u5f62\u7d50\u5408<\/a><\/span>\u3068\u3057\u3066\u3001\u9023\u7d9a\u3059\u308b\u5404\u5270\u4f59\u3092\u6bb5\u968e\u7684\u306b\u8a08\u7b97\u3067\u304d\u307e\u3059\u3002<\/p>

\u305f\u3060\u3057\u3001\u3053\u306e\u65b9\u6cd5\u306f\u6700\u3082\u52b9\u679c\u7684\u3067\u306f\u3042\u308a\u307e\u305b\u3093\u3002\u3088\u308a\u76f4\u63a5\u7684\u306a\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u660e\u3089\u304b\u306b\u3059\u308b\u305f\u3081\u306b\u3001\u6700\u521d\u306b\u3053\u308c\u3089\u306e\u8a08\u7b97\u3092\u4f5c\u6210\u3057\u307e\u3059\u3002<\/p>
r<\/th><\/th> =<\/th>\u3042\u306a\u305f<\/th>\u00d7<\/th>\u3082\u3063\u3066\u3044\u308b<\/th>+<\/th> v<\/th> \u00d7<\/th> b<\/th><\/tr>
120 <\/td> =<\/td> 1<\/td> \u00d7<\/td> 120<\/td> –<\/td> 0<\/td> \u00d7<\/td> 23<\/td><\/tr>
23 <\/td> =<\/td> 0<\/td> \u00d7<\/td> 120<\/td> +<\/td> 1<\/td> \u00d7<\/td> 23<\/td><\/tr>
5<\/td> =<\/td> 120<\/td> –<\/td> 5<\/td> \u00d7<\/td> 23<\/td> =<\/td> 1<\/td> \u00d7<\/td> 120<\/td> –<\/td> 5<\/td> \u00d7<\/td> 23<\/td><\/tr>
3<\/td> =<\/td> 23<\/td> –<\/td> 4<\/td> \u00d7<\/td> 5<\/td> =<\/td> 1\u00d723<\/td> –<\/td> 4<\/td> \u00d7<\/td> (1\u00d7120\uff5e5\u00d723)<\/td> =<\/td> -4<\/td> \u00d7<\/td> 120<\/td> +<\/td> 21<\/td> \u00d7<\/td> 23<\/td><\/tr>
2<\/td> =<\/td> 5<\/td> –<\/td> 1<\/td> \u00d7<\/td> 3<\/td> =<\/td> (1\u00d7120\uff5e5\u00d723)<\/td> –<\/td> 1<\/td> \u00d7<\/td> (-4\u00d7120 + 21\u00d723)<\/td> =<\/td> 5<\/td> \u00d7<\/td> 120<\/td> –<\/td> 26<\/td> \u00d7<\/td> 23<\/td><\/tr>
1<\/td> =<\/td> 3<\/td> –<\/td> 1<\/td> \u00d7<\/td> 2<\/td> =<\/td> (-4\u00d7120 + 21\u00d723)<\/td> –<\/td> 1<\/td> \u00d7<\/td> (5\u00d7120\uff5e26\u00d723)<\/td> =<\/td> -9<\/td> \u00d7<\/td> 120<\/td> +<\/td> 47<\/td> \u00d7<\/td> 23<\/td><\/tr><\/table>

\u6700\u5f8c\u306e\u884c\u3067\u306f 1 = -9\u00d7120 + 47\u00d723 \u304c\u5f97\u3089\u308c\u3001\u307e\u3055\u306b\u5fc5\u8981\u306a\u3082\u306e\u3001 u<\/i> = -9 \u304a\u3088\u3073v<\/i> = 47 \u304c\u5f97\u3089\u308c\u308b\u3053\u3068\u306b\u6ce8\u610f\u3057\u3066\u304f\u3060\u3055\u3044\u3002\u3053\u308c\u306f\u30011 \u304c 1 \u3067\u3042\u308b\u305f\u3081\u3001-9 \u306f 120 \u3092 23 \u3067\u6cd5\u5b9a\u3057\u3066\u4e57\u7b97\u3059\u308b\u9006\u6570\u3067\u3042\u308b\u3053\u3068\u3092\u610f\u5473\u3057\u307e\u3059\u3002 = -9 \u00d7 120 (mod 23)\u3002\u540c\u69d8\u306b\u300147 \u306f 120 \u3092\u6cd5\u3068\u3059\u308b\u4e57\u7b97\u306e\u200b\u200b 23 \u306e\u9006\u6570\u3067\u3059\u3002<\/p>

\u9752\u8272\u3067\u793a\u3055\u308c\u3066\u3044\u308b\u306e\u306f\u3001\u524d\u306e 2 \u3064\u306e\u6570\u5024\u3092\u9664\u7b97\u3057\u305f\u4f59\u308a\u304b\u3089 gcd \u3092\u6c42\u3081\u308b\u9023\u7d9a\u8a08\u7b97\u3067\u3059 (\u901a\u5e38\u306e Euclid \u30a2\u30eb\u30b4\u30ea\u30ba\u30e0)\u3002\u5bfe\u5fdc\u3059\u308b\u5546\u306f\u9ec4\u8272<\/a><\/span>\u3067\u793a\u3055\u308c\u3066\u3044\u307e\u3059\u3002 2 \u3064\u306e\u7dd1\u8272\u306e\u5217\u306f\u3001Bezout \u4fc2\u6570 ( u<\/i>\u304a\u3088\u3073v<\/i> ) \u3092\u3082\u305f\u3089\u3059\u9023\u7d9a\u8a08\u7b97\u3092\u793a\u3057\u307e\u3059\u3002\u3053\u308c\u3089\u306e\u4fc2\u6570\u306f\u3001\u9ec4\u8272\u306e\u5217\u306e\u5546\u3092\u4f7f\u7528\u3057\u3066\u3001\u540c\u3058\u5217\u306e\u524d\u306b\u3042\u308b 2 \u3064\u306e\u4fc2\u6570\u304b\u3089\u8a08\u7b97\u3055\u308c\u3066\u3044\u308b\u3053\u3068\u3092\u78ba\u8a8d\u3067\u304d\u307e\u3059\u3002\u5f0f\u306f\u6b21\u306e\u6bb5\u843d\u306e\u8868<\/a><\/span>\u3067\u6307\u5b9a\u3055\u308c\u3066\u3044\u307e\u3059\u3002<\/p><\/div>

\n\"\u62e1\u5f35<\/figure>

\u53c2\u8003\u8cc7\u6599<\/h2>
  1. \u062e\u0648\u0627\u0631\u0632\u0645\u064a\u0629 \u0625\u0642\u0644\u064a\u062f\u0633 \u0627\u0644\u0645\u0645\u062f\u062f\u0629 \u2013 arabe<\/a><\/li>
  2. Algorisme d’Euclides ampliat \u2013 catalan<\/a><\/li>
  3. Roz\u0161\u00ed\u0159en\u00fd Eukleid\u016fv algoritmus \u2013 tch\u00e8que<\/a><\/li>
  4. Erweiterter euklidischer Algorithmus \u2013 allemand<\/a><\/li>
  5. Extended Euclidean algorithm \u2013 anglais<\/a><\/li>
  6. \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u062a\u0639\u0645\u06cc\u0645\u200c\u06cc\u0627\u0641\u062a\u0647 \u0627\u0642\u0644\u06cc\u062f\u0633 \u2013 persan<\/a><\/li><\/ol><\/div>\n
    \n

    \n \u62e1\u5f35 Euclid \u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306b\u3064\u3044\u3066\u8a73\u3057\u304f\u89e3\u8aac\u30fb\u95a2\u9023\u52d5\u753b\n <\/h2>\n
    \n \n
    \n
    \n