Even the most avid calculator will shudder at such a calculation! With the power of modular arithmetic, however, we can find the answer without calculations exceeding the calculator's limit. By the end of this chapter, not only will you have the knowledge to perform such a calculation, but I implore that you do so on your own. 

    The % operator is known to any programmer or mathematician with adequate experience as the "modulo" operator. It works much like + or * in that it takes two numbers and returns a single number. Anyone who has done long division will be familiar with the concept of a remainder, that is, the quantity that is left after you've done the repeated subtraction. The modulo is exactly that quantity. For example, 35%4 = 3 because when you divide 35 by 4, the remainder is 3. The modulo operator has the following properties:

• For the operation a%b, a is called the dividend, b is called the divisor and the result is called the modulus.
  
• 0 <= a%b < b
  
• If a%b = n, then a-n is divisible by b
  

    Often times, we find it convenient to, instead of writing something like 45%6, write it as 45 mod 6 as it clearly defines the divisor. The divisor is an important quantity because it defines the "looping point" of our number set. It's very clear to see that 16 mod 6 = 4, 17 mod 6 = 5, and 18 mod 6 = 0 and that it repeats infinitely. This gives us our fourth, and arguably most important, property.

where n is any integer. If we restrict a so that 0 <= a < b, we obtain an easy way to calculate the modulus. For example, 43 mod 7 = 1 + 6(7) mod 7 = 1 mod 7 = 1. It's important to note that this property also allows us to define the modulo operator for negative dividends (though not for negative divisors). -3 mod 10 = 7 + (-1)(10) mod 10 = 7 mod 10 = 7. This fact will become very important when we discuss negative numbers in binary. 

    It's one thing to calculate the modulus, but most times we have an expression inside of the dividend such as 62+12 mod 5 or 43*2 mod 7. It would be useful if we had a way of simplifying dividend in order to calculate the modulus easier. To do that, we have the following operations:

• a+/-b mod n = ((a mod n)+/-(b mod n)) mod n
  
• a*b mod n = ((a mod n)*(b mod n)) mod n
  
• a^b mod n = ((a mod n)^b) mod n
  

where +/- is addition or subtraction.
    Notice that division is not mentioned. This is because it does not have very nice properties with the modulus (due, in part, to the fact that it is so closely related to division). Let's put these properties to use:

• 53+27 mod 7 = (53 mod 7) + (27 mod 7) mod 7 = (4+6(7) mod 7)+(6+3(7) mod 7) mod 7 = 4+6 mod 7 = 3+1(7) mod 7 = 3
  
• 45*16 mod 9 = (45 mod 9)*(16 mod 9) mod 9 = (0+5(9) mod 9)*(5+1(9) mod 9) mod 9 = 0*5 mod 9 = 0
  
• 76^3 mod 35 = (6 + 2(35) mod 35)^3 mod 35 = 6^3 mod 35 = 216 mod 35 = 6 + 6(35) mod 35 = 6
  

    Of the operations discussed in the previous section, the last two should be particularly surprising in that they took a potentially laborious calculation and turned it into simple mental math. It's clear that the modulo operator has the ability to simplify multiplication (which makes sense considering it's related to division) to a great degree. In studying the last property, a pattern emerges quickly. Let's look at the following operations. 3^0 mod 7 = 1, 3^1 mod 7 = 3, 3^2 mod 7 = 2, 3^3 mod 7 = 6, 3^4 mod 7 = 4, 3^5 mod 7 = 5, 3^6 = 1. We arrive back where we began and, according to the third property, this pattern repeats infinitely. Similar to the pattern we see from addition in equation (2), multiplication also has a similar equation.

only if a and n don't share any factors. φ is called the Euler totient function. I won't be covering it in this tutorial but I urge the reader to read the Wikipedia article on it. This number φ(n) is like the "looping point" but for multiplication because clearly a^0 mod n = 1. 

    At this point, you should have the tools you need to tackle the problem I posed at the beginning of the chapter (if you're clever). In the next topic, we will solve the problem that I posed. At this point I'd advise the reader to try and solve it themselves and then return to read the next topic and see how their solution matches up.

    To introduce the topic, I would like to give the reader a nice trick I've used many times in my life. If you want to tell if a number is divisible by 3, add up the digits and if the result is divisible by 3, then so is the original number (the same property applies to 9 but 3 is the easiest to explain and we will discuss how to prove it for the other numbers). Once you have sufficiently convinced yourself this is true, the question becomes "What causes this strange trick?". Luckily, modular arithmetic shows whats really going on, but to prove it will require everything we've talked about up to this point. 

    Using the third property discussed in Section 2, we know that if a mod b = 0, then a is divisible by b. Thus, if a mod 3 = 0, then a is divisible by 3. If a has the digits a0, a1, a2, ... where a0 is the rightmost digit (not a*0), then a = a0 + 10*a1 + 100*a2... 10^n+an. Now the properties discussed in Chapter 3 come into play. Our expression is currently  a0 + 10*a1 + 100*a2... 10^n+an mod 3. If we notice, however, that 10^n mod 3 = (10 mod 3)^n mod 3 = (1+3(3) mod 3)^n mod 3 = 1^n mod 3 = 1, then our expression becomes  a0 + a1 + a2... an mod 3. And thus we arrive at the result. If the sum of the digits is divisible mod 3, then so is the original number. Note that 3 could be any number we want and we can create a way to test any number's divisibility based on the sum of its digits. 

    Now, we are ready to tackle question (1). Let's look at the expression 17^1139. How do we tell what the last digit is? Well if any number can be expanded as  a0 + 10*a1 + 100*a2... 10^n+an. Then if we take the expression modulo 10, we're just left with a0, the rightmost digit. Thus our question becomes "what is 17^1139 mod 10?". Here, we can notice that 17 and 10 don't share any factors, thus we can apply equation (3). If we change the the equation to 17^(3+284(4)) mod 10 = 17^3*17^(4(284)) mod 10 = 17^3*1^284 mod 10 = 17^3 mod 10. At this point we're close to an answer and one could easily give this to a calculator and get an answer. But in the pursuit of applying our knowledge and simplifying things, we can apply property 3 of Section 3 to get (17 mod 10)^3 mod 10 = 7^3 mod 10 = 7*49 mod 10 = 7*(49 mod 10) mod 10 = 7*9 mod 10 = 63 mod 10 = 3. So with some simple equations and mental math, we were able to answer the question fairly easily. 

    I hope that you enjoyed the first part of this tutorial and learned a lot. I wanted to start this because I've noticed both a lack of resources for new people and a large amount of misinformation filling the server. As a math major, I felt it was important to set some things straight and create such a resource. If you have any recommendations (anywhere from future subjects to additions to the current parts) please let me know in the replies. Thanks for reading!