My Math Forum A Modular Arithmetic Question

 Number Theory Number Theory Math Forum

 April 2nd, 2013, 02:23 AM #1 Member   Joined: Apr 2013 Posts: 65 Thanks: 0 A Modular Arithmetic Question What are the last 2 digits of $2005^{2003^{2004}+3}$ when written in base 3?
 April 2nd, 2013, 06:25 AM #2 Member   Joined: Mar 2013 Posts: 90 Thanks: 0 Re: A modular-arithmetic question $2003\equiv2\pmod3$ and $2^2\equiv1\pmod3$ so $2003^{2004}\equiv2^{2004}=(2^2)^{1002}\equiv1\pmod 3$. Hence $2003^{2004}+3\equiv1\pmod3$, say $2003^{2004}+3=3N+1$. Now $2005\equiv2+0+0+5=7\pmod9$ and $7^3\equiv1\pmod9$. Hence $2005^{2003^{2004}+3}\equiv7^{3N+1}\equiv(7^3)^N\cd ot7\equiv7\pmod9$, i.e. the last two digits in base 3 are 21.
 April 2nd, 2013, 06:45 AM #3 Member   Joined: Apr 2013 Posts: 65 Thanks: 0 Re: A Modular Arithmetic Question Oh I see. Thanks a lot, I tried to use mod 100 and then turn the result into the third base but it clearly didn't work so well. Base conversions always confuse me. I have a question though, shouldn't we use instead mod 8 instead of 9? What I mean by that is: $2005^{\phi(9)}\equiv1\pmod9$ and $\phi(9)=8 \Longrightarrow 2003^{2004}\equiv(x)\pmod8$
 April 2nd, 2013, 07:10 AM #4 Member   Joined: Mar 2013 Posts: 90 Thanks: 0 Re: A modular-arithmetic question We take mod 9 because we’re working in base 3 and $9=3^2$ (just as if you wanted the last two digits in base 10 you would take mod 100 as $100=10^2$). By the way, my original proof was incorrect in some details. I’ve edited and fixed my post.
 April 2nd, 2013, 07:33 AM #5 Member   Joined: Apr 2013 Posts: 65 Thanks: 0 Re: A Modular Arithmetic Question Yeah now it's clear, thanks. I meant $\phi(9)=6$ btw, a little brain malfunction there. So we can either take mod 3 or 6 because both $2005^{3k}$ and $2005^{6k}\equiv1\pmod9$, thats what I tried to mean. I have one last question. Last 2 digits of $9^{8^{7^{6^{5^{4^{3^{2}}}}}}}$ ?
 April 2nd, 2013, 11:57 AM #6 Member   Joined: Mar 2013 Posts: 90 Thanks: 0 Re: A modular-arithmetic question Well, $9^{10}\equiv1\pmod{100}$ so try and work around that.
April 2nd, 2013, 12:19 PM   #7
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: A modular-arithmetic question

Quote:
 Originally Posted by Nehushtan By the way, my original proof was incorrect in some details. I’ve edited and fixed my post.
I think it's still wrong -- or else I'm making a mistake. n^6 = 1 mod 9 for n not divisible by 3, so 2005^(2003^2004) = 2005^(2003^2004 mod 6) mod 9. 2003^2004 is 1 mod 6, so 2005^(2003^2004) = 2005 = 7 mod 9. Adding 3 you get 1, so the last two digits are 01.

 April 2nd, 2013, 12:33 PM #8 Member   Joined: Apr 2013 Posts: 65 Thanks: 0 Re: A Modular Arithmetic Question CRGreathouse: I guess you missaw it, it should be 2005^(2003^(2004)+3) instead of 2005^(2003^2004) + 3. So 2003^2004 is 1 mod 6, adding 3 you get 4. 2005^(6k+4)=7 (mod 9) Nehushtan: How do you know that 9^10=1 (mod 100) ?
April 2nd, 2013, 12:55 PM   #9
Senior Member

Joined: Mar 2012

Posts: 572
Thanks: 26

Re: A Modular Arithmetic Question

Quote:
 Originally Posted by Drake Nehushtan: How do you know that 9^10=1 (mod 100) ?
Have a look at the pattern (mod 100) of 9^1, 9^2, 9^3 - you should spot it fairly early on.

 April 2nd, 2013, 01:11 PM #10 Member   Joined: Apr 2013 Posts: 65 Thanks: 0 Re: A Modular Arithmetic Question Alright thanks. I tried to take mod 40 but it didn't work out.

 Tags arithmetic, modular, question

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post aaron-math Number Theory 3 August 27th, 2012 08:51 AM mathslog Number Theory 1 April 6th, 2012 03:08 PM Hanny David Number Theory 0 January 24th, 2009 03:48 PM Ciachyou Number Theory 1 January 23rd, 2009 11:58 AM Drake Algebra 4 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top