Modulo Problems

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

#NumberTheory #ModularArithmetic #HelpMe! #brillianthelp #Pleasehelp

Note by Krishna Ar
7 years ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

I have completely different approach to the question to make it look very simple, 32012couldbewrittenas:(34)503itisquiteinterestingtonotethat81multipliedby81henceforthchangesitstensdigitafter5cyclicrepetitionsi.e.8,6,4,2,0,8........unitdigitwillalwaysbe1dividepowerby5i.e.5035R=3findthethirdstensdigitsi.e.4answerwillbe41{ 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 - 7 years ago

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 - 7 years ago

Log in to reply

Akshaj is the bomb diggity. :D

Finn Hulse - 7 years ago

Log in to reply

I somehow don't really understand that comment.

Yuxuan Seah - 7 years ago

Log in to reply

@Yuxuan Seah Oh I'm just saying he's awesome. :D

Finn Hulse - 7 years ago

Log in to reply

@Finn Hulse Oh haha :D

Yuxuan Seah - 7 years 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 :)

Krishna Ar - 7 years ago

Log in to reply

Check out my set Olympiad Number Theory for similar notes.

You 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 - 7 years ago

Log in to reply

@Calvin Lin @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 - 7 years ago

@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 - 7 years ago

Log in to reply

Use something called eulers totient theorem, which states 3201232012(modϕ(100))32012(mod40)312(33)4274729229241(mod100)3^{2012}\equiv 3^{2012\pmod{\phi(100)}}\equiv 3^{2012\pmod{40}}\equiv 3^{12}\equiv (3^3)^4\equiv 27^4\equiv 729^2\equiv 29^2\equiv 41 \pmod{100}

Where ϕ(n)\phi(n) denotes the number of numbers less than nn that are relatively prime to nn.

Nathan Ramesh - 7 years ago

Log in to reply

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. @Nathan Ramesh

Krishna Ar - 7 years ago

Log in to reply

@Krishna Ar 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 know

Nathan Ramesh - 7 years ago

Log in to reply

@Nathan Ramesh Oh! Well :)

Krishna Ar - 7 years ago

@Nathan Ramesh 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...:)

Krishna Ar - 7 years ago

Log in to reply

@Krishna Ar What I did is essentially the same thing.

Nathan Ramesh - 7 years ago

Log in to reply

@Nathan Ramesh 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? :/

Krishna Ar - 7 years ago

Log in to reply

@Krishna Ar No, give me another example and I will show you

Nathan Ramesh - 7 years ago

Log in to reply

@Nathan Ramesh Hi @Nathan Ramesh - Take a look at this one- calculating 71728mod1000 7^{1728} mod 1000 . Using the euler theorem, you get that phi (1000)= 400. so this is equal to 7128mod1000 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 - 7 years ago

Log in to reply

@Krishna Ar No te that it equals 4964=(501)6449^{64}=(50-1)^{64} you can expand it with binomial theorem but note that 5030(mod1000)50^3\equiv 0\pmod{1000} so all the first 62 terms cancel. The 50250^2 term also is 0 mod 1000 then you can just do the last two terms easily :)

Nathan Ramesh - 7 years ago

Log in to reply

@Nathan Ramesh OK. Why do the first 62 terms cancel...I didnt get it could you explain again @Nathan Ramesh

Krishna Ar - 7 years ago

Log in to reply

@Krishna Ar When you expand it with binomial theorem the first 62 terms are all 0 mod 100 because they contain a 50^3

Nathan Ramesh - 7 years ago

Log in to reply

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

Krishna Ar - 7 years ago

Log in to reply

@Krishna Ar Yes, correct. It is simple.

Nathan Ramesh - 7 years ago

Log in to reply

@Nathan Ramesh 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? @Nathan Ramesh

Krishna Ar - 7 years ago

Log in to reply

@Krishna Ar Well since it's minus like (50-1) not (50+1) it's 501(6463)1163+164=3199801(mod1000)-50^1*\dbinom{64}{63}*11^{63}+1^{64}=-3199\equiv 801\pmod{1000}

Nathan Ramesh - 7 years ago

Log in to reply

@Nathan Ramesh Oh! My bad, :P.....So can binomial theorem used to simplify modular exponentiation...an genral rule?

Krishna Ar - 7 years ago

Log in to reply

@Krishna Ar 7 is a good number

Nathan Ramesh - 7 years ago

Log in to reply

@Nathan Ramesh Cyclic its decimal representations are you mean :P ?

Krishna Ar - 7 years ago

Log in to reply

@Krishna Ar No 49 is one less than 50

Nathan Ramesh - 7 years ago

Log in to reply

@Nathan Ramesh Oh...Ok,...you meant that :)

Krishna Ar - 7 years ago
×

Problem Loading...

Note Loading...

Set Loading...