114514^810-1は3で何回割れる??

テーマ:
  ある整数nを素数pで割り切れる最大の回数(オーダー)をord_p(n)と表します。つまり、ord_p(n)=kとすると、nはp^kで割り切れるが、p^(k+1)では割り切れないことを意味します。言い換えれば、nを素因数分解した時のpの右肩につく指数がkとなります。







この時、ordの性質として、
pを素数、x,yを整数とすると、
ord_p(x±y)≧min(ord_p(x), ord_p(y))
ord_p(xy)=ord_p(x)+ord_p(y)
さらに、xはyの倍数とすると
ord_p(x/y)=ord_p(x)-ord_p(y)
です。




オーダーの面白い定理として、LTEの補題があります。



今回は証明をおいといて、実際にコレを使ってみましょう!


(114514^810)-1を3で割った余りは??

求める値はord_3(114514^810-1)です。
1=1^810であるから
ord_3(114514^810-1)=ord_3(114514^810-1^810)
です。
これに加えて、3が奇素数、114514も1も3で割ると1余るから、LTEの補題が使えます。

LTEの補題を使ってみると、求める値はord_3(114514-1)+ord_3(810)です。

114514-1=114513ですので、これの3で割り切れる回数を考えましょう。
114513=3×38171で、38171は3で割り切れないので、ord_3(114513)=1です。

また810=3^4×10なので、ord_3(810)=4です。

よって、求める値は、1+4=5となります。

LTEの補題の利点は、足し算の中に掛け算の要素を見出すことが出来る点ですね!


↓twitterやってます。