$x$, $y$, $p$ は自然数とする。$\frac{x}{p} = \frac{y}{p-1}$ が成り立つならば、この式の値は整数で、$x$, $y$ の最大公約数に一致することを示せ。

1. 問題の内容

$x$, $y$, $p$ は自然数とする。$\frac{x}{p} = \frac{y}{p-1}$ が成り立つならば、この式の値は整数で、$x$, $y$ の最大公約数に一致することを示せ。

2. 解き方の手順

まず、$\frac{x}{p} = \frac{y}{p-1} = k$ とおく。ここで、$k$ は定数である。すると、

$x = kp$

$y = k(p-1)$

と表せる。

$x$ と $y$ の最大公約数を $d$ とすると、$x = ad$ , $y = bd$ （$a$, $b$ は互いに素な自然数）と表せる。

よって、

$ad = kp$

$bd = k(p-1)$

$k = \frac{ad}{p} = \frac{bd}{p-1}$

$ad(p-1) = bdp$

$a(p-1) = bp$

$ap - a = bp$

$ap - bp = a$

$p(a-b) = a$

ここで、$a-b$ は整数なので、$p$ は $a$ の約数となる。

$a$は$p$の倍数である。$a=mp$とおくと($m$は自然数)、

$mp-a=bp$

$-a=bp-mp$

$-mp=bp-mp$

$0=bp$

これは矛盾する。

$x=kp$ と $y=k(p-1)$ より、$x-y = kp - k(p-1) = kp - kp + k = k$

$x = y + k$

$x, y$ の最大公約数を $d$ とおくと、$x = ad$, $y = bd$ （$a, b$ は互いに素な自然数）とおける。

$ad = bd + k$

$k = ad - bd = (a-b)d$

つまり、$k$ は $d$ の倍数である。$k=nd$とおける（$n$は自然数）

$x=kp$と$y=k(p-1)$に代入する。

$ad = ndp$

$bd = nd(p-1)$

$a=np$

$b=n(p-1)$

$x$と$y$の最大公約数$d$は、$x=ad=npd$と$y=bd=n(p-1)d$の公約数である。

ここで、$n$ は $a$ と $b$ の公約数ではないので、$n$ は $x$ と $y$ の最大公約数 $d$ の約数である。$a=np$と$b=n(p-1)$より、$gcd(a,b)=1$であるから、$gcd(p,p-1)=1$が成り立つ。

したがって、$k$ は $x$ と $y$ の最大公約数 $d$ に等しい。

$k = \frac{x}{p}$ より、$x = kp$ なので、$k$ が整数ならば $x$ は整数。

$k = \frac{y}{p-1}$ より、$y = k(p-1)$ なので、$k$ が整数ならば $y$ は整数。

したがって、$\frac{x}{p} = \frac{y}{p-1}$ の値は整数で、$x$ と $y$ の最大公約数に一致する。

3. 最終的な答え

$\frac{x}{p} = \frac{y}{p-1}$ の値は整数で、$x$ と $y$ の最大公約数に一致する。