Question

Calculate the remainder when 3^293 is divided by 97. I'm not sure how to solve this. My work so far:-
293 = (3*97) + 2

3^293 = 3^(3 * 97 + 2) = 3^2 * (3^3)^97 = 9* 27^97.
I'm stuck here.

Answer 1

is it like a show-your-work problem?

Answer 2

I guess we need to bring modular arithmetic into this?
I find that stuff rather difficult...

Answer 3

But we are talking remainders so mod arithmetic comes to mind.

Answer 4

OK i 've found the solution.
You use Fermat's Little Theorem

Answer 5

x^p = x mod p where p is a prime number
so here we have

3^293 mod 97 = ( 9*27^97) mod 97
= (9 * 27) mod 97
= (243) mod 97
= 49 mod 97

so the remainder is 49.

Answer 6

Please check my work

Answer 7

@ganeshie8

Answer 8

i think it's correct

Answer 9

yea I came across Fermats Little theorem browsing a chapter on modular arithmetic. That was new to me.

Answer 10

oh in number theory and arithmetic therma is really important :")and this theorem too

Answer 11

there is also thermat's big theorem

Answer 12

I'd only heard of Fermats Last Theorem whose proof had to wait for centuries!!

Answer 13

i think it is thermats big theory you are talking about..it was proveid in 90's wiles needed 7 years to prove :)

Answer 14

he wote that he had the proof but didn't have free space to write it on the margin..wiles needed 150 pages or more ;)

Answer 15

Wow! Thats the one about a^n + b^n= c^n being not true for n = integer >2 right?

Answer 16

yeah that is: but it is proved and numbers are found to satisfy that

Answer 17

There are numbers which satisfy that? That I didn't know. Whole numbers?

Answer 18

Hey!

Answer 19

yaeh,you can google

Answer 20

Your work looks perfect!

Answer 21

http://www.wolframalpha.com/input/?i=3%5E293+mod+97

Answer 22

Good! I'm beginning to get a better grasp of modular arithmetic. THanks ganeshie.

Answer 23

Just for the sake of an alternative, notice that :

\[x^p\equiv x\pmod{p}\]

is same as

\[x^{p-1}\equiv 1\pmod{p}\]

whenever \(\gcd(x,p)=1\)

Answer 24

Therefore, rising both sides to \(k\)th power we get :
\[(x^{p-1})^k \equiv 1 \pmod{p}\]

Answer 25

thats looks a useful result

Answer 26

Since \(97\) is prime, we have :
\[(3^{96})^k\equiv 1\pmod{97}\]

Answer 27

plugging \(k=3\) gives
\[3^{288}\equiv 1\pmod{97}\]

Answer 28

multiply both sides by \(3^5\) and we're done!

Answer 29

yes
3^5 = 243

Answer 30

great