積で割った余りを合同式で求める。

　高校時代は合同式と相加平均・相乗平均の大小関係が大好きでした。
　それで、高校で普通合同式を使わずに解く問題も合同式を解きたいと思いました。そのために、一般的でない合同式の公式を証明します。

　まずは合同式の定義と一般的な公式の証明をします。

f:id:Natsu1014_brog:20210404121850p:plain

　ここからは $(3),(4)$ の別バージョンとして $(6),(7)$ を証明します。

f:id:Natsu1014_brog:20210404121955p:plain

　さて、今回使うのは $(7)$ だけを使います。

　解きたい問題は「 $p,q$ を互いに素な自然数としたとき, $p$ で割ると $r$ 余り, $q$ で割ると $s$ 余るとき, $n$ を $pq$ で割った余りを求めよ.]という問題です。
　まず一般的な方法で解きます。

$n$ はある整数 $k,l$ が存在して
　 $n=pk+r, \, n=ql+s$

と表される.
このとき $pk+r=ql+s$ であるから $pk-ql=s-r$ .
$p$ と $q$ は互いに素であるから, ユークリッド互除法により
　 $pk' -ql' =1$
を満たす組 $(k' ,l' )=(k_0,l_0)$ が求まる.
したがって $p(s-r)k_0-q(s-r)l_0=s-r$ であるから
　 $p [ k-(s-r)k_0 ]=q [ l-(s-r)l_0 ]$ .
$p$ と $q$ は互いに素, $k-(s-r)k_0,l-(s-r)l_0$ は整数より, $k-(s-r)k_0$ は $q$ の倍数である.
よって, ある整数 $m$ が存在して $k-(s-r)k_0=qm \, \therefore k=qm+(s-r)k_0$ .
このとき, $l=pm+(s-r)l_0$ .
したがって, $n_0=p(s-r)k_0+r=q(s-r)l_0+s$ とおくと $n=pqm+n_0$ ( $m$ は整数) より $n$ を $pq$ で割った余りは $n_0$ を $pq$ で割った余りに等しい.

　次に合同式を使った場合です。

$n ≡ r \, ({\rm mod}p)$ より $qn ≡ qr \, ({\rm mod}pq)$ .
$n ≡ s \, ({\rm mod}q)$ より $pn ≡ ps \, ({\rm mod}pq)$ .
$p$ と $q$ は互いに素であるから, ユークリッド互除法により
　 $pk' -ql' =1$
を満たす組 $(k' ,l' )=(k_0,l_0)$ が求まる.
したがって $n ≡ (pk_0-pl_0)n ≡ psk_0-qrl_0 \, ({\rm mod}pq)$ .
すなわち $n$ を $pq$ で割った余りは $psk_0-qrl_0$ を $pq$ で割った余りに等しい.

　 $n_0=psk_0-qrl_0$ となることは簡単に分かります。また、合同式を使った解法だと、本質的には同じですがユークリッド互除法を使わずにゴリ押せます。例題を解いてみましょう。

[問] $19,11$ で割るとそれぞれ $7,5$ 余る自然数を $209$ で割った余りを求めよ.
[答]
$n$ を $19,11$ で割るとそれぞれ $7,5$ 余る自然数とすると,
　 $n ≡ 7 \, ({\rm mod}19) \, \therefore 11n ≡ 77 \, ({\rm mod}209) \cdots$ ①
　 $n ≡ 5 \, ({\rm mod}11) \, \therefore 19n ≡ 95 \, ({\rm mod}209) \cdots$ ②
② $-$ ① より

　 $8n ≡ 19n-11n ≡ 95-77 ≡ 18 \, ({\rm mod}209) \, \therefore 8n ≡18 \, ({\rm mod}209) \cdots$ ③
① $-$ ③ より

　 $3n ≡ 11n-8n ≡77-18≡59 \, ({\rm mod}209) \, \therefore 3n ≡ 59 \, ({\rm mod}209) \cdots$ ④

④ $×3-$ ③ より
　 $n ≡ 3n \times 3 -8n ≡ 59 \times 3 - 18 ≡ 159 \, ({\rm mod}209)$
したがって, $n$ を $209$ で割った余りは $159$ である.

　 $2$ つの合同式から $n ≡ \cdots$ の式を求めるまでは多少面倒ですが、ユークリッド互除法から式変形するよりはずっと楽ですし、うまくやれば短くできそうです。もしかしたら選んだ整数によっては面倒になるかもしれませんが、そのときは別の方法で。少なくとも以前求めた行列を使った方法をやれば、簡単に求まるはずです。

NTMRの数学メモ

数学について調べたことを書きます。高校数学に毛が生えた内容。

積で割った余りを合同式で求める。