Question and Answers Forum

All Questions      Topic List

Algebra Questions

Previous in All Question      Next in All Question      

Previous in Algebra      Next in Algebra      

Question Number 30119 by rahul 19 last updated on 16/Feb/18

Let N= 2^(1224) −1. S= 2^(153) +2^(77) +1. T= 2^(408) −2^(204) +1. then which of the following statment is correct? a) S and T both divide N. b) only S divides N. c) only T divides N. d) Neither S nor T divides N.

$$\mathrm{Let}\:\:\mathrm{N}=\:\mathrm{2}^{\mathrm{1224}} \:−\mathrm{1}. \\ $$$$\mathrm{S}=\:\mathrm{2}^{\mathrm{153}} +\mathrm{2}^{\mathrm{77}} +\mathrm{1}. \\ $$$$\mathrm{T}=\:\mathrm{2}^{\mathrm{408}} −\mathrm{2}^{\mathrm{204}} +\mathrm{1}. \\ $$$$\mathrm{then}\:\mathrm{which}\:\mathrm{of}\:\mathrm{the}\:\mathrm{following}\:\mathrm{statment}\:\mathrm{is} \\ $$$$\:\mathrm{correct}? \\ $$$$\left.\mathrm{a}\right)\:\mathrm{S}\:\mathrm{and}\:\mathrm{T}\:\mathrm{both}\:\mathrm{divide}\:\mathrm{N}. \\ $$$$\left.\mathrm{b}\right)\:\mathrm{only}\:\mathrm{S}\:\mathrm{divides}\:\mathrm{N}. \\ $$$$\left.\mathrm{c}\right)\:\mathrm{only}\:\mathrm{T}\:\mathrm{divides}\:\mathrm{N}. \\ $$$$\left.\mathrm{d}\right)\:\mathrm{Neither}\:\mathrm{S}\:\mathrm{nor}\:\mathrm{T}\:\mathrm{divides}\:\mathrm{N}. \\ $$

Commented by rahul 19 last updated on 16/Feb/18

sir how does this prooves that S divides N? as the ans. is A.

$$\mathrm{sir}\:\mathrm{how}\:\mathrm{does}\:\mathrm{this}\:\mathrm{prooves}\:\mathrm{that}\:\mathrm{S}\:\mathrm{divides} \\ $$$$\mathrm{N}?\:\mathrm{as}\:\mathrm{the}\:\mathrm{ans}.\:\mathrm{is}\:\mathrm{A}. \\ $$

Answered by Giannibo last updated on 16/Feb/18

N=2^(1224) −1^(1224) =(2^(612) −1^(612) )(2^(612) +1^(612) )= (2^(306) −1)(2^(306) +1)(2^(612) +1)= 2^(153) +2^(77) ≡−1modS ⇒2^(154) +2^(78) ≡−2modS⇒2^(154) +2^(78) +1=(2^(77) +1)^2 ≡−1modS 2^(153) ≡(−2^(77) −1)modS (2^(153) )^2 ≡(2^(77) +1)^2 modS ⇒2^(306) ≡−1modS⇒2^(306) +1≡0modS S∣(2^(306) +1) & (2^(306) +1)∣N S∣N N=(2^(612) −1)(2^(612) +1)=((2^(204) )^3 +1^3 )(2^(612) −1)= (2^(204) +1)((2^(204) )^2 −2^(204) +1)(2^(612) −1) T=2^(408) −2^(204) +1∣N

$$ \\ $$$$ \\ $$$$\mathrm{N}=\mathrm{2}^{\mathrm{1224}} −\mathrm{1}^{\mathrm{1224}} =\left(\mathrm{2}^{\mathrm{612}} −\mathrm{1}^{\mathrm{612}} \right)\left(\mathrm{2}^{\mathrm{612}} +\mathrm{1}^{\mathrm{612}} \right)= \\ $$$$\left(\mathrm{2}^{\mathrm{306}} −\mathrm{1}\right)\left(\mathrm{2}^{\mathrm{306}} +\mathrm{1}\right)\left(\mathrm{2}^{\mathrm{612}} +\mathrm{1}\right)= \\ $$$$\mathrm{2}^{\mathrm{153}} +\mathrm{2}^{\mathrm{77}} \equiv−\mathrm{1modS}\:\Rightarrow\mathrm{2}^{\mathrm{154}} +\mathrm{2}^{\mathrm{78}} \equiv−\mathrm{2modS}\Rightarrow\mathrm{2}^{\mathrm{154}} +\mathrm{2}^{\mathrm{78}} +\mathrm{1}=\left(\mathrm{2}^{\mathrm{77}} +\mathrm{1}\right)^{\mathrm{2}} \equiv−\mathrm{1modS} \\ $$$$\mathrm{2}^{\mathrm{153}} \equiv\left(−\mathrm{2}^{\mathrm{77}} −\mathrm{1}\right)\mathrm{modS} \\ $$$$\left(\mathrm{2}^{\mathrm{153}} \right)^{\mathrm{2}} \equiv\left(\mathrm{2}^{\mathrm{77}} +\mathrm{1}\right)^{\mathrm{2}} \mathrm{modS}\:\Rightarrow\mathrm{2}^{\mathrm{306}} \equiv−\mathrm{1modS}\Rightarrow\mathrm{2}^{\mathrm{306}} +\mathrm{1}\equiv\mathrm{0modS} \\ $$$$\mathrm{S}\mid\left(\mathrm{2}^{\mathrm{306}} +\mathrm{1}\right)\:\&\:\left(\mathrm{2}^{\mathrm{306}} +\mathrm{1}\right)\mid\mathrm{N} \\ $$$$\mathrm{S}\mid\mathrm{N} \\ $$$$\mathrm{N}=\left(\mathrm{2}^{\mathrm{612}} −\mathrm{1}\right)\left(\mathrm{2}^{\mathrm{612}} +\mathrm{1}\right)=\left(\left(\mathrm{2}^{\mathrm{204}} \right)^{\mathrm{3}} +\mathrm{1}^{\mathrm{3}} \right)\left(\mathrm{2}^{\mathrm{612}} −\mathrm{1}\right)= \\ $$$$\left(\mathrm{2}^{\mathrm{204}} +\mathrm{1}\right)\left(\left(\mathrm{2}^{\mathrm{204}} \right)^{\mathrm{2}} −\mathrm{2}^{\mathrm{204}} +\mathrm{1}\right)\left(\mathrm{2}^{\mathrm{612}} −\mathrm{1}\right) \\ $$$$\mathrm{T}=\mathrm{2}^{\mathrm{408}} −\mathrm{2}^{\mathrm{204}} +\mathrm{1}\mid\mathrm{N} \\ $$

Commented by rahul 19 last updated on 17/Feb/18

what is ≡ mod ?

$$\mathrm{what}\:\mathrm{is}\:\equiv\:\mathrm{mod}\:? \\ $$

Commented by prof Abdo imad last updated on 19/Feb/18

x≡y [n] means ∃k∈Z /x−y=kn or n divide x−y.

$${x}\equiv{y}\:\left[{n}\right]\:{means}\:\exists{k}\in{Z}\:/{x}−{y}={kn}\:\:{or}\:{n}\:{divide}\:{x}−{y}. \\ $$

Answered by MJS last updated on 16/Feb/18

I set n=51 N=2^(24n) −1 S=2^(3n) +2^((3n+1)/2) +1 T=2^(8n) −2^(4n) +1 then I made polynome divisions N/T=2^(16n) +2^(12n) −2^(4n) −1 this is integer for n∈N N/S=2^(21n) −2^((39n+1)/2) +2^(18n) −2^(15n) +2^((27n+1)/2) −2^(12n) +2^(9n) −2^((15n+1)/2) +2^(6n) −2^(3n) +2^((3n+1)/2) −1 this is surely integer for n=2k−1; k∈N 51=2∙26−1 therefore answer A is correct S∣N ∧ T∣N

$$\mathrm{I}\:\mathrm{set}\:{n}=\mathrm{51} \\ $$$${N}=\mathrm{2}^{\mathrm{24}{n}} −\mathrm{1} \\ $$$${S}=\mathrm{2}^{\mathrm{3}{n}} +\mathrm{2}^{\frac{\mathrm{3}{n}+\mathrm{1}}{\mathrm{2}}} +\mathrm{1} \\ $$$${T}=\mathrm{2}^{\mathrm{8}{n}} −\mathrm{2}^{\mathrm{4n}} +\mathrm{1} \\ $$$$\mathrm{then}\:\mathrm{I}\:\mathrm{made}\:\mathrm{polynome}\:\mathrm{divisions} \\ $$$${N}/{T}=\mathrm{2}^{\mathrm{16}{n}} +\mathrm{2}^{\mathrm{12}{n}} −\mathrm{2}^{\mathrm{4}{n}} −\mathrm{1} \\ $$$$\mathrm{this}\:\mathrm{is}\:\mathrm{integer}\:\mathrm{for}\:{n}\in\mathbb{N} \\ $$$${N}/{S}=\mathrm{2}^{\mathrm{21}{n}} −\mathrm{2}^{\frac{\mathrm{39}{n}+\mathrm{1}}{\mathrm{2}}} +\mathrm{2}^{\mathrm{18}{n}} −\mathrm{2}^{\mathrm{15}{n}} +\mathrm{2}^{\frac{\mathrm{27}{n}+\mathrm{1}}{\mathrm{2}}} −\mathrm{2}^{\mathrm{12}{n}} +\mathrm{2}^{\mathrm{9}{n}} −\mathrm{2}^{\frac{\mathrm{15}{n}+\mathrm{1}}{\mathrm{2}}} +\mathrm{2}^{\mathrm{6}{n}} −\mathrm{2}^{\mathrm{3}{n}} +\mathrm{2}^{\frac{\mathrm{3}{n}+\mathrm{1}}{\mathrm{2}}} −\mathrm{1} \\ $$$$\mathrm{this}\:\mathrm{is}\:\mathrm{surely}\:\mathrm{integer}\:\mathrm{for}\:{n}=\mathrm{2}{k}−\mathrm{1};\:{k}\in\mathbb{N} \\ $$$$\mathrm{51}=\mathrm{2}\centerdot\mathrm{26}−\mathrm{1} \\ $$$$\mathrm{therefore}\:\mathrm{answer}\:\mathrm{A}\:\mathrm{is}\:\mathrm{correct}\:{S}\mid{N}\:\wedge\:{T}\mid{N} \\ $$$$ \\ $$

Commented by rahul 19 last updated on 17/Feb/18

little tricky sol. as it is tough to set n=51.

$$\mathrm{little}\:\mathrm{tricky}\:\mathrm{sol}.\:\mathrm{as}\:\mathrm{it}\:\mathrm{is}\:\mathrm{tough}\:\mathrm{to}\:\mathrm{set}\:\mathrm{n}=\mathrm{51}. \\ $$

Commented by MJS last updated on 17/Feb/18

the polynome division with the original numbers is more complicated

$$\mathrm{the}\:\mathrm{polynome}\:\mathrm{division}\:\mathrm{with}\:\mathrm{the} \\ $$$$\mathrm{original}\:\mathrm{numbers}\:\mathrm{is}\:\mathrm{more} \\ $$$$\mathrm{complicated} \\ $$

Commented by Rasheed.Sindhi last updated on 17/Feb/18

To rahul, It′s not so much tough to set 51 51 is GCD of 1224,153,408 &204

$$\mathrm{To}\:\mathrm{rahul}, \\ $$$$\mathrm{It}'\mathrm{s}\:\mathrm{not}\:\mathrm{so}\:\mathrm{much}\:\mathrm{tough}\:\mathrm{to}\:\mathrm{set}\:\mathrm{51} \\ $$$$\mathrm{51}\:\mathrm{is}\:\mathrm{GCD}\:\mathrm{of}\:\mathrm{1224},\mathrm{153},\mathrm{408}\:\&\mathrm{204} \\ $$

Commented by rahul 19 last updated on 17/Feb/18

thank you sir .

$$\mathrm{thank}\:\mathrm{you}\:\mathrm{sir}\:. \\ $$

Terms of Service

Privacy Policy

Contact: info@tinkutara.com