## Definition

**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} \]

## Comments

Sort by:

TopNewestWhy is 17^17 congruent to 7^17? – Adarsh Kumar · 2 years, 10 months ago

Log in to reply

– Vederis Leunardus · 2 years, 9 months ago

because 17 mod 10 is 7Log in to reply

– Adarsh Kumar · 2 years, 10 months ago

I got itLog 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. · 7 months, 2 weeks ago

Log in to reply

chinese remainder theorem wiki? – Calvin Lin Staff · 7 months, 2 weeks ago

Have you checked out theLog 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, 9 months ago

Log in to reply

Euler's Theorem :) – Calvin Lin Staff · 1 year, 9 months ago

You can read up onLog in to reply

– John Taylor · 1 year, 9 months ago

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?Log in to reply

– Calvin Lin Staff · 1 year, 9 months ago

Which weird symbols? \( \Pi \) means take the product of, just like \(\Sigma\) means take the sum of.Log in to reply

Really cool...... – Sai Venkatesh · 2 years, 5 months ago

Log in to reply