Number theory: What are the last 4 digits of 2^503? (No calculator)

Question

This was an extra credit question on a math test (was not related to what we are learning/have learned)

 

Apparently, it's 0008, because 2^X repeats its last 4 digits every 500 numbers in a pattern, starting at n=3

 

I got the additional information that the repetition of 2^X can be modeled by f(x)= (4/5)(5^X), where X is the number of digits in the pattern (in this case, 4), and f(x) is the amount of values before the pattern repeats itself, also, the pattern begins at n=x.

 

It may seem as if I have answered my own question, but how could I have solved this WITHOUT a calculator? (a quick modulo could have given me 2^503mod1000=8, of course)

Answer 1

Hi Bob,

 

I can see why this problem was confusing for you.  The information about the repetition of 2^X is incorrect as stated, at least in my interpretation of what you have written.  

 

What is incorrect is the starting point of the pattern, and what is missing is a complete statement of the pattern, including an explanation of how to obtain the number of digits in the pattern.

 

Before I correct/amend the repetition pattern formula, let me show you how you could obtain the last four digits of 2^503 essentially by hand.  

 

To find the last n digits of a number, you want to compute its residue modulo 10^n; so here, we want to compute the residue modulo 10^4 (I notice in the last line of your post, you compute modulo 1000=10^3, which leads to the erroneous conclusion).

 

So, we want to compute:

 

2^503 mod 10^4

 

Now, you may have already encountered Euler's generalization of Fermat's  Theorem in class, or else this problem may have been intended to motivate the discussion of it.  The theorem states 

 

(ET)   gcd(a,n)=1  implies  a^φ(n) = 1 (mod n)

 

where φ(n) is Euler's totient function, and counts the number of integers between 1 and n (inclusive) that are relatively prime to n.  It is known that φ(p^k) = p^k - p^(k-1) for any prime p.

 

We will use (ET) to help us compute 2^503 (mod 10^4) by first computing its residue mod 5^4, since gcd(2,5^4) = 1.  First, let's compute φ(5^4):

 

φ(5^4) = 5^4 - 5^(4-1) = 625 - 125 = 500

 

Now, compute:

 

2^503 = (2^500)(2^3) = 2^3 = 8 (mod 5^4)

 

where we have used (ET) with a=2 and n=5^4.

 

But we are trying to compute 2^503 mod 10^4, not mod 5^4, so let's write what we know now, but in quotient form:

 

(I)    2^503 = x⋅10^4 + r   

(II)   2^503 = y⋅5^4 + 8

 

The equation (I) expresses our sought after residue r of 2^503 mod 10^4, while (II) reiterates that 2^503 is 8 mod 5^4.  Equating the right-hand sides of (I) and (II), and solving for r, we get:

 

(III)   r = (y - 16x)⋅5^4 + 8

 

after noting that 10^4 = 2^4⋅5^4 = 16⋅5^4.

 

Let's examine what we have so far.  The residue r has to be an integer in the set {0, 1, ... , 10^4 - 1}, which implies that (y - 16x) is in the set {0, 1, ... , 2^4 - 1}.  

 

But we can do better.  From (II), we know that 8 must divide y, so that 8 must also divide (y - 16x).  But this implies that (y - 16x) is in the smaller set {0, 2^3}, i.e. (y - 16x) is either 0 or 8.  

 

Suppose (y - 16x) = 0, so that r=8.  Then, equation (I) implies that

 

2^503 = x⋅10^4 + 8,

 

which is impossible, since upon rearranging we would have

 

2^503 = 8(2x⋅5^4 + 1)

 

and clearly (2x⋅5^4 + 1) is odd, hence cannot equal 2^503/8 = 2^500.

 

So, it must be that (y - 16x) = 8, whereby 

 

r = (y - 16x)⋅5^4 + 8 = 8⋅5^4 + 8 = 5008.

 

In other words, the last four digits of 2^503 are 5008, not 0008.

 

Finally, the correct statement of your repetition pattern formula:

 

2^x mod 10^n has the the same last n digits as 2^(x + k⋅f(x)), for k≥1, starting at any 2^x greater than 10^n.  This last bit is crucial.  See if you can figure out why.  f(x) here is the same (4/5)5^x as in your information.

 

Hope this clears it up.  I take responsibility for all errors I may have made.

 

Regards,

Hassan