Modular Arithmetic: A Brief Primer

In order to make the previous post understandable, I will explain some of the machinery behind what I did. It would make it even harder to understand if I included it in the problem itself, so I made a separate post. (If you already understand what I am talking about, please don't read this explanation, as it may cause you to cringe a little)

Modular arithmetic is basically arithmetic with remainders. When we take a number modulo (often shortened to "mod") n, we consider only its remainder when divided by n. We can add, and multiply these remainders in a similar fashion to standard addition and multiplication. Division also works,  so long as you are dividing by something relatively prime to n.  "Equality" is called congruence, and is often denoted by ≡ (a lot of the time people just use =). 

If we are working mod 7:  3+4≡0  5*9≡3 7k≡0 for any integer k

You can think of modular arithmetic as doing arithmetic on a clock, except with n hours. 

The last n digits of a number is equivalent to taking that number mod 10^n.

It is often important in contest problems to compute a^k (mod n), to that end, there are some important theorems:

Fermat's Little Theorem:

a^p≡a (mod p)

alternatively a^p-1≡1 (mod p), for a relatively prime to p.

Proof: Consider the numbers a, 2a, 3a, ... (p-1)a.

Mod p, they are congruent to 1,2,...(p-1) in some order, as they are all distinct, and nonzero, and there are only p-1 nonzero remaidners mod p.  (They are nonzero because a is not congruent to p, and p is prime, so ab can't be a multiple of p if neither a nor b is)
(They are distinct because we can divide out by a)

So if we multiply them all (mod p), we get (p-1)!,
so (a^(p-1))(p-1)!≡(p-1)! (mod p)

We can divide out (p-1)!, concluding our proof. 

(The first statement of the theorem includes the case a≡0, but this is trivial, as 0^p is obviously 0)

But what happens when we are not using a prime?

The theorem does not remain true.

Mod 6, 2^5≡2, which is obviously not 1. 

The issue comes from the fact that 2 is not relatively prime to 6, so 2*n is always 6k+2w, so it can only be congruent to 2, 4, or 0 mod 6. 

However, we can make a revision of the theorem, to correct for this. This is called Euler's theorem, and is the one I used in the previous post. 

Let phi(n) be the number of numbers less than n that are relatively prime to n.

a^phi(n)≡1 (mod n)

This is true by basically the same reasoning as the previous theorem, just list all the numbers relatively prime to n. (there are phi(n)) of them.