Menu Close

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-

Tinku Tara 0 Comments
Pin




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}\:. \\ $$

Pin

Leave a Reply

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