# Modular Arithmetic

## 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}$

Note by Calvin Lin
7 years, 4 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

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.

- 4 years, 11 months ago

Have you checked out the chinese remainder theorem wiki?

Staff - 4 years, 11 months ago

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...

- 6 years, 1 month ago

You can read up on Euler's Theorem :)

Staff - 6 years, 1 month 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?

- 6 years, 1 month ago

Which weird symbols? $\Pi$ means take the product of, just like $\Sigma$ means take the sum of.

Staff - 6 years, 1 month ago

Really cool......

- 6 years, 9 months ago

Why is 17^17 congruent to 7^17?

- 7 years, 2 months ago

because 17 mod 10 is 7

- 7 years, 1 month ago

I got it

- 7 years, 2 months ago