Question and Answers Forum

All Questions      Topic List

Number Theory Questions

Previous in All Question      Next in All Question      

Previous in Number Theory      Next in Number Theory      

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

Terms of Service

Privacy Policy

Contact: info@tinkutara.com