exercise-Let-a-and-b-be-natural-integers-such-that-0-lt-a-lt-b-1-Show-that-if-a-divides-b-then-for-any-naturel-number-n-n-a-1-divides-n-b-1-2-For-any-non-zero-naturel-number-n-prove-that-t

FacebookTweetPin

Question Number 144980 by henderson last updated on 01/Jul/21

$$\underset{―}{\mathbf{exercise}}$$$$\mathbf{Let}\mathit{a}\mathbf{and}\mathit{b}\mathbf{be}\mathbf{natural}\mathbf{integers}\mathbf{such}\mathbf{that}0<\mathit{a}<\mathit{b}.$$$$1.\mathbf{Show}\mathbf{that}\mathbf{if}\mathit{a}\mathbf{divides}\mathit{b},\mathbf{then}\mathbf{for}\mathbf{any}\mathbf{naturel}$$$$\mathbf{number}\mathit{n},{\mathit{n}}^{\mathit{a}}-1\mathbf{divides}{\mathit{n}}^{\mathit{b}}-1.$$$$$$$$2.\mathbf{For}\mathbf{any}\mathbf{non}-\mathbf{zero}\mathbf{naturel}\mathbf{number}\mathit{n},\mathbf{prove}$$$$\mathbf{that}\mathbf{the}\mathbf{remainder}\mathbf{of}\mathbf{the}\mathbf{euclidean}\mathbf{division}\mathbf{of}$$$${\mathit{n}}^{\mathit{b}}-1\mathbf{by}{\mathit{n}}^{\mathit{a}}-1\mathbf{is}{\mathit{n}}^{\mathit{r}}-1\mathbf{where}\mathit{r}\mathbf{is}\mathbf{the}\mathbf{remainder}$$$$\mathbf{of}\mathbf{the}\mathbf{euclidean}\mathbf{division}\mathbf{of}\mathit{b}\mathbf{by}\mathit{a}.$$$$$$$$3.\mathbf{For}\mathbf{any}\mathbf{non}-\mathbf{zero}\mathbf{naturel}\mathbf{number}\mathit{n},\mathbf{show}$$$$\mathbf{that}\mathit{g}\mathit{c}\mathit{d}({\mathit{n}}^{\mathit{b}}-1,{\mathit{n}}^{\mathit{a}}-1)={\mathit{n}}^{\mathit{d}}-1\mathbf{where}\mathit{d}=\mathit{g}\mathit{c}\mathit{d}(\mathit{b},\mathit{c}).$$$$\overline{\mathit{b}\mathit{y}\mathit{p}\mathit{r}\mathit{o}\mathit{f}\mathit{e}\mathit{s}\mathit{s}\mathit{o}\mathit{r}\mathit{h}\mathit{e}\mathit{n}\mathit{d}\mathit{e}\mathit{r}\mathit{s}\mathit{o}\mathit{n}}.$$

Answered by mindispower last updated on 01/Jul/21

$$a\mid b\Rightarrow n^a-1\mid n^b-1$$$$X^{cn}-1=(X^c-1)(1+X^c+X^{2c}\dots ..+X^{.c(n-1)})$$$$a\mid b\Rightarrow b=ma$$$$n^b-1=n^{ma}-1=(n^a-1).(1+n^a+\dots \dots ..+n^{a(m-1)}).using\left(1\right)$$$$\Rightarrow n^a-1\mid n^b-1$$$$b=ma+r$$$$n^b-1=n^{ma+r}-1+n^r-n^r$$$$n^b-1=n^r(n^{ma}-1)+n^r-1$$$$n^{a-1}\mid n^{ma}-1\dots ..byusinga\mid ma$$$$\Rightarrow n^b-1\equiv (n^r-1)mod(n^a-1)$$$$since0⩽n^r-1<min(n^a-1,n^b-1)$$$$n^r-1isremainderofdivision$$$$n^b-1by{n}^a-1$$$$letd=gcd(a,b)$$$$\Rightarrow n^d-1\mid n^a-1,n^b-1withe1$$$$supoosem\mid (n^a-1,n^b-1)$$$$b>a$$$$b=am+r$$$$\Rightarrow m\mid n^a-1,n^r-1$$$$byreccuraionofeuclid$$$$\Rightarrow m\mid n^d-1\Rightarrow n^d-1>m$$$$\Rightarrow \mathrm{\forall }M\in \mathbb{N}M\mid (n^a-1,n^b-1)\Rightarrow M\mid n^d-1$$$$n^d-1=gcd(n^a-1,n^b-1)$$$$$$

Commented by greg_ed last updated on 01/Jul/21

$$\mathrm{sir},\mathrm{this}\mathrm{line}{n}^{a-1}\mid n^{ma}-1\dots ..byusinga\mid ma{\mathrm{isn}}^{\prime }\mathrm{t}$$$$n^a-1\mid n^{ma}-1\dots ..byusinga\mid ma?$$

Commented by mindispower last updated on 03/Jul/21

$$yessir$$

Terms of Service
Privacy Policy
Contact: info@tinkutara.com

FacebookTweetPin