Menu Close

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

Tinku Tara 0 Comments
Pin




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 by greg_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 by mindispower last updated on 03/Jul/21
yes sir
$${yes}\:{sir}\: \\ $$

Pin

Leave a Reply

Your email address will not be published. Required fields are marked *