Question and Answers Forum

All Questions      Topic List

Arithmetic Questions

Previous in All Question      Next in All Question      

Previous in Arithmetic      Next in Arithmetic      

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

exercise  Let a and b be natural integers such that 0<a<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 the remainder of the euclidean division of   n^b −1 by n^a −1 is n^r −1 where r is the remainder  of the euclidean division of b by a.    3. For any non−zero naturel number n, show   that gcd(n^b −1, n^a −1) = n^d −1 where d = gcd(b,c).                   by professor henderson^(−) .

$$\underline{\boldsymbol{\mathrm{exercise}}} \\ $$ $$\boldsymbol{\mathrm{Let}}\:\boldsymbol{{a}}\:\boldsymbol{\mathrm{and}}\:\boldsymbol{{b}}\:\boldsymbol{\mathrm{be}}\:\boldsymbol{\mathrm{natural}}\:\boldsymbol{\mathrm{integers}}\:\boldsymbol{\mathrm{such}}\:\boldsymbol{\mathrm{that}}\:\mathrm{0}<\boldsymbol{{a}}<\boldsymbol{{b}}. \\ $$ $$\mathrm{1}.\:\boldsymbol{\mathrm{Show}}\:\boldsymbol{\mathrm{that}}\:\boldsymbol{\mathrm{if}}\:\boldsymbol{{a}}\:\boldsymbol{\mathrm{divides}}\:\boldsymbol{{b}},\:\boldsymbol{\mathrm{then}}\:\boldsymbol{\mathrm{for}}\:\boldsymbol{\mathrm{any}}\:\boldsymbol{\mathrm{naturel}}\: \\ $$ $$\boldsymbol{\mathrm{number}}\:\boldsymbol{{n}},\:\boldsymbol{{n}}^{\boldsymbol{{a}}} −\mathrm{1}\:\boldsymbol{\mathrm{divides}}\:\boldsymbol{{n}}^{\boldsymbol{{b}}} −\mathrm{1}. \\ $$ $$ \\ $$ $$\mathrm{2}.\:\boldsymbol{\mathrm{For}}\:\boldsymbol{\mathrm{any}}\:\boldsymbol{\mathrm{non}}−\boldsymbol{\mathrm{zero}}\:\boldsymbol{\mathrm{naturel}}\:\boldsymbol{\mathrm{number}}\:\boldsymbol{{n}},\:\boldsymbol{\mathrm{prove}}\: \\ $$ $$\boldsymbol{\mathrm{that}}\:\boldsymbol{\mathrm{the}}\:\boldsymbol{\mathrm{remainder}}\:\boldsymbol{\mathrm{of}}\:\boldsymbol{\mathrm{the}}\:\boldsymbol{\mathrm{euclidean}}\:\boldsymbol{\mathrm{division}}\:\boldsymbol{\mathrm{of}}\: \\ $$ $$\boldsymbol{{n}}^{\boldsymbol{{b}}} −\mathrm{1}\:\boldsymbol{\mathrm{by}}\:\boldsymbol{{n}}^{\boldsymbol{{a}}} −\mathrm{1}\:\boldsymbol{\mathrm{is}}\:\boldsymbol{{n}}^{\boldsymbol{{r}}} −\mathrm{1}\:\boldsymbol{\mathrm{where}}\:\boldsymbol{{r}}\:\boldsymbol{\mathrm{is}}\:\boldsymbol{\mathrm{the}}\:\boldsymbol{\mathrm{remainder}} \\ $$ $$\boldsymbol{\mathrm{of}}\:\boldsymbol{\mathrm{the}}\:\boldsymbol{\mathrm{euclidean}}\:\boldsymbol{\mathrm{division}}\:\boldsymbol{\mathrm{of}}\:\boldsymbol{{b}}\:\boldsymbol{\mathrm{by}}\:\boldsymbol{{a}}. \\ $$ $$ \\ $$ $$\mathrm{3}.\:\boldsymbol{\mathrm{For}}\:\boldsymbol{\mathrm{any}}\:\boldsymbol{\mathrm{non}}−\boldsymbol{\mathrm{zero}}\:\boldsymbol{\mathrm{naturel}}\:\boldsymbol{\mathrm{number}}\:\boldsymbol{{n}},\:\boldsymbol{\mathrm{show}}\: \\ $$ $$\boldsymbol{\mathrm{that}}\:\boldsymbol{{gcd}}\left(\boldsymbol{{n}}^{\boldsymbol{{b}}} −\mathrm{1},\:\boldsymbol{{n}}^{\boldsymbol{{a}}} −\mathrm{1}\right)\:=\:\boldsymbol{{n}}^{\boldsymbol{{d}}} −\mathrm{1}\:\boldsymbol{\mathrm{where}}\:\boldsymbol{{d}}\:=\:\boldsymbol{{gcd}}\left(\boldsymbol{{b}},\boldsymbol{{c}}\right). \\ $$ $$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\overline {\boldsymbol{{by}}\:\boldsymbol{{professor}}\:\boldsymbol{{henderson}}}. \\ $$

Answered by mindispower last updated on 01/Jul/21

 a∣b⇒n^a −1∣n^b −1  X^(cn) −1=(X^c −1)(1+X^c +X^(2c) .....+X^(.c(n−1)) )  a∣b⇒b=ma  n^b −1=n^(ma) −1=(n^a −1).(1+n^a +........+n^(a(m−1)) ).using (1)  ⇒n^a −1∣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) ∣n^(ma) −1.....by using a∣ma  ⇒n^b −1≡(n^r −1)mod(n^a −1)  since0≤ n^r −1<min(n^a −1,n^b −1)  n^r −1 is remainder of division   n^b −1by n^a −1  let d=gcd(a,b)  ⇒n^d −1∣n^a −1,n^b −1 withe 1  supoose m∣(n^a −1,n^b −1)  b>a  b=am+r  ⇒m∣n^a −1,n^r −1  by reccuraion of euclid  ⇒m∣n^d −1⇒n^d −1>m  ⇒∀M∈N M∣(n^a −1,n^b −1)⇒M∣n^d −1  n^d −1=gcd(n^a −1,n^b −1)

$$\:{a}\mid{b}\Rightarrow{n}^{{a}} −\mathrm{1}\mid{n}^{{b}} −\mathrm{1} \\ $$ $${X}^{{cn}} −\mathrm{1}=\left({X}^{{c}} −\mathrm{1}\right)\left(\mathrm{1}+{X}^{{c}} +{X}^{\mathrm{2}{c}} .....+{X}^{.{c}\left({n}−\mathrm{1}\right)} \right) \\ $$ $${a}\mid{b}\Rightarrow{b}={ma} \\ $$ $${n}^{{b}} −\mathrm{1}={n}^{{ma}} −\mathrm{1}=\left({n}^{{a}} −\mathrm{1}\right).\left(\mathrm{1}+{n}^{{a}} +........+{n}^{{a}\left({m}−\mathrm{1}\right)} \right).{using}\:\left(\mathrm{1}\right) \\ $$ $$\Rightarrow{n}^{{a}} −\mathrm{1}\mid{n}^{{b}} −\mathrm{1} \\ $$ $${b}={ma}+{r} \\ $$ $${n}^{{b}} −\mathrm{1}={n}^{{ma}+{r}} −\mathrm{1}+{n}^{{r}} −{n}^{{r}} \\ $$ $${n}^{{b}} −\mathrm{1}={n}^{{r}} \left({n}^{{ma}} −\mathrm{1}\right)+{n}^{{r}} −\mathrm{1} \\ $$ $${n}^{{a}−\mathrm{1}} \mid{n}^{{ma}} −\mathrm{1}.....{by}\:{using}\:{a}\mid{ma} \\ $$ $$\Rightarrow{n}^{{b}} −\mathrm{1}\equiv\left({n}^{{r}} −\mathrm{1}\right){mod}\left({n}^{{a}} −\mathrm{1}\right) \\ $$ $${since}\mathrm{0}\leqslant\:{n}^{{r}} −\mathrm{1}<{min}\left({n}^{{a}} −\mathrm{1},{n}^{{b}} −\mathrm{1}\right) \\ $$ $${n}^{{r}} −\mathrm{1}\:{is}\:{remainder}\:{of}\:{division}\: \\ $$ $${n}^{{b}} −\mathrm{1}{by}\:{n}^{{a}} −\mathrm{1} \\ $$ $${let}\:{d}={gcd}\left({a},{b}\right) \\ $$ $$\Rightarrow{n}^{{d}} −\mathrm{1}\mid{n}^{{a}} −\mathrm{1},{n}^{{b}} −\mathrm{1}\:{withe}\:\mathrm{1} \\ $$ $${supoose}\:{m}\mid\left({n}^{{a}} −\mathrm{1},{n}^{{b}} −\mathrm{1}\right) \\ $$ $${b}>{a} \\ $$ $${b}={am}+{r} \\ $$ $$\Rightarrow{m}\mid{n}^{{a}} −\mathrm{1},{n}^{{r}} −\mathrm{1} \\ $$ $${by}\:{reccuraion}\:{of}\:{euclid} \\ $$ $$\Rightarrow{m}\mid{n}^{{d}} −\mathrm{1}\Rightarrow{n}^{{d}} −\mathrm{1}>{m} \\ $$ $$\Rightarrow\forall{M}\in\mathbb{N}\:{M}\mid\left({n}^{{a}} −\mathrm{1},{n}^{{b}} −\mathrm{1}\right)\Rightarrow{M}\mid{n}^{{d}} −\mathrm{1} \\ $$ $${n}^{{d}} −\mathrm{1}={gcd}\left({n}^{{a}} −\mathrm{1},{n}^{{b}} −\mathrm{1}\right) \\ $$ $$ \\ $$

Commented bygreg_ed last updated on 01/Jul/21

sir, this line n^(a−1) ∣n^(ma) −1.....by using a∣ma isn′t   n^a −1∣n^(ma) −1.....by using a∣ma ?

$$\mathrm{sir},\:\mathrm{this}\:\mathrm{line}\:{n}^{{a}−\mathrm{1}} \mid{n}^{{ma}} −\mathrm{1}.....{by}\:{using}\:{a}\mid{ma}\:\mathrm{isn}'\mathrm{t}\: \\ $$ $${n}^{{a}} −\mathrm{1}\mid{n}^{{ma}} −\mathrm{1}.....{by}\:{using}\:{a}\mid{ma}\:? \\ $$

Commented bymindispower last updated on 03/Jul/21

yes sir

$${yes}\:{sir}\: \\ $$

Terms of Service

Privacy Policy

Contact: info@tinkutara.com