Modular arithmetic is a system of arithmetic for integers, which considers the remainder. In modular arithmetic, numbers "wrap around" upon reaching a given fixed quantity (this given quantity is known as the modulus) to leave a remainder. Modular arithmetic is often tied to prime numbers, for instance, in Wilson's theorem, Lucas's theorem, and Hensel's lemma, and generally appears in fields like cryptography, computer science, and computer algebra.
An intuitive usage of modular arithmetic is with a 12-hour clock. If it is 10:00 now, then in 5 hours the clock will show 3:00 instead of 15:00. 3 is the remainder of 15 with a modulus of 12.
A number is the equivalent of asking for the remainder of when divided by . Two integers and are said to be congruent (or in the same equivalence class) modulo if they have the same remainder upon division by . In such a case, we say that
The easiest way to understand modular arithmetic is to think of it as finding the remainder of a number upon division by another number. For example, since both 15 and -9 leave the same remainder 3 when divided by 12, we say that
This allows us to have a simple way of doing modular arithmetic: first perform the usual arithmetic, and then find the remainder. For example, to find , we can take
and divide it by 11, which gives us
However, this could get messy when the numbers get larger. One approach that we could take is to first find the remainders of 123 and 321 when divided by 11 (the remainders are both 2), perform the usual arithmetic, and find the remainder again. In this example, since and , we can conclude that
For a positive integer , the integers and are congruent if their remainders when divided by are the same.
As we can see above, 52 and 24 are congruent (mod 7) because and
Note that is different from
Another way of defining this is that integers and are congruent if their difference is an integer multiple of , that is, if has a remainder of 0.
36 and 10 are said to be congruent (mod 13) because their difference is an integer multiple of , that is,
Properties of addition in modular arithmetic:
- If , then
- If , then for any integer
- If and , then
- If , then
It is currently 7:00 PM. What time (in AM or PM) will it be in 1000 hours?
Time "repeats" every 24 hours, so we work modulo 24. Since
the time in 1000 hours is equivalent to the time in 16 hours. Therefore, it will be 11:00 AM in 1000 hours.
Find the sum of 31 and 148 in modulo 24.
31 in modulo 24 is equivalent to 7. If we use the first modular addition rule stated in this wiki, we find that . 155 in modulo 24 is 11.
As stated previously, 31 in modulo 24 is 7. Instead of using the first rule, we'll use the second rule. 148 is 4 in modulo 24. So now, all we need to find is 7+4, which is .
Find the remainder when is divided by
We know that , , , , , , and . From property 3, we have
Since has a remainder of when divided by , so does and thus the answer is .
Modular multiplication appears in many fields of mathematics and has many far-ranging applications, including cryptography, computer science, and computer algebra.
Properties of multiplication in modular arithmetic:
- If , then .
- If , then for any integer .
- If and , then .
Since and , we have
Find the remainder when is divided by .
We did a similar problem above, where the signs were all instead of . In that case, manually adding the numbers up wouldn't take that much time, though the modular arithmetic solution was faster.
In this example, multiplying the numbers would be very tedious. Instead, we use property 3 repeatedly. We know that , , , , , and . Therefore,
implying the product, upon division by leaves a remainder of
Prove property 3 of multiplication in modular arithmetic as stated below:
If and , then .
By the definition of equivalence, is a multiple of and is a multiple of That is,
for constants and . Then
This implies is a multiple of and therefore , or .
Since exponentiation is repeated multiplication, we have the following:
Property of Exponentiation in Modular Arithmetic:
If , then for any positive integer .
We can write in the form of , where is some integer. Then we have
Now notice how all the terms of this sum are multiples of , except the last when . Hence
We observe that
Then by the property of exponentiation, we have
In the above example, we do not need to find the exact value of , which is very large
What is the last digit of
The last digit of a number is equivalent to the number taken modulo 10. Working modulo 10, we have
Find the last three digits of
We can write as
Since leaves a remainder of when divided by , its last three digits are .
Find an example of integers where , but .
Many combinations of will work here. We present the case with and , where we get , but while .
The important takeaway is that the exponentiation property only works on the base. If you want to work with the powers, you will need Euler's theorem.
This is tricky. Consider . Note that we cannot simply divide both sides of the equation by 2, since . This shows that, in general, division is not well defined. As the following property shows, if we add the condition that are coprime, then division becomes well defined.
Property of division in modular arithmetic:
If and , then .
This property is true because if is a multiple of and , then must divide , or equivalently, .
The modular inverse of in the ring of integers modulo is an integer such that
If and are integers such that , then there exists an integer such that .
is called the multiplicative inverse of modulo
The following Python code shows how we can calculate the modulo inverse by implementing the extended Euclidean algorithm:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
Aditya is excited for his birthday party on Saturday, March 2, 2013. He is turning 16 years old. What day of the week was Aditya born?
Details and Assumptions:
- The recent leap years are 2012, 2008, 2004, 2000, 1996, .... If your answer is Monday, type 1. If your answer is Tuesday, type 2, and so on and so forth. If your answer is Sunday, type 7.
Is there a positive integer for which is a Fibonacci number?
If is a prime of the form , then there are seventh powers (where the +1 accounts for 0). This gives a fighting chance of the residues being distinct from the Fibonacci residues. So, we try the smallest prime of the form , which is 29.
We can check that , which gives us
When looking at the remainder of the Fibonacci numbers taken modulo 29, we obtain the repeating sequence
A quick check shows us that no number appears in both sequences, and thus the answer is no.