Again I am back with my lame questions....they are so lame that you would doubt if I am a legit level 5 In Number theory.

Find 3^2012's last 2 digits and also try to find its last 3 digits is the question

I know its mod 100 but i am not able to simplify it.

I would love if someone could tell me NOT ONLY HOW TO SOLVE THIS, BUT ALSO HOW TO SOLVE ANY SUCH PROBLEM USING MOD 100, 1000....AND ALSO HOW TO DO MODULAR EXPONENTIATION FAST. Thanks

## Comments

Sort by:

TopNewestI have completely different approach to the question to make it look very simple, \({ 3 }^{ 2012 }\quad could\quad be\quad written\quad as:\\ { { (3 }^{ 4 }) }^{ 503 }\\ it\quad is\quad quite\quad interesting\quad to\quad note\quad that\quad 81\quad multiplied\quad by\quad 81\quad henceforth\quad changes\\ its\quad ten's\quad digit\quad after\quad 5\quad cyclic\quad repetitions\quad i.e.\quad 8,6,4,2,0,8........\\ unit\quad digit\quad will\quad always\quad be\quad 1\\ \Rrightarrow divide\quad power\quad by\quad 5\quad i.e.\frac { 503 }{ 5 } R=3\\ find\quad the\quad third's\quad ten's\quad digits\quad i.e.\quad 4\\ answer\quad will\quad be \boxed{41}\) – Utkarsh Rajput · 2 years, 11 months ago

Log in to reply

If you're not already aware, @Finn Hulse created this Modular Arithmetic set for you.

For further resources, you can look at #Modular Arithmetic, or do a search and filter by tags. @Akshaj Kadaveru 's note on Modular Arithmetic is a detailed introduction. – Calvin Lin Staff · 2 years, 12 months ago

Log in to reply

– Krishna Ar · 2 years, 12 months ago

Yes, sir. I am aware of this. But thanks to Nathan Ramesh I came to know of the Euler Theorem. Since then, i learnt a lot more about this topic and am yet learning. And I haven't seen a note about Euler's theorem anywhere, thus didnt know till recently. Thanks :)Log in to reply

Olympiad Number Theory for similar notes.

Check out my setYou could also do a search for Euler's Theorem, and filter by notes, which will display my note on Euler's Theorem. – Calvin Lin Staff · 2 years, 12 months ago

Log in to reply

@Calvin Lin - I extremely apologize for the inadvertent error of mine while setting up the answer of the question- "Integral Divisors". Your answer was right. Kindly change it as required. Thanks – Krishna Ar · 2 years, 12 months ago

Log in to reply

– Finn Hulse · 2 years, 12 months ago

Akshaj is the bomb diggity. :DLog in to reply

– Yuxuan Seah · 2 years, 12 months ago

I somehow don't really understand that comment.Log in to reply

– Finn Hulse · 2 years, 12 months ago

Oh I'm just saying he's awesome. :DLog in to reply

– Yuxuan Seah · 2 years, 11 months ago

Oh haha :DLog in to reply

@Finn Hulse @Daniel Liu @Nathan Ramesh please help me out..is it some kind of a cycle or is it modular exponentiaiton...please tell me! :) – Krishna Ar · 2 years, 12 months ago

Log in to reply

Where \(\phi(n)\) denotes the number of numbers less than \(n\) that are relatively prime to \(n\). – Nathan Ramesh · 2 years, 12 months ago

Log in to reply

@Nathan Ramesh – Krishna Ar · 2 years, 12 months ago

Thanks :) ,....Thanks a lot!!!!!!!...Could you tell me how to learn more about these? For eg:- I knew this function but not this theorem :(....So any form of resource would be appreciated.Log in to reply

– Nathan Ramesh · 2 years, 12 months ago

There isn't anything in particular that I think you have to read. I learned it all from browsing brilliant problems and googling things I don't knowLog in to reply

– Krishna Ar · 2 years, 12 months ago

Hey, Is this the only way to do it? Doesn't modular exponentiation work here? I am just asking becuase I want to know a different way...:)Log in to reply

– Nathan Ramesh · 2 years, 12 months ago

What I did is essentially the same thing.Log in to reply

– Krishna Ar · 2 years, 12 months ago

Ok. Yes. SO this works only if 3 is coprime to 100. So, for other cases you have to use the lengthy modular exponentiation right? And was this too easy a problem? :/Log in to reply

– Nathan Ramesh · 2 years, 12 months ago

No, give me another example and I will show youLog in to reply

@Nathan Ramesh @Finn Hulse pL answer – Krishna Ar · 2 years, 12 months ago

Log in to reply

@Nathan Ramesh - Take a look at this one- calculating \( 7^{1728} mod 1000\) . Using the euler theorem, you get that phi (1000)= 400. so this is equal to \( 7^{128} mod1000\) . How do I simplify it further.? @Finn Hulse you too have a look at this please. And i would like some further genralization on how to simplify such large mod powers. :) – Krishna Ar · 2 years, 12 months ago

HiLog in to reply

– Nathan Ramesh · 2 years, 12 months ago

No te that it equals \(49^{64}=(50-1)^{64}\) you can expand it with binomial theorem but note that \(50^3\equiv 0\pmod{1000}\) so all the first 62 terms cancel. The \(50^2\) term also is 0 mod 1000 then you can just do the last two terms easily :)Log in to reply

@Nathan Ramesh – Krishna Ar · 2 years, 12 months ago

OK. Why do the first 62 terms cancel...I didnt get it could you explain againLog in to reply

– Nathan Ramesh · 2 years, 12 months ago

When you expand it with binomial theorem the first 62 terms are all 0 mod 100 because they contain a 50^3Log in to reply

@Nathan Ramesh – Krishna Ar · 2 years, 12 months ago

Okay, the last two don't and all I have to do is find their sum and get it mod 1000 ...rite?Log in to reply

– Nathan Ramesh · 2 years, 12 months ago

Yes, correct. It is simple.Log in to reply

@Nathan Ramesh – Krishna Ar · 2 years, 12 months ago

Wow! Thank you. So they're like 64c63 into 50 and 1 into 1...so it becomes 3201 mod 1000 equal to 201. but answer is 801...am i wrong somewer?Log in to reply

– Nathan Ramesh · 2 years, 12 months ago

Well since it's minus like (50-1) not (50+1) it's \(-50^1*\dbinom{64}{63}*11^{63}+1^{64}=-3199\equiv 801\pmod{1000}\)Log in to reply

– Krishna Ar · 2 years, 12 months ago

Oh! My bad, :P.....So can binomial theorem used to simplify modular exponentiation...an genral rule?Log in to reply

– Nathan Ramesh · 2 years, 12 months ago

7 is a good numberLog in to reply

– Krishna Ar · 2 years, 12 months ago

Cyclic its decimal representations are you mean :P ?Log in to reply

– Nathan Ramesh · 2 years, 12 months ago

No 49 is one less than 50Log in to reply

– Krishna Ar · 2 years, 12 months ago

Oh...Ok,...you meant that :)Log in to reply

– Krishna Ar · 2 years, 12 months ago

Oh! Well :)Log in to reply