Waste less time on Facebook — follow Brilliant.

Modular Arithmetic


Modular Arithmetic is a system of arithmetic for the integers, in which two integers \(a\) and \(b\) are equivalent (or in the same equivalence class) modulo \(N\) if they have the same remainder upon division by \(N\). In mathematical notation,

\[a \equiv b \pmod{N}.\]

Here are a few properties of Modular Arithmetic:

A. If \(a+b = c\), then \(a + b \equiv c \pmod {N}\).

B. If \( a \cdot b = c\), then \( a\cdot b \equiv c \pmod{N}\).

C. If \( a \equiv b \pmod{N}\), then \( a+k \equiv (b+k) \pmod {N}\) for any integer \( k\).

D. If \( a\equiv b\) and \(c\equiv d \pmod{N}\), then \( a + c \equiv (b + d) \pmod {N}\).

E. If \( a \equiv b \pmod{N}\), then \( ka \equiv kb \pmod{N}\) for any integer \( k\).

F. If \( a \equiv b\) and \(c \equiv d \pmod{N}\), then \( ac \equiv bd \pmod{N}\).

These properties show that addition and multiplication on equivalence classes modulo \(N\) are well defined. Are subtraction and division also well defined? We have the property:

G. If \( a \equiv b \pmod {N}\), then \( -a \equiv -b \pmod{N}\)

We can then use the properties of addition to show that subtraction is defined.

What about division? Consider \( 4 \equiv 8 \pmod{4}\). Note that we cannot simply divide both sides of the equation by 2, since \( 2 \not \equiv 4 \pmod{4}\). This shows that in general, division is not well defined. As the following property shows, if we add the condition that \( k, N\) are coprime, then division becomes well defined:

H. If \( \gcd(k,N)=1\) and \( ka \equiv kb \pmod{N}\), then \( a \equiv b \pmod{N}\).

This property is true because if \( k(a-b)\) is a multiple of \( N\) and \( \gcd(k,N)=1\), then \( N\) must divide \( a-b\), or equivalently, \( a \equiv b \pmod{N}\). We state one final property.

I. If \( a\) and \(N\) are integers such that \( \gcd (a, N)=1\), then there exists an integer \( x\) such that \( ax \equiv 1 \pmod{N}\). \( x\) is called the multiplicative inverse of \( a\) modulo \( N.\)

Worked Examples

1. It is currently 7:00 PM. What time will it be in 1000 hours?

Solution: Time repeats every 24 hours, so we work modulo 24. Since

\[ 1000 \equiv 16 + (24\times 41) \equiv 16 \pmod{24},\]

the time in 1000 hours is equivalent to the time in 16 hours. Therefore, it will be 11:00AM in 1000 hours.


2. What is the last digit of \( 17^{17}\)?

Solution: The last digit of a number is equivalent to the number taken modulo 10. Working modulo 10, we have

\[\begin{array} { l l l l } 17^{17} & \equiv 7^{17} & \equiv (7^2)^8 \cdot 7 & \pmod{10}\\ & \equiv (49)^8 \cdot 7 & \equiv 9^8 \cdot 7 & \pmod{10} \\ & \equiv (9^2)^4 \cdot 7 & \equiv (81)^4 \cdot 7 & \pmod{10} \\ & \equiv 1^4 \cdot 7 & \equiv 7 & \pmod{10}. \end{array} \]

Note by Calvin Lin
2 years, 7 months ago

No vote yet
1 vote


Sort by:

Top Newest

Why is 17^17 congruent to 7^17? Adarsh Kumar · 2 years, 5 months ago

Log in to reply

@Adarsh Kumar because 17 mod 10 is 7 Vederis Leunardus · 2 years, 4 months ago

Log in to reply

@Adarsh Kumar I got it Adarsh Kumar · 2 years, 5 months ago

Log in to reply

I think you should write a wiki on the Chinese remainder theorem. The current one leaves much to be desired. You should create one with detailed examples, and without the assumption of prior knowledge. DarkMind S. · 2 months, 2 weeks ago

Log in to reply

@DarkMind S. Have you checked out the chinese remainder theorem wiki? Calvin Lin Staff · 2 months, 2 weeks ago

Log in to reply

How do you find the last two digits of a large number? Can someone explain Euler's Totient Theorem or Carmichael's Theorem to me because I am severely confused... John Taylor · 1 year, 4 months ago

Log in to reply

@John Taylor You can read up on Euler's Theorem :) Calvin Lin Staff · 1 year, 4 months ago

Log in to reply

@Calvin Lin Thanks, but I still don't understand a few things. Why does phi N = n (1-1/a)(1-1/b)? And what do all the weird symbols on the Euler's Totient Function page mean? John Taylor · 1 year, 4 months ago

Log in to reply

@John Taylor Which weird symbols? \( \Pi \) means take the product of, just like \(\Sigma\) means take the sum of. Calvin Lin Staff · 1 year, 4 months ago

Log in to reply

Really cool...... Sai Venkatesh · 2 years ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...