ユークリッドの互除法

ユークリッドの互除法を用いて、$2$ つの整数 $437$ と $323$ の最大公約数を求めよ。

ユークリッドの互除法を用いて、$667$ と $437$ の最大公約数を求めよ。

ユークリッドの互除法を用いて、$437$ と $323$ の最大公約数を求めよ。

$n$ は $1\leqq n\leqq 100$ を満たす整数とする。$3n+4$ と $5n+1$ の最大公約数が $1$ より大きくなるような $n$ の個数を求めよ。

正の整数 $n$ に対して、$5n+3$ と $3n+1$ の最大公約数を $d_n$ とする。$n=1,2,3,\dots ,100$ のときの $d_n$ の和
$$d_1+d_2+d_3+\cdots +d_{100}$$
を求めよ。

正の整数 $n$ に対して、$3n+7$ と $5n+2$ の最小公倍数を $L$ とする。$n\leqq 200$ を満たす正の整数 $n$ のうち、
$$L=\frac{(3n+7)(5n+2)}{29}$$
が成り立つものすべての和を求めよ。

$n$ は $1\leqq n\leqq 200$ を満たす整数とする。2 つの整数 $n^2+2$ と $n+4$ の最大公約数が $6$ となるような $n$ の個数を求めよ。

$p,q$ を相異なる奇素数とし、$n=pq$、$\phi =(p-1)(q-1)$ とおく。正の整数 $e,d$ は $ed\equiv 1(\mathrm{mod}\phi )$ をみたすとする（RSA 暗号の公開鍵 $(n,e)$ と秘密鍵 $d$）。中国剰余定理を使った高速な復号（CRT-RSA）のために、次を定める。
- $d_p$ を $d$ を $p-1$ で割った余り、$d_q$ を $d$ を $q-1$ で割った余りとする（$0\le d_p\le p-2$、$0\le d_q\le q-2$）。
- 整数 $u$ を、$qu\equiv 1(\mathrm{mod}p)$ をみたす整数のうちの 1 つとする（$p,q$ は相異なる素数なので、このような $u$ は存在する）。

$0\le c<n$ をみたす整数 $c$（暗号文）に対して、
- $m_p$ を $c^{d_p}$ を $p$ で割った余り、$m_q$ を $c^{d_q}$ を $q$ で割った余り（$0\le m_p\le p-1$、$0\le m_q\le q-1$）、
- $h$ を $u(m_p-m_q)$ を $p$ で割った余り（$0\le h\le p-1$）、
- $m=m_q+qh$

とおく。ここで $c$ は $n$ と互いに素であるとは限らない（$c=0$ や、$c$ が $p$ または $q$ の倍数である場合も含む）。また、整数 $a$ に対して $a^0=1$ と定める（$a=0$ のときも含む）。このとき、$0\le m<n$ かつ $m\equiv c^d(\mathrm{mod}n)$ であることを証明せよ。

ただし、フェルマーの小定理と、「整数 $x$ が相異なる素数 $p,q$ のそれぞれで割り切れるならば $pq$ で割り切れる」ことは用いてよい。

互いに素な正の整数の組 $(a,b)$ から始めて、次の操作をくり返す。

「2 つの数が異なるとき、大きい方の数を、大きい方から小さい方を引いた数に置き換える。」

2 つの数が等しくなったら操作を終える。このとき 2 つの数はともに $1$ になっている。終えるまでに行った操作の回数を $T(a,b)$ とする。たとえば $(3,5)\to (3,2)\to (1,2)\to (1,1)$ より $T(3,5)=3$ である。

$a+b=100$ を満たす互いに素な正の整数の組 $(a,b)$ 全体を考えるとき、$T(a,b)$ の最小値を求めよ。

$m,n$ は $1\leqq m<n\leqq 60$ を満たす整数とする。$2$ つの整数 $2^m-1$ と $2^n-1$ の最大公約数が $15$ となるような組 $(m,n)$ の個数を求めよ。

$m,n$ は $1\leqq m\leqq 20$, $1\leqq n\leqq 20$ を満たす整数とする。2 つの整数 $4^m-1$ と $8^n-1$ の最大公約数が $63$ となるような整数の組 $(m,n)$ の個数を求めよ。