次に示すユークリッドの互除法(方法 1，方法 2)で、正の整数 a, b の最大公約数
は、それぞれ m と n のどちらの変数に求まるか。ここで，m mod n は，m を n
で割った余りを表す。
方法 1 方法 2 ＿＿＿＿＿ ＿＿＿＿＿ （ 開 始 ） （ 開 始 ） ￣￣│￣￣ ￣￣│￣￣ ┌───┴───┐ ┌───┴───┐ │ a → m │ │ a → m │ │ b → n │ │ b → n │ └───┬───┘ └───┬───┘ ┌───┴───┐ ──┴── │ m mod n → r │ ／ ループ 2 ＼ └───┬───┘ │ │ ──┴── └───┬───┘ ／ ループ 1 ＼ ┌───┴───┐ │ r = 0 │ │ m mod n → r │ └───┬───┘ └───┬───┘ ┌───┴───┐ ┌───┴───┐ │ n → m │ │ n → m │ └───┬───┘ └───┬───┘ ┌───┴───┐ ┌───┴───┐ │ r → n │ │ r → n │ └───┬───┘ └───┬───┘ ┌───┴───┐ ┌───┴───┐ │ m mod n → r │ │ r = 0 │ └───┬───┘ ＼ ループ 2 ／ ┌───┴───┐ ──┬── │ │ ＿＿｜＿＿ ＼ ループ 1 ／ （ 終 了 ） ──┬── ￣￣￣￣￣ ＿＿｜＿＿ （ 終 了 ） ￣￣￣￣￣ ┌─┬─────┬─────┐ │ │ 方法 1 │ 方法 2 │ ├─┼─────┼─────┤ │ア│ m │ m │ ├─┼─────┼─────┤ │イ│ m │ n │ ├─┼─────┼─────┤ │ウ│ n │ m │ ├─┼─────┼─────┤ │エ│ n │ n │ └─┴─────┴─────┘
