عدد $x$ را طوری بیابید که $\text{g.c.d}(160,x)=1$.

Question

می‌خواهیم عدد $x$ را به گونه‌ای انتخاب کنیم که $\text{g.c.d}(x,160)=1$. روشی سراغ دارید که آسون باشه. در جزوه ما $x$ رو مثلا عدد ۷ در نظر گرفته است. ممنون.

Comments

@fo-eng شما دنبال الگوریتمی هستید که ب.م.م. دو عدد داده شده را محاسبه کند، یا الگوریتمی که عددی پیدا کند که نسبت به یک عدد داده شده اول باشد، یا اینکه یک عدد دارید، می‌خواهید عددی بیابید که ب.م.م.اش با عدد قبلی برابر عدد داده‌شده‌ای باشد. اینها ۳ پرسش کاملا متفاوت هستند و معنایشان به هیچ وجه یکسان نیست. لطفا خواستهٔ پرسش‌تان را به طور یکتا مشخص کنید.

Answer 1

اگر 160 را تجزیه کنیم داریم: $$160=2^5 \times 5$$ اگر بخواهیم عددی را انتخاب کنیم که نسبت به 160 اول باشد باید در تجزیه آن عاملهای اولی غیر از 2 و 5 داشته باشیم.

مثلا: $e=3$ یا هر توانی از 3

یا $e=7$ یا هر توانی از 7

یا $e=3 \times 7=21$

زیرا ب م م دو عدد برابر است با پایه های مشترک با کمترین توان.

وقتی $e$ را به شکل بالا انتخاب کنیم با 160 هیچ پایه مشترکی ندارند و لذا ب م م آنها 1 می شود.

Comments

این لینک رو مشاهده بفرمایید:
آمده ب م م را از روش اقلیدسی حساب کرده است یعنی تقسیم هوی متوالی. به نظرتون این روش صحیح است:

http://fa.wikipedia.org/wiki/بزرگ‌ترین_مقسوم‌علیه_مشترک

---

بله درسته.ب م م رو میشه از روشهای مختلف به دست آورد از جمله تقسیم های متوالی و یا تجزیه به عامل های اول و ...

ولی در نهایت همه روش ها به یک جواب می رسند.

---

خب الان بیایید 160 روتقسیم بر 7 کنید!
تا چه زمانی باید این کار رو ادامه بدیم؟
الان توی همون مرحله اول 160 تقسیم 7 باقی مانده شده 6  ...
مرحله بعد هم دوباره می تونیم هفت رو تقسیم شش کنیم و باقی مانده میشه 1. چرا این رو قبول نکرده؟

---

بعد از 1 باز هم تقسیم ادامه داره، در ادامه پاسخ ب م م 160 و 7 رو هم براتون نوشتم.

Answer 2

به عنوان مثال می توان ب م م دو عدد 84 و 18 را به روش تقسیم های متوالی به شکل زیر به دست آورد، این کار را تا جایی ادامه می دهیم که به باقیمانده صفر برسیم. در این صورت آخرین مقسوم علیه، ب م م می باشد.

ابتدا ۸۴ را به ۱۸ تقسیم می کنیم؛ خارج قسمت تقسیم ۴ و باقی‌مانده ۱۲ بدست می‌آید. خارج قسمت را بالا و باقیمانده را سمت راست مقسوم علیه قرار می دهیم. سپس ۱۸ را بر ۱۲ تقسیم می کنیم؛ خارج قسمت ۱ و باقی‌مانده ۶ بدست می‌آید؛ مجدداً ۱۲ را بر ۶ تقسیم می‌کنیم؛ خارج قسمت ۲ و باقی‌مانده ۰ می‌شود. پس عدد ۶ ب.م.م دو عدد ۸۴ و ۱۸ است.

روش دوم: تجزیه به عاملهای اول: $$84=3 \times 7 \times 2^2 $$ $$18=2 \times 3^2$$ ب م م عبارتست از حاصلضرب پایه های مشترک با کمترین توان یعنی:$3 \times 2=6$

ب م م 160 و 7 برابر است با 1، زیرا:

Answer 3

اگر شرط اضافه‌تری روی $e$ نگذارید خیلی بدیهی می‌توانید عدد ۱ را انتخاب کنید چون ب.م.م. هر عددی با ۱ برابر با ۱ است.