數與座標系/3 最大公因數與最小公倍數-範例

出自高材生

< 數與座標系

跳轉到: 導航, 搜索

範例8
1. 求解： $5814\,$ 與 $6018\,$ 之最大公因數
2. 已知： $a,b,q_{1},q_{2},q_{3}\in N$ ，且 $\left\{ \begin{align} & a=b\times q_{1}+4098 \\ & b=4098\times q_{2}+582 \\ & 4098=582\times q_{3}+24 \\ \end{align} \right.$ ，求解： $\left( a,b \right)$
3. 求解： $2^{20}-1\,$ 與 $2^{19}+1\,$ 之最大公因數
- 範例8類題1
  - 已知：
  - 求解：
- 範例8類題2
  - 已知：
  - 求解：
- 範例8類題3
  - 已知：
  - 求解：

範例9
- 已知：
- 求解：
- 範例9類題1
  - 已知：
  - 求解：
- 範例9類題2
  - 已知：
  - 求解：

範例10
- - 已知：
  - 求解：
- 範例10類題
  - 已知：
  - 求解：

範例8

求解： $5814\,$ 與 $6018\,$ 之最大公因數
已知： $a,b,q_{1},q_{2},q_{3}\in N$ ，且 $\left\{ \begin{align} & a=b\times q_{1}+4098 \\ & b=4098\times q_{2}+582 \\ & 4098=582\times q_{3}+24 \\ \end{align} \right.$ ，求解： $\left( a,b \right)$
求解 $2^{20}-1\,$ 與 $2^{19}+1\,$ 之最大公因數

答案

$102\,$
$\left( a,b \right)=6\,$
$3\,$

詳解

1

$5814\overset{1}{\overline{\left){\begin{align} & 6018 \\ & \frac{5814}{204} \\ \end{align}}\right.}}$
$204\overset{28}{\overline{\left){\begin{align} & 5814 \\ & \frac{4080}{1734} \\ & \frac{1632}{102} \\ & \\ \end{align}}\right.}}$
$102\overset{2}{\overline{\left){\begin{align} & 204 \\ & \frac{204}{0} \\ \end{align}}\right.}}\#$

2

$\left\{ \begin{align} & a=b\times q_{1}+4098 \\ & b=4098\times q_{2}+582 \\ & 4098=582\times q_{3}+24 \\ \end{align} \right.\Rightarrow \left\{ \begin{align} & \frac{a}{b}=\frac{b\times q_{1}}{b}+\frac{4098}{b} \\ & \frac{b}{4098}=\frac{4098\times q_{2}}{4098}+\frac{582}{4098} \\ & \frac{4098}{582}=\frac{582\times q_{3}}{582}+\frac{24}{582} \\ \end{align} \right.$
$\frac{582}{24}=\frac{24\times 24}{24}+\frac{6}{24}$
$\frac{24}{6}=\frac{6\times 4}{6}+\frac{0}{6}\Rightarrow \left( a,b \right)=6\#$

3

輾轉相除法：餘數標示紅色
1. $\frac{2^{20}-1}{2^{19}+1}=1+\frac{\left( 2^{20}-1 \right)-\left( 2^{19}+1 \right)}{2^{19}+1}=1+\frac{2^{20}-2^{19}-2}{2^{19}+1}=1+\frac{{\color{Red}2^{19}-2}}{2^{19}+1}$
2. $\frac{2^{19}+1}{2^{19}-2}=1+\frac{\left( 2^{19}+1 \right)-\left( 2^{19}-2 \right)}{2^{19}-2}=1+\frac{{\color{Red}3}}{2^{19}-2}$
3. $\frac{2^{19}-2}{3}=\frac{2\left( 2^{18}-1 \right)}{3}=\frac{2\left( 4^{9}-1 \right)}{3}=\frac{2\left( 4-1 \right)\left( 4^{8}+4^{7}+\cdots +4^{1}+1 \right)}{3}$ ，提示：因式分解
  $=\frac{2\times 3\times \left( 4^{8}+4^{7}+\cdots +4^{1}+1 \right)}{3}=2\times \left( 4^{8}+4^{7}+\cdots +4^{1}+1 \right)+\frac{{\color{Red}0}}{3}$
  $\Rightarrow G.C.M\left( 2^{20}-1,2^{19}+1 \right)=3\#$

範例8類題1

已知

求解

答案

詳解

範例8類題2

已知

$a\in Z\,$ 且 $a|a+8,a-1|a+11\,$

求解

$a\,$

答案

詳解

範例8類題3

已知

求解

答案

詳解

範例9

已知

求解

答案

詳解

範例9類題1

已知

求解

答案

詳解

範例9類題2

已知

求解

答案

詳解

範例10

已知

求解

答案

詳解

範例10類題

已知

求解

答案

詳解

取自"http://www.come2pass.com/wiki/index.php/%E6%95%B8%E8%88%87%E5%BA%A7%E6%A8%99%E7%B3%BB/3_%E6%9C%80%E5%A4%A7%E5%85%AC%E5%9B%A0%E6%95%B8%E8%88%87%E6%9C%80%E5%B0%8F%E5%85%AC%E5%80%8D%E6%95%B8-%E7%AF%84%E4%BE%8B"

檢視

個人工具

登入／建立新帳號

12年一貫

搜索

工具箱