Calculate-19-93-mod-81-

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 + n x + \frac{n (n - 1) x^{2}}{2} + \frac{n (n - 1) (n - 2) x^{3}}{6} + \dots

= A_{0} + A_{1} + A_{2} + A_{3} + \dots

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} + \dots

\dots \dots +^{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}} \dots . . p_{n}^{α_{n}}

then ϕ (m) = m (1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) \dots (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) \dots \dots \dots (i)

19^{5} \equiv 10 (\mod 81)

{(19^{5})}^{8} \equiv {(10)}^{8} = 100000000 \equiv 73 (\mod 81

19^{40} \equiv 73 (\mod 81) \dots \dots \dots (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)