前、バシェの定理を証明しました。
ax + by = 1が整数解を持つ ⇔ (ａ，ｂ)＝1
というものでした。
(ａ，ｍ)＝1であるとしましょう。バシェの定理によればこのとき
ａａ’＋ｍｙ＝1となるａ’、ｙが存在します（文字は全て整数）。これは
ａａ’≡1（mod m）ということです。これをすぐ使います。
ａｘ≡ａｃ（mod m）……★（ただし（ａ，ｍ）＝1）のとき、両辺をａで割りたくなりますよね。でも合同式なので、普通の等式並みに式変形できる保証はまだありません。しかし上で示した事実を使えます。（ａ，ｍ）＝1なのでａａ’≡1となるａ’があります。このａ’を★の両辺にかけてａａ’ｘ≡ａａ’ｃ。ここでａａ’を1で置き換えてｘ≡ｃ。これでａで割れました。
①2ｘ≡1（mod 3）
両辺を2倍して4ｘ≡2
よってｘ≡2（mod 3）。
ｘ＝3ｋ＋2（ｋは整数）
②4ｘ≡ｘ＋29（mod 7）
3ｘ≡29≡1
両辺を5倍して15ｘ≡5
よってｘ≡5（mod 7）。
（ｘ＝7ｋ＋5（ｋは整数））
あるいは、3ｘ≡1の両辺に14を加えて
3ｘ≡15（mod 7）
最初に示した事実を用いて、
（3，17）＝1から両辺を3で割れて、
ｘ≡5（mod 7）を得ます。
①は2ｘ＋3ｙ＝1の整数解を求めていることですし、②は3ｘ＋7ｙ＝29を解くのと同じことです。
以上、証明や問題は何度も紹介している『親切な代数学演習―整数・群・環・体』（加藤明史2002現代数学社）を参考にしています。整数から始まり、群、環、体、線形代数からガロア理論まで、必要なことが全部書いてあります。何回読んでも勉強になります。
ぼくは暗号の理論にも興味があって何度か勉強を始めようとしたことがあるんですが、整数論は現代の暗号理論の基本です。もちろん合同式などもガンガン出てきます。がんばってみます。
