**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.\)

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

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

## Comments

Sort by:

TopNewestWhy is 17^17 congruent to 7^17?

Log in to reply

because 17 mod 10 is 7

Log in to reply

I got it

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.

Log in to reply

Have you checked out the chinese remainder theorem wiki?

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

Log in to reply

You can read up on Euler's Theorem :)

Log in to reply

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

Log in to reply

Really cool......

Log in to reply