Prove-that-41-divides-2-20-1-

Question Number 35004 by Rasheed.Sindhi last updated on 14/May/18

$$\mathrm{Prove}\:\mathrm{that}\:\mathrm{41}\:\mathrm{divides}\:\mathrm{2}^{\mathrm{20}} −\mathrm{1} \\ $$

Answered by tanmay.chaudhury50@gmail.com last updated on 14/May/18

let us solve analytically... 2^(20) −1=(2^5 )^4 −1 (32)^4 −1=(41−9)^4 −1 =(_ 41)^4 −4C_1 (41)^3 9+4C_2 (41)^2 .9^2 −4C_3 (41).9^3 +9^4 −1 so except (9^4 )rest terms are divisible by 41 now 9^4 −1 (9^2 )^2 −1 (82−1)^2 −1 (82^ )^2 −2×82×1+1−1 (82)^2 −2×82×1 this two terms also divdible by 41 since 82 is divisible by 41

$${let}\:{us}\:{solve}\:{analytically}… \\ $$$$\mathrm{2}^{\mathrm{20}} −\mathrm{1}=\left(\mathrm{2}^{\mathrm{5}} \right)^{\mathrm{4}} −\mathrm{1} \\ $$$$\left(\mathrm{32}\right)^{\mathrm{4}} −\mathrm{1}=\left(\mathrm{41}−\mathrm{9}\right)^{\mathrm{4}} −\mathrm{1} \\ $$$$=\left(_{} \mathrm{41}\right)^{\mathrm{4}} −\mathrm{4}{C}_{\mathrm{1}} \left(\mathrm{41}\right)^{\mathrm{3}} \mathrm{9}+\mathrm{4}{C}_{\mathrm{2}} \left(\mathrm{41}\right)^{\mathrm{2}} .\mathrm{9}^{\mathrm{2}} −\mathrm{4}{C}_{\mathrm{3}} \left(\mathrm{41}\right).\mathrm{9}^{\mathrm{3}} \\ $$$$+\mathrm{9}^{\mathrm{4}} −\mathrm{1} \\ $$$${so}\:{except}\:\left(\mathrm{9}^{\mathrm{4}} \right){rest}\:{terms}\:{are}\:{divisible}\:{by}\:\mathrm{41} \\ $$$${now}\:\mathrm{9}^{\mathrm{4}} −\mathrm{1} \\ $$$$\left(\mathrm{9}^{\mathrm{2}} \right)^{\mathrm{2}} −\mathrm{1} \\ $$$$\left(\mathrm{82}−\mathrm{1}\right)^{\mathrm{2}} −\mathrm{1} \\ $$$$\left(\mathrm{82}^{} \right)^{\mathrm{2}} −\mathrm{2}×\mathrm{82}×\mathrm{1}+\mathrm{1}−\mathrm{1} \\ $$$$\left(\mathrm{82}\right)^{\mathrm{2}} −\mathrm{2}×\mathrm{82}×\mathrm{1}\:\:\:{this}\:{two}\:{terms}\:{also}\:{divdible} \\ $$$${by}\:\mathrm{41}\:{since}\:\mathrm{82}\:{is}\:{divisible}\:{by}\:\mathrm{41} \\ $$

Commented by Rasheed.Sindhi last updated on 15/May/18

$$\mathcal{G}^{\:\overset{\frown} {\mathcal{O}}\overset{\frown} {\mathcal{O}}} \mathcal{D}\:\mathcal{A}{pproach}! \\ $$

Commented by tanmay.chaudhury50@gmail.com last updated on 15/May/18

$${thanx}…{we}\:{can}\:{post}\:{question}\:{along}\:{with}\: \\ $$$${final}\:{answer}\:{so}\:{that}\:{we}\:{get}\:{satisfaction}… \\ $$$${the}\:{people}\:{who}\:{post}\:{question}\:{may}\:{post}\:{question} \\ $$$${different}\:{variety}… \\ $$

Answered by MJS last updated on 14/May/18

2^(20) mod 41=1 (2^(20) mod 41)=(2^(10) mod 41)^2 =(2^5 mod 41)^4 = =(−9)(−9)(−9)(−9)=81×81=(−1)(−1)=1 multiplying remainders can be great fun ;−)

$$\mathrm{2}^{\mathrm{20}} \mathrm{mod}\:\mathrm{41}=\mathrm{1} \\ $$$$\left(\mathrm{2}^{\mathrm{20}} \mathrm{mod}\:\mathrm{41}\right)=\left(\mathrm{2}^{\mathrm{10}} \mathrm{mod}\:\mathrm{41}\right)^{\mathrm{2}} =\left(\mathrm{2}^{\mathrm{5}} \mathrm{mod}\:\mathrm{41}\right)^{\mathrm{4}} = \\ $$$$=\left(−\mathrm{9}\right)\left(−\mathrm{9}\right)\left(−\mathrm{9}\right)\left(−\mathrm{9}\right)=\mathrm{81}×\mathrm{81}=\left(−\mathrm{1}\right)\left(−\mathrm{1}\right)=\mathrm{1} \\ $$$$\left.\mathrm{multiplying}\:\mathrm{remainders}\:\mathrm{can}\:\mathrm{be}\:\mathrm{great}\:\mathrm{fun}\:;−\right) \\ $$

Commented by Rasheed.Sindhi last updated on 15/May/18

V_r ^( e) y Nice!... But using congruence notation were easier and prettier, I think.

$$\mathcal{V}_{{r}} ^{\:{e}} {y}\:\mathcal{N}{ice}!… \\ $$$$\mathrm{But}\:\mathrm{using}\:\mathrm{congruence}\:\mathrm{notation}\:\mathrm{were} \\ $$$$\mathrm{easier}\:\mathrm{and}\:\mathrm{prettier},\:\mathrm{I}\:\mathrm{think}. \\ $$

Commented by MJS last updated on 14/May/18

$$\mathrm{true} \\ $$

Answered by ajfour last updated on 14/May/18

41=2^5 +3^2 2^(20) =(41−3^2 )^4 =41^4 −4.3^2 .41^3 +6.3^4 .41^2 −4.3^6 .41+3^8 3^8 =(2×41−1)^2 =4×41^2 −4×41+1 hence 2^(20) =k(41)+1 ( ∀ k ∈ N ) or 41 divides 2^(20) −1 .

$$\mathrm{41}=\mathrm{2}^{\mathrm{5}} +\mathrm{3}^{\mathrm{2}} \\ $$$$\mathrm{2}^{\mathrm{20}} =\left(\mathrm{41}−\mathrm{3}^{\mathrm{2}} \right)^{\mathrm{4}} \\ $$$$\:\:\:\:\:\:=\mathrm{41}^{\mathrm{4}} −\mathrm{4}.\mathrm{3}^{\mathrm{2}} .\mathrm{41}^{\mathrm{3}} +\mathrm{6}.\mathrm{3}^{\mathrm{4}} .\mathrm{41}^{\mathrm{2}} \\ $$$$\:\:\:\:\:\:\:\:\:\:−\mathrm{4}.\mathrm{3}^{\mathrm{6}} .\mathrm{41}+\mathrm{3}^{\mathrm{8}} \\ $$$$\mathrm{3}^{\mathrm{8}} =\left(\mathrm{2}×\mathrm{41}−\mathrm{1}\right)^{\mathrm{2}} =\mathrm{4}×\mathrm{41}^{\mathrm{2}} −\mathrm{4}×\mathrm{41}+\mathrm{1} \\ $$$${hence}\:\:\:\mathrm{2}^{\mathrm{20}} ={k}\left(\mathrm{41}\right)+\mathrm{1}\:\:\:\:\:\left(\:\forall\:{k}\:\in\:{N}\:\right) \\ $$$${or}\:\:\:\mathrm{41}\:{divides}\:\mathrm{2}^{\mathrm{20}} −\mathrm{1}\:. \\ $$

Commented by Rasheed.Sindhi last updated on 15/May/18

$$\mathcal{G}^{\:\overset{\frown} {\mathcal{O}}\overset{\frown} {\mathcal{O}}} \mathcal{D}\:\:\mathcal{A}{pproach}! \\ $$

Facebook Tweet Pin

Prove-that-41-divides-2-20-1-

Leave a Reply Cancel reply