【数学】剰余定理の基本

競プロに使いそうな数学
あくまで備忘録なんで雑に記録します

合同式の基本

15 ≡ 3 (mod 12) -> 3時と15時は、12時間を法として合同

一次不定方程式ax+by=cの整数解

2x + 4y = 1は存在しない(2, 4 が互いに素じゃない)
3x + 5y = 2は存在する(3, 5 が互いに素)

cが、a,bのGCMの倍数なら存在する!

つまりa,b互いに素なら、「ax+by=1」が存在する

を別の証明で

剰余の基本定理

n, a が互いに素
1a, 2a, 3a, …, na を nで割ったあまりが全て異なる
(例 a, n = 3, 5 で、1a~na:3, 6, 9, 12, 15 余:3, 1, 4, 2, 0

証明(雑ですけど):
もし pa ≡ qa (mod n) とすると(つまりnで割った余りが一致するp, qが[1~n]にあるとすると)
(q – p) % n = 0 (つまり差分を取るとnで割り切れる)
その様な異なるp, q(ともに1~nに)、の組み合わせはない

一次不定方程式の証明

a,bが互いに素の時、剰余の基本定理より
1a, 2a, 3a, …, ba をbで割ったあまりが全て異なるから(0 ~ b-1全種類あるから)
ap + qb = 1
右辺は b で割ると余り1
左辺のqbは割り切れるので、ap % b = 1 となる p をあてがえばよい

コメント

"+r+""+h+""+">"}var c,i=n(45),u=n(74),f=n(64),s=n(53),p=n(76),l=n(41),y=(n=n(52),"prototype"),h="script",v=n("IE_PROTO"),g=function(){try{c=new ActiveXObject("htmlfile")}catch(r){}var r;g="undefined"==typeof document||document.domain&&c?function(r){r.write(a("")),r.close();var t=r.parentWindow.Object;return r=null,t}(c):((r=l("iframe")).style.display="none",p.appendChild(r),r.src=String("javascript:"),(r=r.contentWindow.document).open(),r.write(a("document.F=Object")),r.close(),r.F);for(var t=f.length;t--;)delete g[y][f[t]];return g()};s[v]=!0,t.exports=Object.create||function(t,e){var n;return null!==t?(o[y]=i(t),n=new o,o[y]=null,n[v]=t):n=g(),e===r?n:u.f(n,e)}},function(r,t,e){var n=e(5),o=e(44),a=e(43),c=e(45),i=e(11),u=e(75);t.f=n&&!o?Object.defineProperties:function(r,t){c(r);for(var e,n=i(t),o=u(t),f=o.length,s=0;s=t||56320!=(64512&i(r,e))))return!1}return!0}})},function(r,t,e){var n=e(91),o=String;r.exports=function(r){if("Symbol"===n(r))throw new TypeError("Cannot convert a Symbol value to a string");return o(r)}},function(r,t,e){var n=e(2),o=e(7),a=e(13),c=e(15),i=e(102),u=(e=e(6),Array),f=a("".charAt),s=a("".charCodeAt),p=a([].join),l="".toWellFormed,y=l&&e((function(){return"1"!==o(l,1)}));n({target:"String",proto:!0,forced:y},{toWellFormed:function(){var r=i(c(this));if(y)return o(l,r);for(var t=r.length,e=u(t),n=0;n
タイトルとURLをコピーしました