Bigger the mod bigger the remainder

Number Theory Level 3

Find 999 111 m o d 888 { 999 }^{ 111 }\quad mod\quad 888


The answer is 111.

Shivamani Patil by shivamani patil , 21, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

999 ≡ 111 ( m o d 888 ) 999 \equiv 111 \pmod {888} so, 99 9 111 ≡ 11 1 111 ( m o d 888 ) 999^{111} \equiv 111^{111} \pmod {888} .

11 1 2 ≡ 1 ( m o d 888 ) 111^2 \equiv 1 \pmod {888} or 11 1 111 ≡ 111 ( m o d 888 ) 111^{111} \equiv 111 \pmod {888} so, 99 9 111 ≡ 11 1 111 ≡ 111 ( m o d 888 ) 999^{111} \equiv 111^{111} \equiv 111 \pmod {888}

3 Helpful 0 Interesting 0 Brilliant 0 Confused
Kartik Sharma
Oct 31, 2014

Use CRT!

We have to find 111 111 = 0 m o d 888 {111}^{111} = 0 mod 888

111 111 = 0 m o d 111 {111}^{111} = 0 mod 111

111 111 = 7 m o d 8 {111}^{111} = 7 mod 8 [This can be found using euler's totient function]

Now using CRT,

111 111 = 111 ∗ 7 ∗ 7 m o d 888 {111}^{111} = 111*7*7 mod 888

111 111 = 111 m o d 888 {111}^{111} = 111 mod 888

Anyone having any doubts on the CRT step can ask in the comments.

0 Helpful 0 Interesting 0 Brilliant 0 Confused

Try to write your mod's in LaTeX with the code \pmod{n} which gives

( m o d n ) \pmod{n}

Sharky Kesa - 6 years, 6 months ago

sorry i have no idea about totient fuction nor CRT..can u solve in a more simple way?

Ritam Baidya - 6 years, 6 months ago

last third step plz explain again @Kartik Sharma

Harshi Singh - 5 years, 11 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...