 | 2015/01/12(Mon) 13:52:38 編集(投稿者)
「AD-BC≡1(mod N)」というキーワードで検索すれば同じ質問に回答も付いていますよ。
引用すると、
<質問>
合同式についてです。Nを自然数とします。
ad-bc ≡ 1 (mod N)なる整数a,b,c,dが与えられたとします。
すると、ある整数s,tが存在して、c+sNとd+tNが互いに素になります。(←証明は省略します)
c' = c+sN, d' = d+tNと置きます。
ここからが質問です。
x(c')-y(d') = 1であって、かつx = a (mod N), y = b (mod N)となる
整数x, yが存在するらしいのですが、どうやって証明すれば良いのでしょうか？
c'とd'が互いに素なのでx(d')-y(c') = 1なるx, yは取れますがその先がわかりません。
<回答>
a(d')-b(c') ≡ ad-bc ≡ 1 (mod N) なので、a(d')-b(c') = 1+Nuとおける
c'とd'が互いに素なので、z(d')-w(c') = -uとなるz, wがとれる
このとき、x=a+Nz, y=b+Nwとおけば、条件をみたす
いかがでしょうか？
・・・となっています。
ここで「(←証明は省略します)」の部分すら私には証明できず、
気になって私がこの部分を質問してみたら、以下の回答をもらいました。
<私の質問>
整数とは有理数の整数を表すものとします。
a, bを互いに素な整数とします。
任意の0でない整数nに対して、ある整数x, yが存在してn = xa+ybと表せます。
このとき、x, yが互いに素となるように選ぶことは可能でしょうか?
(a, b) = 1ならば、ある整数u, vが存在して1 = ua+vbと表せるので、
n = (nu)a+(nv)b = xa+ybとなることからx = nu, y = nvとは取れますが、
n > 1或いはn < -1ならnuとnvは互いに素ではありません。
<頂いた回答>
可能だと思います。
仰るとおり 1 = ua + vb を満たす整数u, vが存在します。
x = nu + b
y = nv - a
とおけば、 n = xa + yb はすぐ確認できます。
またvx - uy = 1
の成立もすぐ確認できるので、xとyは互いに素です。
ちなみにnに対する「0でない」という条件は全く不要だと思います。
・・・ということです。
なので、これらを組み合わせればスレ主さんの疑問も氷解することでしょう!
|