s/t mod N - Isa@Diary

${ \displaystyle s,t,N \in Z\space\space s,t,N \gt 0, t | s }$
のときに
${ \displaystyle \frac{s}{t} \bmod N = \frac{s \bmod tN}{t} }$
がすぐ理解できなかったのでメモ。

手順

ある $k(\space\space k\in Z, k \geq 0)$ を使って
${ \displaystyle \frac{s}{t} = kN + (\frac{s}{t} \bmod N) }$
と書ける。これを変形して
${\displaystyle \Leftrightarrow s = tkN + t(\frac{s}{t} \bmod N)\\ \Leftrightarrow s \bmod tN = (tkN \bmod tN + (t(\frac{s}{t} \bmod N)) \bmod tN) \bmod tN \\ }$
ここで明らかに $tkN \bmod tN = 0$ で、また $(t(\frac{s}{t} \bmod N)) \bmod tN$ は
${ \displaystyle \frac{s}{t} \bmod N \lt N \\ \Leftrightarrow t(\frac{s}{t} \bmod N) \lt tN \\ \Rightarrow (t(\frac{s}{t} \bmod N)) \bmod tN = t(\frac{s}{t} \bmod N) }$

よって
${ \displaystyle s \bmod tN = t(\frac{s}{t} \bmod N)\\ \Leftrightarrow \frac{s}{t} \bmod N = \frac{s \bmod tN}{t} }$