プロが教える店舗&オフィスのセキュリティ対策術

という問題があるのですが、解答の方針を教えていただけないでしょうか?
xz/y-[xz/y] がxz/yの小数部分を表すというのは調べてわかったのですが、
そこからどうやって値を絞り込むかが皆目見当がつきません。

A 回答 (5件)

y=1のときにはzは存在しないので1<zとする。


x,yは互いに素なので整数a,bが存在して
ax+by=1・・・(1)
もし整数A,Bについて
Ax+By=1・・・(2)
ならば(1)-(2)より
(a-A)x+(b-B)y=0
よってa-Aはyで割りきれるからnを整数として
a-A=ny
とかける。nを任意に選んでも
B=nx+b
とすれば(2)を満たす。
A=a-ny
であるから0≦A<yで有るようにnを適当に選びAを一意に決定できる。
ただしA=0とするとBy=1となり矛盾するので
0<A<yで有るようにnを適当に選びAを一意に決定できる。
そのときのAをzとおく。
すると
zx+By=1
であるから
xz/y=1/y-B
であり、よって
xz/yの小数は1/yである。
zx+By=1かつ0<z<y
を満たすzは一意だからzを上記以外に決定したときはBを適当に選び
k=zx+Byかつ1<k<yとなる。
このとき
xz/y=k/y-B
となり
xz/yの小数はk/yとなりいずれも1/yより大きい。
    • good
    • 0
この回答へのお礼

理解できました。ありがとうございます!

お礼日時:2009/07/03 10:48

No.4の1行目は次の間違い。


y=1のときにはzは存在しないので1<yとする。
    • good
    • 0

起きたばかりで回答したので寝ぼけていたみたい。


No2は大間違い。
x,yは互いに素なので整数a,bが存在して
ax+by=1・・・(1)
もし整数A,Bについて
Ax+By=1・・・(2)
ならば(1)-(2)より
(a-A)x+(b-B)y=0
よってa-Aはyで割りきれるからnを整数として
a-A=ny
とかける。nを任意に選んでも
B=nx+b
とすれば(2)を満たす。
A=a-ny
であるから0<A<yで有るようにnを適当に選びAを決定できる。
このときのAをzとすればよい。
a,bはユークリッドの互除法で求まるからそれを元にAすなわちzは求まる。
なお最小の少数は当然1/yである。
    • good
    • 0

[]をガウスの揮毫としxをyで割った余りをx%yと書くと


x%y=1のときz=1
x%y≠1のときz=[y/(x%y)]+1
    • good
    • 0

xz/yが整数となることはありえません。

xzをyで割ったあまりの最小値は1以上となりますが多分1になると考えられます。

そのようなzを探す場合、オイラーの定理が使えます。
http://ja.wikipedia.org/wiki/%E3%82%AA%E3%82%A4% …
yよりも小さくyと互いに素な自然数の個数をφ(y)としますと、
x^φ(y)≡1(mod y)
となります。
z'=x^{φ(y)-1}としますとxz'≡1(mod y)となります。
ということは、zはz'をyで割ったあまりとすると
xz≡1(mod y)
となり、このときxz/yの小数部分は1/yで最小となります。

参考URL:http://ja.wikipedia.org/wiki/%E3%82%AA%E3%82%A4% …
    • good
    • 0
この回答へのお礼

簡潔ですね。ありがとうございます!

お礼日時:2009/07/03 10:47

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!