1
解説高校数学
最大公約数表の作り方（四則演算無し）
57
1
$$\newcommand{beginend}[2]{\begin{#1}#2\end{#1}}
\newcommand{C}[0]{\mathbb{C}}
\newcommand{clone}[2]{\beginend{matrix}{\uparrow{#2}\ \\ {\color{blue}{#1}}\rightarrow}}
\newcommand{hygeo}[6]{ {}_{#2}{#1}_{#3}\left[\begin{matrix}{#4}\\ {#5}\end{matrix}\ ;{#6}\right]}
\newcommand{kfrac}[0]{\mathop{\large\rm{K}}}
\newcommand{lr}[3]{\left#1{#2}\right#3}
\newcommand{N}[0]{\mathbb{N}}
\newcommand{overupallow}[1]{\matrix{\uparrow\\ {#1}}}
\newcommand{overupandrightarrow}[1]{\matrix{\uparrow\hspace{13pt}\\ {\color{blue}{#1}}\rightarrow}}
\newcommand{Q}[0]{\mathbb{Q}}
\newcommand{R}[0]{\mathbb{R}}
\newcommand{slfrac}[2]{\cancel{\tiny\beginend{matrix}{\large{#1}\hspace{8pt}\\ \large\hspace{9pt}{#2}}}}
\newcommand{stirling}[3]{\left[ \begin{matrix}{#1} \\ {#2}\end{matrix} {#3}\right]}
\newcommand{Stirling}[3]{\left\{ \begin{matrix}{#1} \\ {#2}\end{matrix} {#3}\right\}}
\newcommand{Z}[0]{\mathbb{Z}}
$$
定理
$m,n\ge1$の最大公約数を$\gcd(m,n)$と表します。
このとき、$\gcd(m,n)$は次の漸化式で計算することができます。
$\beginend{cases}{
\gcd(m,m) &= m \\
\gcd(m,n) &= \gcd(n,m) = \gcd(m-n,n) &(m>n)
}$
2行目は次の様にできます。
$\gcd(m,n) = \gcd(|m-n|,\min(m,n)) \quad(m\ne n)$
2行目
$g \coloneqq \gcd(m,n)$
$ga \coloneqq m, gb \coloneqq n$
$a,b$は互いに素。
$\Longrightarrow a-b,b$は互いに素。
$\gcd(m-n,n) = \gcd(g(a-b),gb) = g\gcd(a-b,b) = g$
プログラム上で最大公約数の表が必要な場合、
ユークリッドの互除法で一つずつ求めるよりも
この漸化式を使った方が効率的です。
手順
1. 対角線上に自然数を並べる。（1行目）
| $\color{gray}8$ | $\color{red}8$ | |||||||
| $\color{gray}7$ | $\color{red}7$ | |||||||
| $\color{gray}6$ | $\color{red}6$ | |||||||
| $\color{gray}5$ | $\color{red}5$ | |||||||
| $\color{gray}4$ | $\color{red}4$ | |||||||
| $\color{gray}3$ | $\color{red}3$ | |||||||
| $\color{gray}2$ | $\color{red}2$ | |||||||
| $\color{gray}1$ | $\color{red}1$ | |||||||
| $\slfrac nm$ | $\color{gray}1$ | $\color{gray}2$ | $\color{gray}3$ | $\color{gray}4$ | $\color{gray}5$ | $\color{gray}6$ | $\color{gray}7$ | $\color{gray}8$ |
2. 転写する。（2行目）
| $\color{gray}4$ | $4$ | |||
| $\color{gray}3$ | $3$ | |||
| $\color{gray}2$ | $\color{red}1$ | $2$ | ||
| $\color{gray}1$ | $\clone1\quad$ | $\color{red}1$ | ||
| $\slfrac nm$ | $\color{gray}1$ | $\color{gray}2$ | $\color{gray}3$ | $\color{gray}4$ |
| $\color{gray}4$ | $4$ | |||
| $\color{gray}3$ | $\color{red}1$ | $\color{red}1$ | $3$ | |
| $\color{gray}2$ | $\clone1\quad$ | $\clone\quad2$ | $\color{red}1$ | |
| $\color{gray}1$ | $1$ | $\clone1\quad$ | $\color{red}1$ | |
| $\slfrac nm$ | $\color{gray}1$ | $\color{gray}2$ | $\color{gray}3$ | $\color{gray}4$ |
| $\color{gray}4$ | $\color{red}1$ | $\color{red}2$ | $\color{red}1$ | $4$ |
| $\color{gray}3$ | $\clone1\quad$ | $\clone\quad1$ | $\clone\quad3$ | $\color{red}1$ |
| $\color{gray}2$ | $1$ | $\clone2\quad$ | $\clone\quad1$ | $\color{red}2$ |
| $\color{gray}1$ | $1$ | $1$ | $\clone1\quad$ | $\color{red}1$ |
| $\slfrac nm$ | $\color{gray}1$ | $\color{gray}2$ | $\color{gray}3$ | $\color{gray}4$ |
3. 完成。
| $\color{gray}8$ | $1$ | $2$ | $1$ | $4$ | $1$ | $4$ | $1$ | $8$ |
| $\color{gray}7$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $7$ | $1$ |
| $\color{gray}6$ | $1$ | $2$ | $3$ | $2$ | $1$ | $6$ | $1$ | $2$ |
| $\color{gray}5$ | $1$ | $1$ | $1$ | $1$ | $5$ | $1$ | $1$ | $1$ |
| $\color{gray}4$ | $1$ | $2$ | $1$ | $4$ | $1$ | $2$ | $1$ | $4$ |
| $\color{gray}3$ | $1$ | $1$ | $3$ | $1$ | $1$ | $3$ | $1$ | $1$ |
| $\color{gray}2$ | $1$ | $2$ | $1$ | $2$ | $1$ | $2$ | $1$ | $2$ |
| $\color{gray}1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ |
| $\slfrac nm$ | $\color{gray}1$ | $\color{gray}2$ | $\color{gray}3$ | $\color{gray}4$ | $\color{gray}5$ | $\color{gray}6$ | $\color{gray}7$ | $\color{gray}8$ |
四則演算すら使わず転写だけで表が出来ました。
適当なアルゴリズムでプロット
投稿日：8月15日
投稿者
投稿者
この記事を高評価した人
この記事を高評価した人
高評価したユーザはいません
コメント
コメント