Menu Close

Calculate-19-93-mod-81-

Tinku Tara 0 Comments
Pin




Question Number 13584 by Tinkutara last updated on 21/May/17
Calculate 19^(93) (mod 81).
$$\mathrm{Calculate}\:\mathrm{19}^{\mathrm{93}} \:\left(\mathrm{mod}\:\mathrm{81}\right). \\ $$
Commented by RasheedSindhi last updated on 22/May/17
Using (1+x)^n ≡1+nx(mod y) (Mentioned by tinkutara elsewhere.) (1+18)^(93) ≡1+18×93(mod 81) ≡1675(mod 81) ≡20×81+55(mod 81) ≡55(mod 81)
$$\mathrm{Using} \\ $$$$\left(\mathrm{1}+\mathrm{x}\right)^{\mathrm{n}} \equiv\mathrm{1}+\mathrm{nx}\left(\mathrm{mod}\:\mathrm{y}\right) \\ $$$$\:\:\:\:\:\left(\mathrm{Mentioned}\:\mathrm{by}\:\mathrm{tinkutara}\:\mathrm{elsewhere}.\right) \\ $$$$\left(\mathrm{1}+\mathrm{18}\right)^{\mathrm{93}} \equiv\mathrm{1}+\mathrm{18}×\mathrm{93}\left(\mathrm{mod}\:\mathrm{81}\right) \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\equiv\mathrm{1675}\left(\mathrm{mod}\:\mathrm{81}\right) \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\equiv\mathrm{20}×\mathrm{81}+\mathrm{55}\left(\mathrm{mod}\:\mathrm{81}\right) \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\equiv\mathrm{55}\left(\mathrm{mod}\:\mathrm{81}\right) \\ $$
Commented by Tinkutara last updated on 22/May/17
But it was my doubt, is it true in all cases even when x and y have no common factor?
$$\mathrm{But}\:\mathrm{it}\:\mathrm{was}\:\mathrm{my}\:\mathrm{doubt},\:\mathrm{is}\:\mathrm{it}\:\mathrm{true}\:\mathrm{in}\:\mathrm{all} \\ $$$$\mathrm{cases}\:\mathrm{even}\:\mathrm{when}\:{x}\:\mathrm{and}\:{y}\:\mathrm{have}\:\mathrm{no} \\ $$$$\mathrm{common}\:\mathrm{factor}? \\ $$
Commented by RasheedSindhi last updated on 22/May/17
I think it′s not general: (1+15)^2 ≡1+2×15(mod 7) ≡31(mod 7) ≡3(mod 7) But 256=7×36+4 Here 15 and 7 are coprime and formula doesn′t work.
$$\mathrm{I}\:\mathrm{think}\:\mathrm{it}'\mathrm{s}\:\mathrm{not}\:\mathrm{general}: \\ $$$$\left(\mathrm{1}+\mathrm{15}\right)^{\mathrm{2}} \equiv\mathrm{1}+\mathrm{2}×\mathrm{15}\left(\mathrm{mod}\:\mathrm{7}\right) \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\equiv\mathrm{31}\left(\mathrm{mod}\:\mathrm{7}\right) \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\equiv\mathrm{3}\left(\mathrm{mod}\:\mathrm{7}\right) \\ $$$$\mathrm{But}\:\:\:\mathrm{256}=\mathrm{7}×\mathrm{36}+\mathrm{4} \\ $$$$\mathrm{Here}\:\mathrm{15}\:\mathrm{and}\:\mathrm{7}\:\mathrm{are}\:\mathrm{coprime}\:\mathrm{and} \\ $$$$\mathrm{formula}\:\mathrm{doesn}'\mathrm{t}\:\mathrm{work}. \\ $$
Commented by Tinkutara last updated on 22/May/17
Then where it can be applied?
$$\mathrm{Then}\:\mathrm{where}\:\mathrm{it}\:\mathrm{can}\:\mathrm{be}\:\mathrm{applied}? \\ $$
Commented by mrW1 last updated on 22/May/17
if x^2 mod y =0 then always (1+x)^n mod y = (1+nx) mod y
$${if}\:{x}^{\mathrm{2}} \:{mod}\:{y}\:=\mathrm{0}\:{then}\:{always} \\ $$$$\left(\mathrm{1}+{x}\right)^{{n}} \:{mod}\:{y}\:=\:\left(\mathrm{1}+{nx}\right)\:{mod}\:{y} \\ $$
Commented by Tinkutara last updated on 22/May/17
But you have calculated 13^(99) mod 81 ≡ 55 mod 81. 13^(99) mod 81 = (1 + 12)^(99) mod 81 ≡ (1 + 99×12) mod 81 ≡ 55 mod 81 But here 12^2 mod 81 = 144 mod 81 ≠ 0
$$\mathrm{But}\:\mathrm{you}\:\mathrm{have}\:\mathrm{calculated}\:\mathrm{13}^{\mathrm{99}} \:\mathrm{mod}\:\mathrm{81} \\ $$$$\equiv\:\mathrm{55}\:\mathrm{mod}\:\mathrm{81}. \\ $$$$\mathrm{13}^{\mathrm{99}} \:\mathrm{mod}\:\mathrm{81}\:=\:\left(\mathrm{1}\:+\:\mathrm{12}\right)^{\mathrm{99}} \:\mathrm{mod}\:\mathrm{81} \\ $$$$\equiv\:\left(\mathrm{1}\:+\:\mathrm{99}×\mathrm{12}\right)\:\mathrm{mod}\:\mathrm{81}\:\equiv\:\mathrm{55}\:\mathrm{mod}\:\mathrm{81} \\ $$$$\mathrm{But}\:\mathrm{here}\:\mathrm{12}^{\mathrm{2}} \:\mathrm{mod}\:\mathrm{81}\:=\:\mathrm{144}\:\mathrm{mod}\:\mathrm{81}\:\neq\:\mathrm{0} \\ $$
Commented by mrW1 last updated on 22/May/17
if x^2 mod y = 0 then (1+x)^n mod y = (1+nx) mod y this is always true. if x^2 mod y ≠ 0 and x^3 mod y ≠ 0 but x^4 mod y = 0, then you should check the terms with x^2 and x^3 separately. They may be also divisible by y, but not always.
$${if}\:{x}^{\mathrm{2}} \:{mod}\:{y}\:=\:\mathrm{0}\:{then}\: \\ $$$$\left(\mathrm{1}+{x}\right)^{{n}} \:{mod}\:{y}\:=\:\left(\mathrm{1}+{nx}\right)\:{mod}\:{y} \\ $$$${this}\:{is}\:{always}\:{true}. \\ $$$$ \\ $$$${if}\:{x}^{\mathrm{2}} \:{mod}\:{y}\:\neq\:\mathrm{0}\:{and} \\ $$$${x}^{\mathrm{3}} \:{mod}\:{y}\:\neq\:\mathrm{0}\:{but} \\ $$$${x}^{\mathrm{4}} \:{mod}\:{y}\:=\:\mathrm{0}, \\ $$$${then}\:{you}\:{should}\:{check}\:{the}\:{terms}\:{with} \\ $$$${x}^{\mathrm{2}} \:{and}\:{x}^{\mathrm{3}} \:{separately}.\:{They}\:{may}\:{be}\:{also} \\ $$$${divisible}\:{by}\:{y},\:{but}\:{not}\:{always}. \\ $$
Commented by mrW1 last updated on 22/May/17
(1+x)^n =1+nx+((n(n−1)x^2 )/2)+((n(n−1)(n−2)x^3 )/6)+... =A_0 +A_1 +A_2 +A_3 +... For (1+x)^n mod y = (1+nx) mod y it means A_2 upwards is divisible by y. The condition for this is x^2 mod y =0 or { ((((n(n−1)x^2 )/2) mod y =0)),(((n−2)x mod 3 =0)) :} For example (1+12)^(99) mod 162=? x^2 =12^2 =144 mod 162 =144≠0 but ((99×98×12^2 )/2)=11×49×9×12^2 =11×49×8×162 mod 162=0 and (99−2)×12=97×4×3 mod 3=0 ⇒(1+12)^(99) mod 162 =(1+99×12) mod 162 =1189 mod 162 =55
$$\left(\mathrm{1}+{x}\right)^{{n}} =\mathrm{1}+{nx}+\frac{{n}\left({n}−\mathrm{1}\right){x}^{\mathrm{2}} }{\mathrm{2}}+\frac{{n}\left({n}−\mathrm{1}\right)\left({n}−\mathrm{2}\right){x}^{\mathrm{3}} }{\mathrm{6}}+… \\ $$$$={A}_{\mathrm{0}} +{A}_{\mathrm{1}} +{A}_{\mathrm{2}} +{A}_{\mathrm{3}} +… \\ $$$${For}\:\left(\mathrm{1}+{x}\right)^{{n}} \:{mod}\:{y}\:=\:\left(\mathrm{1}+{nx}\right)\:{mod}\:{y} \\ $$$${it}\:{means}\:{A}_{\mathrm{2}} \:{upwards}\:{is}\:{divisible}\:{by}\:{y}. \\ $$$${The}\:{condition}\:{for}\:{this}\:{is} \\ $$$${x}^{\mathrm{2}} \:{mod}\:{y}\:=\mathrm{0} \\ $$$${or} \\ $$$$\begin{cases}{\frac{{n}\left({n}−\mathrm{1}\right){x}^{\mathrm{2}} }{\mathrm{2}}\:{mod}\:{y}\:=\mathrm{0}}\\{\left({n}−\mathrm{2}\right){x}\:{mod}\:\mathrm{3}\:=\mathrm{0}}\end{cases} \\ $$$$ \\ $$$${For}\:{example}\:\left(\mathrm{1}+\mathrm{12}\right)^{\mathrm{99}} \:{mod}\:\mathrm{162}=? \\ $$$${x}^{\mathrm{2}} =\mathrm{12}^{\mathrm{2}} =\mathrm{144}\:{mod}\:\mathrm{162}\:=\mathrm{144}\neq\mathrm{0} \\ $$$${but}\:\frac{\mathrm{99}×\mathrm{98}×\mathrm{12}^{\mathrm{2}} }{\mathrm{2}}=\mathrm{11}×\mathrm{49}×\mathrm{9}×\mathrm{12}^{\mathrm{2}} \\ $$$$=\mathrm{11}×\mathrm{49}×\mathrm{8}×\mathrm{162}\:{mod}\:\mathrm{162}=\mathrm{0} \\ $$$${and}\: \\ $$$$\left(\mathrm{99}−\mathrm{2}\right)×\mathrm{12}=\mathrm{97}×\mathrm{4}×\mathrm{3}\:{mod}\:\mathrm{3}=\mathrm{0} \\ $$$$\Rightarrow\left(\mathrm{1}+\mathrm{12}\right)^{\mathrm{99}} \:{mod}\:\mathrm{162}\:=\left(\mathrm{1}+\mathrm{99}×\mathrm{12}\right)\:{mod}\:\mathrm{162} \\ $$$$=\mathrm{1189}\:{mod}\:\mathrm{162}\:=\mathrm{55} \\ $$
Commented by Tinkutara last updated on 22/May/17
So it is better to expand using binomial theorem.
$$\mathrm{So}\:\mathrm{it}\:\mathrm{is}\:\mathrm{better}\:\mathrm{to}\:\mathrm{expand}\:\mathrm{using}\:\mathrm{binomial} \\ $$$$\mathrm{theorem}. \\ $$
Commented by mrW1 last updated on 22/May/17
yes!
$${yes}! \\ $$
Answered by ajfour last updated on 21/May/17
19^(93) =(1+18)^(93) =1+^(93) C_1 (18)+^(93) C_2 (18)^2 +... ......+^(93) C_(92) (18)^(92) +^(93) C_(93) (18)^(93) third term onwards each is divisible by 81, and 1+^(93) C_1 (18)=1+93×18 = 1675 =81(20)+55 so 19^(93) (mod 81) =55 .
$$\mathrm{19}^{\mathrm{93}} =\left(\mathrm{1}+\mathrm{18}\right)^{\mathrm{93}} \\ $$$$\:\:\:\:=\mathrm{1}+^{\mathrm{93}} \mathrm{C}_{\mathrm{1}} \left(\mathrm{18}\right)+^{\mathrm{93}} \mathrm{C}_{\mathrm{2}} \left(\mathrm{18}\right)^{\mathrm{2}} +… \\ $$$$\:\:\:\:\:\:……+^{\mathrm{93}} \mathrm{C}_{\mathrm{92}} \left(\mathrm{18}\right)^{\mathrm{92}} +^{\mathrm{93}} \mathrm{C}_{\mathrm{93}} \left(\mathrm{18}\right)^{\mathrm{93}} \\ $$$$\:\:\mathrm{third}\:\mathrm{term}\:\mathrm{onwards}\:\mathrm{each}\:\mathrm{is} \\ $$$$\mathrm{divisible}\:\mathrm{by}\:\mathrm{81}, \\ $$$$\mathrm{and}\:\mathrm{1}+^{\mathrm{93}} \mathrm{C}_{\mathrm{1}} \left(\mathrm{18}\right)=\mathrm{1}+\mathrm{93}×\mathrm{18} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:=\:\mathrm{1675}\:=\mathrm{81}\left(\mathrm{20}\right)+\mathrm{55} \\ $$$$\mathrm{so}\:\:\:\mathrm{19}^{\mathrm{93}} \:\left(\mathrm{mod}\:\mathrm{81}\right)\:=\mathrm{55}\:. \\ $$
Commented by Tinkutara last updated on 21/May/17
Thanks!
$$\mathrm{Thanks}! \\ $$
Answered by RasheedSoomro last updated on 05/Jun/17
^(Rasheed Sindhi) Since (19,81)=1 Euler theorm can apply Statement of Euler theorm: •If (a,m)=1,then a^(φ(m)) ≡1(mod m) •Here φ(m) is number of coprimes of m which are not greater than m • If m=p_1 ^α_1 p_2 ^α_2 .....p_n ^α_n then φ(m)=m(1−(1/p_1 ))(1−(1/p_2 ))...(1−(1/p_n )) So as 81=3^4 φ(81)=81(1−(1/3))=81×(2/3)=54 And hence 19^(54) ≡1(mod 81).........(i) 19^5 ≡10(mod 81) ( 19^5 )^8 ≡(10)^8 =100000000≡73(mod 81 19^(40) ≡73(mod 81).........(ii) (i)×(ii): 19^(54) ×19^(40) ≡1×73(mod 81) 19^(94) ≡73+81×12=1045(mod 81) 19^(94) /19≡1045/19(mod 81) 19^(93) ≡55(mod 81)
$$\:^{\mathrm{Rasheed}\:\mathrm{Sindhi}} \\ $$$$\mathrm{Since}\:\left(\mathrm{19},\mathrm{81}\right)=\mathrm{1}\:\mathrm{Euler}\:\mathrm{theorm}\:\mathrm{can}\:\mathrm{apply} \\ $$$$\:\:\mathrm{Statement}\:\mathrm{of}\:\mathrm{Euler}\:\mathrm{theorm}: \\ $$$$\bullet\mathrm{If}\:\left(\mathrm{a},\mathrm{m}\right)=\mathrm{1},\mathrm{then} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\mathrm{a}^{\phi\left(\mathrm{m}\right)} \equiv\mathrm{1}\left(\mathrm{mod}\:\mathrm{m}\right) \\ $$$$\bullet\mathrm{Here}\:\phi\left(\mathrm{m}\right)\:\mathrm{is}\:\mathrm{number}\:\mathrm{of}\:\mathrm{coprimes}\:\mathrm{of}\:\mathrm{m} \\ $$$$\mathrm{which}\:\mathrm{are}\:\mathrm{not}\:\mathrm{greater}\:\mathrm{than}\:\mathrm{m} \\ $$$$\bullet\:\:\:\:\:\:\:\:\mathrm{If}\:\mathrm{m}=\mathrm{p}_{\mathrm{1}} ^{\alpha_{\mathrm{1}} } \mathrm{p}_{\mathrm{2}} ^{\alpha_{\mathrm{2}} } …..\mathrm{p}_{\mathrm{n}} ^{\alpha_{\mathrm{n}} } \\ $$$$\:\:\:\:\:\:\mathrm{then}\:\:\phi\left(\mathrm{m}\right)=\mathrm{m}\left(\mathrm{1}−\frac{\mathrm{1}}{\mathrm{p}_{\mathrm{1}} }\right)\left(\mathrm{1}−\frac{\mathrm{1}}{\mathrm{p}_{\mathrm{2}} }\right)…\left(\mathrm{1}−\frac{\mathrm{1}}{\mathrm{p}_{\mathrm{n}} }\right) \\ $$$$\mathrm{So}\:\mathrm{as}\:\mathrm{81}=\mathrm{3}^{\mathrm{4}} \\ $$$$\:\:\:\:\:\:\:\phi\left(\mathrm{81}\right)=\mathrm{81}\left(\mathrm{1}−\frac{\mathrm{1}}{\mathrm{3}}\right)=\mathrm{81}×\frac{\mathrm{2}}{\mathrm{3}}=\mathrm{54} \\ $$$$\mathrm{And}\:\mathrm{hence} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\mathrm{19}^{\mathrm{54}} \equiv\mathrm{1}\left(\mathrm{mod}\:\mathrm{81}\right)………\left(\mathrm{i}\right) \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\mathrm{19}^{\mathrm{5}} \equiv\mathrm{10}\left(\mathrm{mod}\:\mathrm{81}\right) \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\left(\:\mathrm{19}^{\mathrm{5}} \right)^{\mathrm{8}} \equiv\left(\mathrm{10}\right)^{\mathrm{8}} =\mathrm{100000000}\equiv\mathrm{73}\left(\mathrm{mod}\:\mathrm{81}\right. \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\mathrm{19}^{\mathrm{40}} \equiv\mathrm{73}\left(\mathrm{mod}\:\mathrm{81}\right)………\left(\mathrm{ii}\right) \\ $$$$\left(\mathrm{i}\right)×\left(\mathrm{ii}\right):\:\:\mathrm{19}^{\mathrm{54}} ×\mathrm{19}^{\mathrm{40}} \equiv\mathrm{1}×\mathrm{73}\left(\mathrm{mod}\:\mathrm{81}\right) \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\mathrm{19}^{\mathrm{94}} \equiv\mathrm{73}+\mathrm{81}×\mathrm{12}=\mathrm{1045}\left(\mathrm{mod}\:\mathrm{81}\right) \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\mathrm{19}^{\mathrm{94}} /\mathrm{19}\equiv\mathrm{1045}/\mathrm{19}\left(\mathrm{mod}\:\mathrm{81}\right) \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\mathrm{19}^{\mathrm{93}} \equiv\mathrm{55}\left(\mathrm{mod}\:\mathrm{81}\right) \\ $$

Pin

Leave a Reply

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