Calculate 19^(93) (mod 81).


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) .$
Commented by RasheedSindhi last updated on 22/May/17

$Using$ ${(1 + x)}^{n} \equiv 1 + nx (\mod y)$ $(Mentioned by tinkutara elsewhere .)$ ${(1 + 18)}^{93} \equiv 1 + 18 \times 93 (\mod 81)$ $\equiv 1675 (\mod 81)$ $\equiv 20 \times 81 + 55 (\mod 81)$ $\equiv 55 (\mod 81)$
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 ?$
Commented by RasheedSindhi last updated on 22/May/17

$I think {it}^{'} s not general :$ ${(1 + 15)}^{2} \equiv 1 + 2 \times 15 (\mod 7)$ $\equiv 31 (\mod 7)$ $\equiv 3 (\mod 7)$ $But 256 = 7 \times 36 + 4$ $Here 15 and 7 are coprime and$ $formula {doesn}^{'} t work .$
Commented by Tinkutara last updated on 22/May/17

$Then where it can be applied ?$
Commented by mrW1 last updated on 22/May/17

$i f x^{2} m o d y = 0 t h e n a l w a y s$ ${(1 + x)}^{n} m o d y = (1 + n x) m o d y$
Commented by Tinkutara last updated on 22/May/17

$But you have calculated 13^{99} \mod 81$ $\equiv 55 \mod 81 .$ $13^{99} \mod 81 = {(1 + 12)}^{99} \mod 81$ $\equiv (1 + 99 \times 12) \mod 81 \equiv 55 \mod 81$ $But here 12^{2} \mod 81 = 144 \mod 81 \neq 0$
Commented by mrW1 last updated on 22/May/17

$i f x^{2} m o d y = 0 t h e n$ ${(1 + x)}^{n} m o d y = (1 + n x) m o d y$ $t h i s i s a l w a y s t r u e .$ $i f x^{2} m o d y \neq 0 a n d$ $x^{3} m o d y \neq 0 b u t$ $x^{4} m o d y = 0,$ $t h e n y o u s h o u l d c h e c k t h e t e r m s w i t h$ $x^{2} a n d x^{3} s e p a r a t e l y . T h e y m a y b e a l s o$ $d i v i s i b l e b y y, b u t n o t a l w a y s .$
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$
${(1 + x)}^{n} = 1 + n x + \frac{n (n - 1) x^{2}}{2} + \frac{n (n - 1) (n - 2) x^{3}}{6} + . . .$ $= A_{0} + A_{1} + A_{2} + A_{3} + . . .$ $F o r {(1 + x)}^{n} m o d y = (1 + n x) m o d y$ $i t m e a n s A_{2} u p w a r d s i s d i v i s i b l e b y y .$ $T h e c o n d i t i o n f o r t h i s i s$ $x^{2} m o d y = 0$ $o r$ ${\begin{cases} \frac{n (n - 1) x^{2}}{2} m o d y = 0 \\ (n - 2) x m o d 3 = 0 \end{cases}$ $F o r e x a m p l e {(1 + 12)}^{99} m o d 162 = ?$ $x^{2} = 12^{2} = 144 m o d 162 = 144 \neq 0$ $b u t \frac{99 \times 98 \times 12^{2}}{2} = 11 \times 49 \times 9 \times 12^{2}$ $= 11 \times 49 \times 8 \times 162 m o d 162 = 0$ $a n d$ $(99 - 2) \times 12 = 97 \times 4 \times 3 m o d 3 = 0$ $\Rightarrow {(1 + 12)}^{99} m o d 162 = (1 + 99 \times 12) m o d 162$ $= 1189 m o d 162 = 55$
Commented by Tinkutara last updated on 22/May/17

$So it is better to expand using binomial$ $theorem .$
Commented by mrW1 last updated on 22/May/17

$y e s!$
	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 \times 18$ $= 1675 = 81 (20) + 55$ $so 19^{93} (\mod 81) = 55 .$
	Commented by Tinkutara last updated on 21/May/17

	$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)} \equiv 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 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) . . . (1 - \frac{1}{p_{n}})$ $So as 81 = 3^{4}$ $ϕ (81) = 81 (1 - \frac{1}{3}) = 81 \times \frac{2}{3} = 54$ $And hence$ $19^{54} \equiv 1 (\mod 81) . . . . . . . . . (i)$ $19^{5} \equiv 10 (\mod 81)$ ${(19^{5})}^{8} \equiv {(10)}^{8} = 100000000 \equiv 73 (\mod 81$ $19^{40} \equiv 73 (\mod 81) . . . . . . . . . (ii)$ $(i) \times (ii) : 19^{54} \times 19^{40} \equiv 1 \times 73 (\mod 81)$ $19^{94} \equiv 73 + 81 \times 12 = 1045 (\mod 81)$ $19^{94} / 19 \equiv 1045 / 19 (\mod 81)$ $19^{93} \equiv 55 (\mod 81)$
Terms of Service
Privacy Policy
Contact: info@tinkutara.com

Question and Answers Forum