×

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
3 years, 7 months ago

Sort by:

Why is 17^17 congruent to 7^17?

- 3 years, 5 months ago

because 17 mod 10 is 7

- 3 years, 4 months ago

I got it

- 3 years, 5 months ago

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.

- 1 year, 2 months ago

Have you checked out the chinese remainder theorem wiki?

Staff - 1 year, 2 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...

- 2 years, 3 months ago

You can read up on Euler's Theorem :)

Staff - 2 years, 3 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?

- 2 years, 3 months ago

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

Staff - 2 years, 3 months ago

Really cool......

- 3 years ago