互いに素な自然数x,yに対して、xz/yの小数部分を最小にする 自然数zを求めよ。ただし、0<z<yとする。

質問

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

回答No.4

reiman · ベストアンサー

ｙ＝１のときにはｚは存在しないので１＜ｚとする。
ｘ，ｙは互いに素なので整数ａ，ｂが存在して
ａｘ＋ｂｙ＝１・・・（１）
もし整数Ａ，Ｂについて
Ａｘ＋Ｂｙ＝１・・・（２）
ならば（１）－（２）より
（ａ－Ａ）ｘ＋（ｂ－Ｂ）ｙ＝０
よってａ－Ａはｙで割りきれるからｎを整数として
ａ－Ａ＝ｎｙ
とかける。ｎを任意に選んでも
Ｂ＝ｎｘ＋ｂ
とすれば（２）を満たす。
Ａ＝ａ－ｎｙ
であるから０≦Ａ＜ｙで有るようにｎを適当に選びＡを一意に決定できる。
ただしＡ＝０とするとＢｙ＝１となり矛盾するので
０＜Ａ＜ｙで有るようにｎを適当に選びＡを一意に決定できる。
そのときのＡをｚとおく。
すると
ｚｘ＋Ｂｙ＝１
であるから
ｘｚ／ｙ＝１／ｙ－Ｂ
であり、よって
ｘｚ／ｙの小数は１／ｙである。
ｚｘ＋Ｂｙ＝１かつ０＜ｚ＜ｙ
を満たすｚは一意だからｚを上記以外に決定したときはＢを適当に選び
ｋ＝ｚｘ＋Ｂｙかつ１＜ｋ＜ｙとなる。
このとき
ｘｚ／ｙ＝ｋ／ｙ－Ｂ
となり
ｘｚ／ｙの小数はｋ／ｙとなりいずれも１／ｙより大きい。

お礼

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

回答No.5

reiman

Ｎｏ．４の１行目は次の間違い。
ｙ＝１のときにはｚは存在しないので１＜yとする。

回答No.3

reiman

起きたばかりで回答したので寝ぼけていたみたい。
Ｎｏ２は大間違い。
ｘ，ｙは互いに素なので整数ａ，ｂが存在して
ａｘ＋ｂｙ＝１・・・（１）
もし整数Ａ，Ｂについて
Ａｘ＋Ｂｙ＝１・・・（２）
ならば（１）－（２）より
（ａ－Ａ）ｘ＋（ｂ－Ｂ）ｙ＝０
よってａ－Ａはｙで割りきれるからｎを整数として
ａ－Ａ＝ｎｙ
とかける。ｎを任意に選んでも
Ｂ＝ｎｘ＋ｂ
とすれば（２）を満たす。
Ａ＝ａ－ｎｙ
であるから０＜Ａ＜ｙで有るようにｎを適当に選びＡを決定できる。
このときのＡをｚとすればよい。
ａ，ｂはユークリッドの互除法で求まるからそれを元にＡすなわちｚは求まる。
なお最小の少数は当然１／ｙである。

回答No.2

reiman

［］をガウスの揮毫としxをyで割った余りをx％yと書くと
x％y＝１のときz＝１
x％y≠１のときz＝［y／（x％y）］＋１

回答No.1

rnakamra

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

そのようなzを探す場合、オイラーの定理が使えます。
http://ja.wikipedia.org/wiki/%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E3%81%AE%E5%AE%9A%E7%90%86_(%E6%95%B0%E8%AB%96)
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%E3%83%A9%E3%83%BC%E3%81%AE%E5%AE%9A%E7%90%86_(%E6%95%B0%E8%AB%96)

お礼

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