Question

فرض کنید $m,n,a$ اعدا طبیعی باشند و $a > 1$ ثابت کنید:

$(a^{m} -1 , a^{n} -1 ) = a^{(m,n)} -1$

منظور از $(a,b)$ بزرگترین مقسوم علیه مشترک $a , b$ است.

Answer 1

اگر $m,n$ دو عدد صحیح باشند که $m \geq n$ بنا به قضیۀ تقسیم داریم:

$m=nq+r,q,r \in Z,0 \leq r< n,(m,n)=(n,r)$

حالا در اینجا داری:

$a^m-1=a^{nq+r}-1=a^r(a^{nq})-1=a^r(a^{nq})-a^r+a^r-1=a^r(a^{nq}-1)+(r^r-1)$

$=a^r((a^n)^q-1)+(a^r-1)=a^r(a^n-1)s+(a^r-1),0 \leq a^r-1< a^n-1$(چرا؟)

$\Rightarrow (a^m-1,a^n-1)=(a^n-1,a^r-1)$

حالا اگر این رون را ادامه دهیم بعد از چند مرحله به باقیمانده صفر میرسیم و آخرین خارج قسمت همانا ب.م.م است یعنی:

$(m,n)=(n,r)=(r,t)=...=d$

$,(a^m-1,a^n-1)=(a^n-1,a^r-1)=...=(a^d-1)=(a^{(m,n)}-1)$

$\Box$