Modular Arithmetic

Definition

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

ab(modN).a \equiv b \pmod{N}.

Here are a few properties of Modular Arithmetic:

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

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

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

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

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

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

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

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

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

What about division? Consider 48(mod4) 4 \equiv 8 \pmod{4}. Note that we cannot simply divide both sides of the equation by 2, since 2≢4(mod4) 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 k, N are coprime, then division becomes well defined:

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

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

I. If a a and NN are integers such that gcd(a,N)=1 \gcd (a, N)=1, then there exists an integer x x such that ax1(modN) ax \equiv 1 \pmod{N}. x x is called the multiplicative inverse of a a modulo N. 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

100016+(24×41)16(mod24), 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 1717 17^{17}?

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

1717717(72)87(mod10)(49)87987(mod10)(92)47(81)47(mod10)1477(mod10).\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
5 years, 7 months ago

No vote yet
1 vote

  Easy Math Editor

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.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Why is 17^17 congruent to 7^17?

Adarsh Kumar - 5 years, 5 months ago

Log in to reply

because 17 mod 10 is 7

Vederis Leunardus - 5 years, 5 months ago

Log in to reply

I got it

Adarsh Kumar - 5 years, 5 months ago

Log in to reply

Really cool......

Sai Venkatesh - 5 years, 1 month 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 - 4 years, 4 months ago

Log in to reply

You can read up on Euler's Theorem :)

Calvin Lin Staff - 4 years, 4 months ago

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?

John Taylor - 4 years, 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 - 4 years, 4 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. - 3 years, 3 months ago

Log in to reply

Have you checked out the chinese remainder theorem wiki?

Calvin Lin Staff - 3 years, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...