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-

FacebookTweetPin

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

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

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

$$\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

$$$$$$$$$$\mathrm{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}\equiv -1\mathrm{modS}\Rightarrow 2^{154}+2^{78}\equiv -2\mathrm{modS}\Rightarrow 2^{154}+2^{78}+1={(2^{77}+1)}^2\equiv -1\mathrm{modS}$$$$2^{153}\equiv (-2^{77}-1)\mathrm{modS}$$$${\left(2^{153}\right)}^2\equiv {(2^{77}+1)}^2\mathrm{modS}\Rightarrow 2^{306}\equiv -1\mathrm{modS}\Rightarrow 2^{306}+1\equiv 0\mathrm{modS}$$$$\mathrm{S}\mid (2^{306}+1)\mathrm{\&}(2^{306}+1)\mid \mathrm{N}$$$$\mathrm{S}\mid \mathrm{N}$$$$\mathrm{N}=(2^{612}-1)(2^{612}+1)=({\left(2^{204}\right)}^3+1^3)(2^{612}-1)=$$$$(2^{204}+1)({\left(2^{204}\right)}^2-2^{204}+1)(2^{612}-1)$$$$\mathrm{T}=2^{408}-2^{204}+1\mid \mathrm{N}$$

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

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

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

$$x\equiv y\left[n\right]means\mathrm{\exists }k\in Z/x-y=knorndividex-y.$$

Answered by MJS last updated on 16/Feb/18

$$\mathrm{I}\mathrm{set}n=51$$$$N=2^{24n}-1$$$$S=2^{3n}+2^{\frac{3n+1}{2}}+1$$$$T=2^{8n}-2^{4\mathrm{n}}+1$$$$\mathrm{then}\mathrm{I}\mathrm{made}\mathrm{polynome}\mathrm{divisions}$$$$N/T=2^{16n}+2^{12n}-2^{4n}-1$$$$\mathrm{this}\mathrm{is}\mathrm{integer}\mathrm{for}n\in \mathbb{N}$$$$N/S=2^{21n}-2^{\frac{39n+1}{2}}+2^{18n}-2^{15n}+2^{\frac{27n+1}{2}}-2^{12n}+2^{9n}-2^{\frac{15n+1}{2}}+2^{6n}-2^{3n}+2^{\frac{3n+1}{2}}-1$$$$\mathrm{this}\mathrm{is}\mathrm{surely}\mathrm{integer}\mathrm{for}n=2k-1;k\in \mathbb{N}$$$$51=2\cdot 26-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

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

Commented by MJS last updated on 17/Feb/18

$$\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

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

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

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

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

FacebookTweetPin