יהיו a=294 ו- b=399. אני מנסה למצוא את d\in\mathbb{Z} המקיים d=(294,399). במילים אחרות, אני מנסה לחשב את מחלק המשותף המקסימלי של a ו-b. באיזה דרך אני צריך לחשב את זה?
תודה רבה
קיימות דרכים רבות כדי לחשב את ה-GCD של a ו-b. בפתרון, אני אציג שתי דרכים שונות.
הדרך הראשונה היא לחשב את המחלק המשותף המקסימלי באופן ישיר בעזרת אלגוריתם אוקלידס:
\begin{align*}
&399=1\cdot294+105\\&294=2\cdot105+84\\&105=1\cdot84+21\\&84=4\cdot21+0
\end{align*}
לכן נקבל:
(294,399)=(294,105)=(84,105)=(84,21)=(0,21)=21
הדרך השנייה לחשב את המחלק המשותף המקסימלי היא בעזרת משפט היסודי של האריתמטיקה - יהיו a,b\in\mathbb{N} אשר מקיימים:
\begin{align*}
&a=\prod_{i=1}^{n}p_{i}^{a_{i}}\\&b=\prod_{i=1}^{n}p_{i}^{b_{i}}
\end{align*}
כך שלכל i\in[1,n], המספר p_{i} הוא ראשוני ו-a_{i},b_{i}\in\mathbb{N}\cup\{0\}. לכן מתקיים:
\begin{align*}
&(a,b)=\prod_{i=1}^{n}p_{i}^{min\{a_{i},b_{i}\}}\\&[a,b]=\prod_{i=1}^{n}p_{i}^{max\{a_{i},b_{i}\}}
\end{align*}
נחזור לשאלה - נשים לב כי מתקיים:
\begin{align*}
&294=2^{1}\cdot3^{1}\cdot7^{2}\cdot19^{0}\\&399=2^{0}\cdot3^{1}\cdot7^{1}\cdot19^{1}
\end{align*}
לכן ע"פ המשפט היסודי של האריתמטיקה נקבל:
\begin{align*}
(294,399)&=2^{min\{1,0\}}\cdot3^{min\{1,1\}}\cdot7^{min\{2,1\}}\cdot19^{min\{0,1\}}\\&=2^{0}\cdot3^{1}\cdot7^{1}\cdot19^{0}=21
\end{align*}
בכל אחת משתי הדרכים קיבלנו d=21.
לייק 1